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  00  1  1  1  1  11  1  1  1  1  00  0  1  1  0  0`
Largest all 1s sub-matrix is from (1,1) to (2,4).
`1  1  1  11  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  00  2  1  1  2  11  3  2  2  3  00  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 10int 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.