Largest rectangle of 1’s or 0’s.

Given a 2D array of 1 and 0, Find the largest rectangle of 1’s or 0’s ie. rectangle (may not be square) which is made up of all 1’s or 0’s.

For example,

A =   0 1 1 0 1
      1 0 1 1 0
      1 0 1 1 1 

Then the largest rectangle is the 2X2 rectangle with top-left corner at (1, 2).

How do we solve it?
We can transform this problem into a set of Maximum Area Rectangle in a histogram sub-problems, one for each row. We will convert each of the row into a histogram such that the height of the bars is equal to the consecutive no of 1’s above it. For example,

A =   0 1 1 0 1            |    _
      1 0 2 1 0            |_  | |_
      2 0 3 2 1            | | | | |_  
                           |_|_|_|_|_|___
                            2 0 3 2 1

Now, apply Maximum histogram rectangle area problem for each of the n rows and then find the maximum of all the n row-histogram max-rectangle area. I have discussed in a separate post about how to solve the Maximum Area Rectangle in a histogram problem. Following is the code for this problem using the solution of maximum area rectangle in a histogram. Overall complexity is minimal O(n^2).

public int maxRectangleOf1s(final int A[][]) {
    int maxArea = 0;
    final int n = A.length;
    final int m = A[0].length;
    final int histograms[][] = new int[n][m];
    // convert each of the row into a histogram such that the height of the bars is equal to the consecutive no of
    // 1's above.
    // first intialize the top row with the input array
    for (int j = 0; j < m; j++) {
        histograms[0][j] = A[0][j] == 1 ? 1 : 0;
    }

    // now compute the histograms.
    for (int i = 1; i < n; i++) {
        for (int j = 0; j < m; j++) {
            histograms[i][j] = A[i][j] == 1 ? histograms[i - 1][j] + A[i][j] : 0;
        }
    }

    // now we have total n histograms, one for each row. Calculate the max area rectangle for each of this
    // histogram.
    for (int i = 0; i < n; i++) {
        maxArea = Math.max(maxArea, maxAreaRectangleHistogram(histograms[i]));
    }

    return maxArea;
}