# Maximal Rectangle

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
```

## Analysis

It's not a easy problem, yet if you've done **"Largest Rectangle in Histogram"**, one approach is convert to that problem for each row, and get "largest rectangle in histogram" for each row, and compare each row's "largest rectangle" to get maximal rectangle in the matrix.

For example:

Original matrix\[]\[]

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

convert to =>

heights\[]\[] matrix

```
[
  [1, 0, 1, 0, 0],
  [2, 0, 2, 1, 1],
  [3, 1, 3, 2, 2],
  [4, 0, 0, 3, 0]
]
```

That for `heights[i][j]` it stands for, for `i-th` row, the height at column `j`, thus each row in `heights[i][j]` could just be input\
for the function `int largestRectangleArea(int[] heights)`.

At this moment, the **"Maximal Rectangle"** problem has been converted to a series of **"Largest Rectangle in Histogram"** problem.

`O(n\*m)` time, `O(n\*m)` space

## Solution

Convert to Largest Rectangle in Histogram problem (where **DP** is used) - 13 ms, faster than 70.66%

```java
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) return 0;
        int rowLength = matrix.length;
        int colLength = matrix[0].length;
        int[][] heights = new int[rowLength][colLength];
        for (int i = 0 ; i < rowLength; i++) {
            for (int j = 0; j < colLength; j++) {
                if (matrix[i][j] == '1') {
                    if (i == 0) heights[i][j] = 1;
                    if (i > 0) heights[i][j] = heights[i-1][j] + 1;
                } else {
                    heights[i][j] = 0;
                }
            }
        }
        int max = 0;
        for (int[] hs : heights) {
            max = Math.max(max, largestRectangleArea(hs));
        }
        return max;
    }

    public int largestRectangleArea(int[] heights) {
        if (heights == null || heights.length == 0) {
            return 0;
        }
        if (heights.length == 1) {
            return heights[0];
        }
        int maxArea = 0;
        int[] leftBound = new int[heights.length];
        int[] rightBound = new int[heights.length];
        leftBound[0] = -1;
        rightBound[heights.length - 1] = heights.length;

        for (int i = 1; i < heights.length; i++) {
            int l = i - 1;
            while (l >= 0 && heights[l] >= heights[i]) {
                l = leftBound[l];
            }
            leftBound[i] = l;
        }
        for (int i = heights.length - 2; i >= 0; i--) {
            int r = i + 1;
            while (r < heights.length && heights[r] >= heights[i]) {
                r = rightBound[r];
            }
            rightBound[i] = r;
        }

        for (int i = 0; i< heights.length; i++) {
            maxArea = Math.max(heights[i] * (rightBound[i] - leftBound[i] - 1), maxArea);
        }
        return maxArea;
    } 
}
```

Convert to largest rectangle histogram (where monotonous **stack** is used) - (35 ms AC)

```java
class Solution {

    // O(n*m)
    public int maximalRectangle(char[][] matrix) {
        if(matrix.length==0) return 0;
        int[] heights = new int[matrix[0].length];
        int maxArea=-1;
        for(int i=0; i<matrix.length; i++){
            for(int j=0; j<matrix[0].length; j++){
                // if (matrix[i][j] == '0') heights[j] = 0;
                // else heights[j]++;
                if (matrix[i][j] == '1') heights[j]++;
                else heights[j] = 0;
            }            
            int area = largestRectangleArea(heights);
            maxArea = Math.max(maxArea, area);
        }
        return maxArea;
    }

    // O(n)
    public int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        stack.push(-1);
        int maxarea = 0;
        for (int i = 0; i < heights.length; i++) {
            while (stack.peek() != -1 && heights[stack.peek()] >= heights[i])
                maxarea = Math.max(maxarea, heights[stack.pop()] * (i - stack.peek() - 1));
            stack.push(i);
        }
        while (stack.peek() != -1)
            maxarea = Math.max(maxarea, heights[stack.pop()] * (heights.length - stack.peek() -1));
        return maxarea;
    }
}
```

Combining largestRectangleArea function into the same loop - using stack

```java
public class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix==null||matrix.length==0||matrix[0].length==0)
            return 0;
        int cLen = matrix[0].length;    // column length
        int rLen = matrix.length;       // row length
        // height array 
        int[] h = new int[cLen+1];
        h[cLen]=0;
        int max = 0;


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

                if (s.isEmpty()||h[s.peek()]<=h[i])
                    s.push(i);
                else {
                    while(!s.isEmpty()&&h[i]<h[s.peek()]){
                        int top = s.pop();
                        int area = h[top]*(s.isEmpty()?i:(i-s.peek()-1));
                        if (area>max)
                            max = area;
                    }
                    s.push(i);
                }
            }
        }
        return max;
    }
}
```

Another combined implementation - using Stack - (35 ms, faster than 37.38% )

```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()]) {
                    max = Math.max(max, h[s.pop()] * (i - s.peek() - 1));
                }
                s.push(i);
            }
        }
        return max;
    }
}
```

## Reference

* [LeetCode: O(n^2) solution based on largest rectangle in histogram](https://leetcode.com/problems/maximal-rectangle/discuss/29064/A-O%28n2%29-solution-based-on-Largest-Rectangle-in-Histogram)


---

# 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/dynamic_programming/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.