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](http://tech-queries.blogspot.com/2011/03/maximum-area-rectangle-in-histogram.html). Below is the example for 3rd row in above discussed matrix:
[](http://4.bp.blogspot.com/-c0LK1_QSJLA/TwCj0RJx6JI/AAAAAAAAQ5s/FRuDL4pmic8/s1600/matrix_max_1.png)
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
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](http://k2code.blogspot.com/2012/01/maximum-area-rectangle-in-histogram.html).
#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.