# Leetcode – Maximal Rectangle solution 1 (Java)

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. 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 = 2`,  we want to build a rectangle with `height == 2`,  so we expand to the left.  It turns out that `ones = 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`, 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.