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.

Example:

1  1  0  0  1  0
0  1  1  1  1  1
1  1  1  1  1  0
0  0  1  1  0  0
Largest all 1s sub-matrix is from (1,1) to (2,4).
1  1  1  1
1  1  1  1
Algorithm: If we draw a histogram of all 1’s cells in above rows (until we find a 0) for a particular row, then maximum all 1s sub-matrix ending in that row will the equal to maximum area rectangle in that histogram. Below is the example for 3rd row in above discussed matrix:

If we calculate this area for all the rows, maximum area will be our answer. We can extend our solution very easily to find start and end co-ordinates.

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:
1  1  0  0  1  0
0  2  1  1  2  1
1  3  2  2  3  0
0  0  3  3  0  0
Now we can simple call our maximum rectangle in histogram on every row in S[][] and update the maximum area every time.

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++)
     {
         if(A[i][j])
             A[i][j] = A[i][j] - A[i-1][j];
     }

 return cur_max;
}

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.