Question: Given a matrix consisting only 0s and 1s, find the maximum size square sub-matrix with all 1s.
Example: Consider the below matrix.
This is a classic Dynamic Programming problem. Lets calculate the maximum size square sub-matrix as we traverse the original matrix M[][]. We will use a auxiliary matrix S[][] of same size for memoization. S[i][j] represents size of the square sub-matrix with all 1s including M[i][j]. 'i' and 'j' will be the last row and column respectively in square sub-matrix.
How to calculate S[i][j]:
(1) First copy the first row and first column as it is from M[][] to S[][]
(2) And for the remaining entries as mentioned do the following:
We should note that if M[i][j] is '0' then S[i][j] will obviously be '0'. If M[i][j] is '1' then S[i][j] depends on earlier values.
If M[i][j] is '1' then it will contribute to the all 1s square sub-matrix ending at either M[i][j-1] or M[i-1][j] or M[i-1][j-1]. If we visualize the conditions then, we will see:
So to sum up:
(3) Find the maximum entry in S[][] and use it to construct the maximum size square sub-matrix.
Example - How did we arrive at above relationship?
Note if we include M[i][j] in earlier calculated sub-matrix then we are adding S[i][j] elements from ith row and jth columns. They all should be '1' if we wanna include M[i][j]. On visualizing with some examples, readers will analyze why, minimum of 3 neighbors is taken.
For the given M[][] in above example, constructed S[][] would be:
Complexity:
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Space Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Example: Consider the below matrix.
The maximum square sub-matrix with all '1' bits is from (2,1) to (4,3)0 1 1 0 11 1 0 1 00 1 1 1 01 1 1 1 01 1 1 1 10 0 0 0 0
Answer:1 1 11 1 11 1 1
This is a classic Dynamic Programming problem. Lets calculate the maximum size square sub-matrix as we traverse the original matrix M[][]. We will use a auxiliary matrix S[][] of same size for memoization. S[i][j] represents size of the square sub-matrix with all 1s including M[i][j]. 'i' and 'j' will be the last row and column respectively in square sub-matrix.
How to calculate S[i][j]:
(1) First copy the first row and first column as it is from M[][] to S[][]
(2) And for the remaining entries as mentioned do the following:
We should note that if M[i][j] is '0' then S[i][j] will obviously be '0'. If M[i][j] is '1' then S[i][j] depends on earlier values.
If M[i][j] is '1' then it will contribute to the all 1s square sub-matrix ending at either M[i][j-1] or M[i-1][j] or M[i-1][j-1]. If we visualize the conditions then, we will see:
S[i][j] = min(S[i][j-1], S[i-1][j], S[i-1][j-1]) + 1
So to sum up:
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*/ S[i][j] = 0
(3) Find the maximum entry in S[][] and use it to construct the maximum size square sub-matrix.
Example - How did we arrive at above relationship?
Note if we include M[i][j] in earlier calculated sub-matrix then we are adding S[i][j] elements from ith row and jth columns. They all should be '1' if we wanna include M[i][j]. On visualizing with some examples, readers will analyze why, minimum of 3 neighbors is taken.
For the given M[][] in above example, constructed S[][] would be:
The value of maximum entry in above matrix is 3 and coordinates of the entry are (4, 3). Using the maximum value and its coordinates, we can find out the required sub-matrix.0 1 1 0 11 1 0 1 00 1 1 1 01 1 2 2 01 2 2 3 10 0 0 0 0
#define ROW 10 #define COL 10 void FindMaxSubSquare(bool M[ROW][COL], int &max_i,
int &max_j, int &size) { int i,j; int S[ROW][COL]; /* Set first column of S[][]*/ for(i = 0; i < ROW; i++) S[i][0] = M[i][0]; /* Set first row of S[][]*/ for(j = 0; j < COL; j++) S[0][j] = M[0][j]; /* Construct other entries of S[][]*/ for(i = 1; i < ROW; i++) { for(j = 1; j < COL; 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[][] */ size = S[0][0]; max_i = 0; max_j = 0; for(i = 0; i < ROW; i++) { for(j = 0; j < COL; j++) { if(size < S[i][j]) { size = S[i][j]; max_i = i; max_j = j; } } } return }
Complexity:
Time Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
Space Complexity: O(m*n) where m is number of rows and n is number of columns in the given matrix.
0 comments:
Post a Comment