Find Largest Sub-Matrix With All 1s (Not Necessarily Square)

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.