In last post, we saw a dynamic programming approach to for finding maximum size square sub-matrix with all 1s. In this post, we will discuss how to find largest all 1s sub-matrix in a binary matrix. The resultant sub-matrix is not necessarily a square sub-matrix.
Largest all 1s sub-matrix is from (1,1) to (2,4).1 1 0 0 1 00 1 1 1 1 11 1 1 1 1 00 0 1 1 0 0
1 1 1 11 1 1 1
For above purpose, we need to generate an auxiliary matrix S where each element represents the number of 1s above and including it, up until the first 0. S for above matrix will be as shown below:
Now we can simple call our maximum rectangle in histogram on every row in S and update the maximum area every time.1 1 0 0 1 00 2 1 1 2 11 3 2 2 3 00 0 3 3 0 0
Also we don’t need any extra space for saving S. We can update original matrix (A) to S and after calculation, we can convert S back to A.
Code: I am not writing the code for largestArea() function. One can find its definition in this post.
#define ROW 10
#define COL 10
int find_max_matrix(int A[ROW][COL])
int i, j;
int max, cur_max;
cur_max = 0;
//Calculate Auxilary matrix
for (i=1; i<ROW; i++)
for(j=0; j<COL; j++)
if(A[i][j] == 1)
A[i][j] = A[i-1][j] + 1;
//Calculate maximum area in S for each row
for (i=0; i<ROW; i++)
max = largestArea(A[i], COL);
if (max > cur_max)
cur_max = max;
//Regenerate Oriignal matrix
for (i=ROW-1; i>0; i--)
for(j=0; j<COL; j++)
A[i][j] = A[i][j] - A[i-1][j];
Complexity: Lets say that total number of rows and columns in A are m and n respectively and N = m*n
Complexity of calculating S = O(m*n) = O(N)
Complexity of LargestArea() for every row = O(n) since there are n elements in every row. Since we called LargestArea() m times so total complexity of calculating largest area = O(m*n) = O(N)
Complexity of converting S to A = O(m*n) = O(N)
So total time complexity = O(N)
Since we are not using any extra space, so space complexity is O(1).
Note: Above function only returns largest area, which can be very easily modified to get start and row indexes as well.
Subscribe - To get an automatic feed of all future posts subscribe here, or to receive them via email go here and enter your email address in the box. You can also like us on facebook and follow me on Twitter @akashag1001.