# Maximal Rectangle

`Stack`, `Dynamic Programming`, `Array`, `Hash Table`

**Hard**

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

**Example:**

```
Input:
[
  ["1","0","1","0","0"],
  ["1","0","1","1","1"],
  ["1","1","1","1","1"],
  ["1","0","0","1","0"]
]
Output: 6
```

## Solution & Analysis

Via @[wangyushawn](https://leetcode.com/wangyushawn)'s, @calis's [answer](https://leetcode.com/problems/maximal-rectangle/discuss/29064/A-O%28n2%29-solution-based-on-Largest-Rectangle-in-Histogram)

### This question is similar as [\[Largest Rectangle in Histogram\]](http://oj.leetcode.com/problems/largest-rectangle-in-histogram/):

You can maintain a row length of Integer array H recorded its height of '1's, and scan and update row by row to find out the largest rectangle of each row.

For each row, if `matrix[row][i] == '1'`. `H[i] +=1`, or reset the `H[i]` to zero.\
and accroding the algorithm of \[**Largest Rectangle in Histogram**], to update the maximum area.

```java
class Solution {
    public int maximalRectangle(char[][] matrix) {
       int rLen = matrix.length, cLen = rLen == 0 ? 0 : matrix[0].length, max = 0;
        int[] h = new int[cLen+1];

        for (int row = 0; row < rLen; row++) {
            Stack<Integer> s = new Stack<Integer>();
            s.push(-1);
            for (int i = 0; i <= cLen ;i++) {
                if(i < cLen && matrix[row][i] == '1')
                    h[i] += 1;
                else h[i] = 0;

                while(s.peek() != -1 && h[i] < h[s.peek()]) {
                    int height = h[s.pop()];
                    int width = i - s.peek() - 1;
                    max = Math.max(max, height * width);
                }
                s.push(i);
            }
        }
        return max;
    }
}
```

See also: [Solution based on Maximum Rectangle in Histogram](/lintcode/stack/maximal-rectangle.md)

#### Two Pass

by @[agritsik](https://leetcode.com/agritsik)

```java
class Solution {

    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0) return 0;

        int[][] dp = new int[matrix.length][matrix[0].length];
        for (int i = 0; i < dp.length; i++) {
            for (int j = 0; j < dp[0].length; j++) {
                dp[i][j] = matrix[i][j]-'0';
                if (dp[i][j] > 0 && i>0) dp[i][j] += dp[i - 1][j];
            }
        }

        int max = 0;
        for (int[] a : dp) max=Math.max(largestRectangleArea(a), max);

        return max;
    }

    // copied "Largest Rectangle in Histogram" solution
    public int largestRectangleArea(int[] a) {
        LinkedList<Integer> stack = new LinkedList<>();
        int max = 0;

        for (int i = 0; i <= a.length; i++) {
            while (!stack.isEmpty() && (i == a.length || a[stack.peek()] > a[i])) {
                int height = a[stack.pop()];
                int width = (!stack.isEmpty()) ? i - stack.peek() - 1 : i;
                max = Math.max(max, height * width);
            }

            stack.push(i);

        }

        return max;
    }
}
```

### Dynamic Programming

Via [@morrischen2008](https://leetcode.com/morrischen2008)'s [**answer**](https://leetcode.com/problems/maximal-rectangle/discuss/29054/Share-my-DP-solution):

The DP solution proceeds row by row, starting from the first row. Let the maximal rectangle area at row `i` and column `j` be computed by `[right(i,j) - left(i,j)]*height(i,j)`.

All the 3 variables left, right, and height can be determined by the information from previous row, and also information from the current row. So it can be regarded as a DP solution. The **transition equations** are:

> left(i,j) = max(left(i-1,j), cur\_left), cur\_left can be determined from the current row
>
> right(i,j) = min(right(i-1,j), cur\_right), cur\_right can be determined from the current row
>
> height(i,j) = height(i-1,j) + 1, if matrix\[i]\[j]=='1';
>
> height(i,j) = 0, if matrix\[i]\[j]=='0'

\-------@[wahcheung](https://leetcode.com/wahcheung)--------

```
[
   ["1","0","1","0","0"],
   ["1","0","1","1","1"],
   ["1","1","1","1","1"],
   ["1","0","0","1","0"]
 ]
```

策略: 把matrix看成多个直方图, 每一行及其上方的数据都构成一个直方图, 需要考察matrix.size()个直方图

* 对于每个点(row, col), 我们最后都计算以这个点上方的连续的'1'往left, right方向延申可以得到的最大的矩形的面积
* 通过这种方法获取的矩形一定会把最大的矩形包含在内
* height\[row]\[col]记录的是(row, col)这个坐标为底座的直方图柱子的高度, 如果这个点是'0', 那么高度当然是0了
* left\[row]\[col]记录的是(row, col)这个坐标点对应的height可以延申到的最左边的位置
* right\[row]\[col]记录的是(row, col)这个坐标点对应的height可以延申到的最右边的位置+1

以上面的matrix为例,

* 对于(row=2, col=1)这个点, left=0, right=5, height=1
* 对于(row=2, col=2)这个点, left=2, right=3, height=3
* (2,2)这个点与(2,1)紧挨着,left和right却已经变化如此之大了, 这是因为left和right除了受左右两边的'1'影响, 还受到了其上方连续的'1'的制约
* 由于点(2,2)上有height=3个'1', 这几个'1'的left的最大值作为当前点的left, 这几个'1'的right的最小值作为当前点的right

因此, 实际上, 我们是要找以height对应的这条线段往左右两边移动(只能往全是'1'的地方移动), 可以扫过的最大面积。

当height与目标最大矩形区域的最短的height重合时, 最大矩形的面积就找到了, 如上面的例子, 就是点(2,3)或(2,4)对应的height

\--

Code by @[Self\_Learner](https://leetcode.com/self_learner)

```java
/* we start from the first row, and move downward;
 * height[i] record the current number of countinous '1' in column i;
 * left[i] record the left most index j which satisfies that for any index k from j to  i, height[k] >= height[i];
 * right[i] record the right most index j which satifies that for any index k from i to  j, height[k] >= height[i];
 * by understanding the definition, we can easily figure out we need to update maxArea with value (height[i] * (right[i] - left[i] + 1));
 * 
 * Then the question is how to update the array of height, left, and right
 * =================================
 * for updating height, it is easy
 * for (int j = 0; j < n; j++) {
 *    if (matrix[i][j] == '1') height[j]++;
 *    else height[j] = 0;
 * }
 * =============================================================================
 * It is a little bit tricky for initializing and updating left and right array
 * for initialization: 
 * we know initially, height array contains all 0, so according to the definition of left and right array, left array should contains all 0, and right array should contain all n - 1
 * for updating left and right, it is kind of tricky to understand...
 *     ==============================================================
 *     Here is the code for updating left array, we scan from left to right
 *     int lB = 0;  //lB is indicating the left boundry for the current row of the matrix (for cells with char "1"), not the height array...
 *     for (int j = 0; j < n; j++) {
 *          if (matrix[i][j] == '1') {
 *              left[j] = Math.max(left[j], lB); // this means the current boundry should satisfy two conditions: within the boundry of the previous height array, and within the boundry of the current row...
 *          } else {
 *              left[j] = 0; // when matrix[i][j] = 0, height[j] will get update to 0, so left[j] becomes 0, since all height in between 0 - j satisfies the condition of height[k] >= height[j];
 *              lB = j + 1; //and since current position is '0', so the left most boundry for next "1" cell is at least j + 1;
 *          }
 *     }
 *     ==============================================================
 *     the idea for updating the right boundary is similar, we just need to iterate from right to left
 *     int rB = n - 1;
 *     for (int j = n - 1; j >= 0; j--) {
 *         if (matrix[i][j] == '1') {
 *              right[j] = Math.min(right[j], rB);
 *         } else {
 *              right[j] = n - 1;
 *              rB = j - 1;
 *      }
 */
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0] == null || matrix[0].length == 0) return 0;
        int m = matrix.length, n = matrix[0].length, maxArea = 0;
        int[] left = new int[n];
        int[] right = new int[n];
        int[] height = new int[n];
        Arrays.fill(right, n - 1);
        for (int i = 0; i < m; i++) {
            int rB = n - 1;
            for (int j = n - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    right[j] = Math.min(right[j], rB);
                } else {
                    right[j] = n - 1;
                    rB = j - 1;
                }
            }
            int lB = 0;
            for (int j = 0; j < n; j++) {
                if (matrix[i][j] == '1') {
                    left[j] = Math.max(left[j], lB);
                    height[j]++;
                    maxArea = Math.max(maxArea, height[j] * (right[j] - left[j] + 1));
                } else {
                    height[j] = 0;
                    left[j] = 0;
                    lB = j + 1;
                }
            }
        }
        return maxArea;
    }
}
```


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://aaronice.gitbook.io/lintcode/stack/maximal-rectangle.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.