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:**

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

**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:

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++)

{

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.
atomThis will fail for the below matrix :

1 1 0 0

0 0 1 1

1 1 1 1

1 1 1 1

Akash@atom: How is it failing, I am getting 8 for given input.

atom@akash: For the above matrix, according to you the cummulative matrix would be:

1 1 0 0

1 1 1 1

2 2 2 2

3 3 3 3

according to this maximum rectangle would be in the 4th row with all 3's and hence your answer would be 12 instead of 8.

Akash@Atom: As I have written "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."

According to above, the cummulative matrix would be:

1 1 0 0

0 0 1 1

1 1 2 2

2 2 3 3

harishiyer-rnsmAwesome Solution

Akash@harishiyer-rnsm: thanks :)

Abhi@Akash can u plz tell how to get upper left and bottom right co-ordinates of maximum area rectangle. ?

AnonymousThe space complexity is not O(1). The largestArea() function requires a stack that can get as large as the number of columns. So the space complexity is O(m).