Java Program for Maximum size square sub-matrix with all 1s
Write a Java program for a given binary matrix, the task is to find out the maximum size square sub-matrix with all 1s.
Approach:
Let the given binary matrix be M[R][C]. The idea of the algorithm is to construct an auxiliary size matrix S[][] in which each entry S[i][j] represents the size of the square sub-matrix with all 1s including M[i][j] where M[i][j] is the rightmost and bottom-most entry in sub-matrix.
Step-by-step approach:
- Construct a sum matrix S[R][C] for the given M[R][C].
- Copy first row and first columns as it is from M[][] to S[][]
- For other entries, use the following expressions to construct S[][]
- If M[i][j] is 1 then
- S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
- Else If M[i][j] is 0 then
- S[i][j] = 0
- If M[i][j] is 1 then
- Find the maximum entry in S[R][C]
- Using the value and coordinates of maximum entry in S[i], print sub-matrix of M[][]
Below is the implementation of the above approach:
Java
// JAVA Code for Maximum size square // sub-matrix with all 1s public class GFG { // method for Maximum size square sub-matrix with all 1s static void printMaxSubSquare( int M[][]) { int i, j; int R = M.length; // no of rows in M[][] int C = M[ 0 ].length; // no of columns in M[][] int S[][] = new int [R][C]; int max_of_s, max_i, max_j; /* Set first column of S[][]*/ for (i = 0 ; i < R; i++) S[i][ 0 ] = M[i][ 0 ]; /* Set first row of S[][]*/ for (j = 0 ; j < C; j++) S[ 0 ][j] = M[ 0 ][j]; /* Construct other entries of S[][]*/ for (i = 1 ; i < R; i++) { for (j = 1 ; j < C; j++) { if (M[i][j] == 1 ) S[i][j] = Math.min( S[i][j - 1 ], Math.min(S[i - 1 ][j], S[i - 1 ][j - 1 ])) + 1 ; else S[i][j] = 0 ; } } /* Find the maximum entry, and indexes of maximum entry in S[][] */ max_of_s = S[ 0 ][ 0 ]; max_i = 0 ; max_j = 0 ; for (i = 0 ; i < R; i++) { for (j = 0 ; j < C; j++) { if (max_of_s < S[i][j]) { max_of_s = S[i][j]; max_i = i; max_j = j; } } } System.out.println( "Maximum size sub-matrix is: " ); for (i = max_i; i > max_i - max_of_s; i--) { for (j = max_j; j > max_j - max_of_s; j--) { System.out.print(M[i][j] + " " ); } System.out.println(); } } // Driver program public static void main(String[] args) { int M[][] = { { 0 , 1 , 1 , 0 , 1 }, { 1 , 1 , 0 , 1 , 0 }, { 0 , 1 , 1 , 1 , 0 }, { 1 , 1 , 1 , 1 , 0 }, { 1 , 1 , 1 , 1 , 1 }, { 0 , 0 , 0 , 0 , 0 } }; printMaxSubSquare(M); } } |
Maximum size sub-matrix is: 1 1 1 1 1 1 1 1 1
Time Complexity: O(m*n), where m is the number of rows and n is the number of columns in the given matrix.
Auxiliary Space: O(m*n), where m is the number of rows and n is the number of columns in the given matrix.
Java Program for Maximum size square sub-matrix with all 1s using Dynamic Programming:
In order to compute an entry at any position in the matrix we only need the current row and the previous row.
Below is the implementation of the above approach:
Java
// Java program for the above approach import java.util.*; class GFG { static int R = 6 ; static int C = 5 ; static void printMaxSubSquare( int M[][]) { int S[][] = new int [ 2 ][C], Max = 0 ; // set all elements of S to 0 first for ( int i = 0 ; i < 2 ; i++) { for ( int j = 0 ; j < C; j++) { S[i][j] = 0 ; } } // Construct the entries for ( int i = 0 ; i < R; i++) { for ( int j = 0 ; j < C; j++) { // Compute the entrie at the current // position int Entrie = M[i][j]; if (Entrie != 0 ) { if (j != 0 ) { Entrie = 1 + Math.min( S[ 1 ][j - 1 ], Math.min(S[ 0 ][j - 1 ], S[ 1 ][j])); } } // Save the last entrie and add the new one S[ 0 ][j] = S[ 1 ][j]; S[ 1 ][j] = Entrie; // Keep track of the max square length Max = Math.max(Max, Entrie); } } // Print the square System.out.print( "Maximum size sub-matrix is: \n" ); for ( int i = 0 ; i < Max; i++) { for ( int j = 0 ; j < Max; j++) { System.out.print( "1 " ); } System.out.println(); } } // Driver Code public static void main(String[] args) { int M[][] = { { 0 , 1 , 1 , 0 , 1 }, { 1 , 1 , 0 , 1 , 0 }, { 0 , 1 , 1 , 1 , 0 }, { 1 , 1 , 1 , 1 , 0 }, { 1 , 1 , 1 , 1 , 1 }, { 0 , 0 , 0 , 0 , 0 } }; printMaxSubSquare(M); } } // This code is contributed by code_hunt. |
Maximum size sub-matrix is: 1 1 1 1 1 1 1 1 1
Time Complexity: O(m*n) where m is the number of rows and n is the number of columns in the given matrix.
Auxiliary space: O(n) where n is the number of columns in the given matrix.
Please refer complete article on Maximum size square sub-matrix with all 1s for more details!
Contact Us