Leetcode – Maximal Rectangle solution 1 (Java)

Tags: , , ,

Maximum Rectangle area for a 0 1 matrix.

Given a 2D binary matrix filled with 0’s and 1’s, find the largest rectangle containing all ones and return its area.

Source: https://leetcode.com/problems/maximal-rectangle/
 
This is a hard one from Facebook.
 
The key to solve this problem is to first build a matrix ones[][], where ones[i][j] means the number of continuous 1s to the cell matrix[i][j] in jth column. See the following figure. 
 
 
 leetcode maximal rectangle
 
 
We have:

We can fill up the matrix ones[][] using dynamic programming. The formula is :

How to use the ones[][] matrix to calculate the maximum area? From the figure, we know that each row of the new matrix ones[][] actually denotes a histogram. So this problem can be converted to the Largest Rectangle in Histogram Problem. 

For the Largest Rectangle in Histogram Problem, there is a O(n) method based on stack.  It might be hard to come up with this optimal solution in an interview. Here I describe an easier to understand method. 

The idea is to calculate the largest area with the height of ones[i][j] for each position at row i, column j. 
For example, suppose we stand on the cell[i][j],  ones[i][j] is the current height.  Then we expand to the left and right until the height is less than the current height. 
For example, in the above figure, ones[3][2] = 2,  we want to build a rectangle with height == 2,  so we expand to the left.  It turns out that ones[3][1] = 0, that means the left area can not be used to form such a rectangle with height == 2. Then we expand to the right, as ones[3][3] == 3, we know the right part can be used to form this rectangle. So with height == 2,  2 is the maximal width to build a rectangle. The corresponding area is 4. 

The following is the implementation for the expanding algorithm:

The complemented implementation is as follows:

Please be noted that, the algorithm described here to calculate the largest rectangle in a histogram is not efficient. The time complexity is O(n^2).  Here is a faster algorithm to solve the histogram problem.