C Program for Maximum size square sub-matrix with all 1s
Write a C 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:
C
// C code for Maximum size square // sub-matrix with all 1s #include <stdio.h> #define bool int #define R 6 #define C 5 void printMaxSubSquare( bool M[R][C]) { int i, j; int S[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] = min(S[i][j - 1], 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; } } } printf ( "Maximum size sub-matrix is: \n" ); for (i = max_i; i > max_i - max_of_s; i--) { for (j = max_j; j > max_j - max_of_s; j--) { printf ( "%d " , M[i][j]); } printf ( "\n" ); } } /* UTILITY FUNCTIONS */ /* Function to get minimum of three values */ int min( int a, int b, int c) { int m = a; if (m > b) m = b; if (m > c) m = c; return m; } /* Driver function to test above functions */ int main() { bool M[R][C] = { { 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); getchar (); } |
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.
C 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:
C
#include <stdio.h> #include <stdbool.h> #define R 6 #define C 5 void printMaxSubSquare( bool M[R][C]) { int S[2][C]; int 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 entry at the current position int Entrie = M[i][j]; if (Entrie) { if (j) Entrie = 1 + ((S[1][j - 1] < S[0][j - 1]) ? ((S[1][j - 1] < S[1][j]) ? S[1][j - 1] : S[1][j]) : ((S[0][j - 1] < S[1][j]) ? S[0][j - 1] : S[1][j])); } // Save the last entry and add the new one S[0][j] = S[1][j]; S[1][j] = Entrie; // Keep track of the max square length Max = (Entrie > Max) ? Entrie : Max; } // Print the square printf ( "Maximum size sub-matrix is: \n" ); for ( int i = 0; i < Max; i++) { for ( int j = 0; j < Max; j++) printf ( "1 " ); printf ( "\n" ); } } int main() { bool M[R][C] = {{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); return 0; } |
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!