# Maximal Rectangle
**Difficulty:** HARD
[External](https://leetcode.com/problems/maximal-rectangle)
Canonical: https://scaleengineer.com/dsa/problems/maximal-rectangle
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Data structures:** Array, Stack, Matrix, Monotonic Stack
**Companies:** [Adobe](https://scaleengineer.com/companies/adobe), [Amazon](https://scaleengineer.com/companies/amazon), [Apple](https://scaleengineer.com/companies/apple), [Bloomberg](https://scaleengineer.com/companies/bloomberg), [Flipkart](https://scaleengineer.com/companies/flipkart), [Google](https://scaleengineer.com/companies/google), [Huawei](https://scaleengineer.com/companies/huawei), [Intuit](https://scaleengineer.com/companies/intuit), [Meta](https://scaleengineer.com/companies/meta), [Microsoft](https://scaleengineer.com/companies/microsoft), [Oracle](https://scaleengineer.com/companies/oracle), [TikTok](https://scaleengineer.com/companies/tiktok), [Uber](https://scaleengineer.com/companies/uber), [Yahoo](https://scaleengineer.com/companies/yahoo), [DE Shaw](https://scaleengineer.com/companies/de-shaw)
---
## Problem
Given a `rows x cols` binary `matrix` filled with `0`'s and `1`'s, find the largest rectangle containing only `1`'s and return _its area_.

**Example 1:**

![](https://assets.glich.co/dsa/maximal-rectangle/image0.jpg) 

**Input:** matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
**Output:** 6
**Explanation:** The maximal rectangle is shown in the above picture.

**Example 2:**

**Input:** matrix = [["0"]]
**Output:** 0

**Example 3:**

**Input:** matrix = [["1"]]
**Output:** 1

**Constraints:**

* `rows == matrix.length`
* `cols == matrix[i].length`
* `1 <= row, cols <= 200`
* `matrix[i][j]` is `'0'` or `'1'`.

# Approaches
## Brute Force with Precomputation
This approach iterates through each cell `(i, j)` and considers it as the top-left corner of a potential maximal rectangle. For each such corner, it expands downwards row by row, calculating the maximum possible rectangle area. To optimize the width calculation, it precomputes the number of consecutive '1's to the right for every cell.
**Time:** O(rows^2 * cols) · **Space:** O(rows * cols)
**Pros:** More intuitive and easier to come up with than the most optimal solution.; It's a significant improvement over a naive O(rows^3 * cols^3) brute-force approach.
**Cons:** The time complexity of O(rows^2 * cols) can be too slow for large matrices.; It uses extra space proportional to the size of the matrix, which can be significant.
### Explanation
A brute-force solution would be to check every possible rectangle, which is highly inefficient. We can improve this by fixing the top-left corner and the height of the rectangle and then finding the maximum possible width. 

This approach pre-calculates, for each cell `(i, j)`, the number of consecutive '1's to its right, including itself. Let's call this `width[i][j]`. This precomputation step takes O(rows * cols) time.

After precomputation, the main algorithm iterates through every cell `(i, j)` as a potential top-left corner. For each `(i, j)`, it iterates downwards to every possible bottom row `k`. For a rectangle defined by top-left `(i, j)` and bottom row `k`, the height is `k - i + 1`. The width is limited by the narrowest stretch of '1's starting from column `j` in any row from `i` to `k`. This is equivalent to `min(width[i][j], width[i+1][j], ..., width[k][j])`. We calculate this area and update our global maximum.

```java
class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[][] width = new int[rows][cols];

        // Precompute width of consecutive '1's to the right
        for (int i = 0; i < rows; i++) {
            for (int j = cols - 1; j >= 0; j--) {
                if (matrix[i][j] == '1') {
                    width[i][j] = (j == cols - 1) ? 1 : width[i][j + 1] + 1;
                } else {
                    width[i][j] = 0;
                }
            }
        }

        int maxArea = 0;
        // Iterate through each cell as a potential top-left corner
        for (int i = 0; i < rows; i++) {
            for (int j = 0; j < cols; j++) {
                int minWidth = Integer.MAX_VALUE;
                // Expand downwards
                for (int k = i; k < rows; k++) {
                    // The width of the rectangle is limited by the narrowest row
                    minWidth = Math.min(minWidth, width[k][j]);
                    if (minWidth == 0) break; // No more rectangle possible
                    int height = k - i + 1;
                    maxArea = Math.max(maxArea, minWidth * height);
                }
            }
        }
        return maxArea;
    }
}
```
### Algorithm
- Initialize `maxArea` to 0.
- If the matrix is empty, return 0.
- Get the number of rows and columns.
- Create a 2D integer array `width` of the same dimensions as the input matrix.
- Precompute the `width` array. For each row `i`, iterate from right to left (from `j = cols - 1` to 0):
  - If `matrix[i][j]` is '1', set `width[i][j]` to `1 + width[i][j+1]`. If `j` is the last column, it's just 1.
  - If `matrix[i][j]` is '0', set `width[i][j]` to 0.
- Iterate through each cell `(i, j)` of the matrix, considering it as a potential top-left corner of a rectangle.
- For each `(i, j)`:
  - Initialize `minWidth` to a very large value.
  - Iterate downwards from the current row `k = i` to the last row.
    - Update `minWidth` to be the minimum of its current value and `width[k][j]`. This `minWidth` represents the width of the rectangle that spans from row `i` to `k` starting at column `j`.
    - If `minWidth` becomes 0, it means the rectangle is broken, so we can break the inner loop.
    - Calculate the height of the current rectangle as `k - i + 1`.
    - Calculate the area as `minWidth * height`.
    - Update `maxArea` with the maximum area found so far.
- Return `maxArea`.

## Dynamic Programming with Histogram
This problem can be efficiently solved by reducing it to a series of 'Largest Rectangle in Histogram' problems. We can iterate through the matrix row by row. For each row, we construct a histogram where the height of each bar at column `j` is the number of consecutive '1's above the current cell `(i, j)`, including the cell itself. Then, we find the largest rectangle in this generated histogram. The overall maximum area is the maximum of the areas found for each row's histogram.
**Time:** O(rows * cols) · **Space:** O(cols)
**Pros:** This is the most efficient approach with a time complexity of O(rows * cols).; It has a low space complexity of O(cols).; It cleverly reduces a 2D problem to a well-known 1D problem, which is a common and powerful problem-solving pattern.
**Cons:** The logic for the largest rectangle in a histogram subproblem, particularly the monotonic stack implementation, can be complex to grasp and implement correctly under pressure.
### Explanation
The key insight is to view the 2D matrix as a sequence of 1D histograms. We process the matrix one row at a time, maintaining an array `heights` of the same size as the number of columns.

For each row `i`, we update `heights[j]` as follows:
- If `matrix[i][j] == '1'`, it means the column of '1's at `j` continues, so we do `heights[j]++`.
- If `matrix[i][j] == '0'`, the continuous column of '1's is broken, so we reset `heights[j] = 0`.

After updating the `heights` array for a row, it represents the heights of bars in a histogram. We then solve the 'Largest Rectangle in Histogram' problem for this `heights` array. This subproblem can be solved in O(cols) time using a monotonic stack. The stack helps in efficiently finding the nearest smaller bars to the left and right for each bar, which define the boundaries of the largest rectangle that can be formed with that bar as the height.

By repeating this process for every row and keeping track of the maximum area found, we can determine the maximal rectangle in the entire matrix.

```java
import java.util.Stack;

class Solution {
    public int maximalRectangle(char[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return 0;
        }
        int rows = matrix.length;
        int cols = matrix[0].length;
        int[] heights = new int[cols];
        int maxArea = 0;

        for (int i = 0; i < rows; i++) {
            // Update heights for the current row
            for (int j = 0; j < cols; j++) {
                if (matrix[i][j] == '1') {
                    heights[j]++;
                } else {
                    heights[j] = 0;
                }
            }
            // Calculate max area for the histogram represented by heights
            maxArea = Math.max(maxArea, largestRectangleArea(heights));
        }
        return maxArea;
    }

    private int largestRectangleArea(int[] heights) {
        Stack<Integer> stack = new Stack<>();
        int maxArea = 0;
        int n = heights.length;

        for (int i = 0; i <= n; i++) {
            int h = (i == n) ? 0 : heights[i];
            while (!stack.isEmpty() && heights[stack.peek()] >= h) {
                int height = heights[stack.pop()];
                int width = stack.isEmpty() ? i : i - stack.peek() - 1;
                maxArea = Math.max(maxArea, height * width);
            }
            stack.push(i);
        }
        return maxArea;
    }
}
```
### Algorithm
- Initialize `maxArea` to 0.
- If the matrix is empty, return 0.
- Create a 1D integer array `heights` of size `cols`, initialized to all zeros.
- Iterate through each `row` of the matrix from top to bottom:
  - Update the `heights` array for the current row: For each column `j`, if `matrix[row][j]` is '1', increment `heights[j]`. If it's '0', reset `heights[j]` to 0.
  - After updating, the `heights` array represents a histogram where each bar's height is the number of consecutive '1's ending at the current row.
  - Call a helper function, `largestRectangleInHistogram(heights)`, to find the largest rectangle in this histogram.
  - Update `maxArea = max(maxArea, result from helper function)`.
- After iterating through all rows, return `maxArea`.

**Algorithm for `largestRectangleInHistogram(heights)`:**
- Use a monotonic stack to store indices of the `heights` array.
- Iterate through the `heights` array from left to right (including a virtual bar of height 0 at the end to clear the stack).
- For each bar `i`:
  - While the stack is not empty and the bar at the top of the stack is taller than the current bar `i`:
    - Pop an index from the stack. This is the bar for which we are calculating the maximum area.
    - The height is `heights[popped_index]`.
    - The width is the distance from the current index `i` to the index of the previous smaller bar (the new stack top). If the stack becomes empty, the width extends to the beginning.
    - Update the maximum area found for this histogram.
  - Push the current index `i` onto the stack.

# Solutions
### CSharp

```csharp
using System ; using System.Collections.Generic ; using System.Linq ; public class Solution { private int MaximalRectangleHistagram ( int [] height ) { var stack = new Stack < int >(); var result = 0 ; var i = 0 ; while ( i < height . Length || stack . Any ()) { if (! stack . Any () || ( i < height . Length && height [ stack . Peek ()] < height [ i ])) { stack . Push ( i ); ++ i ; } else { var previousIndex = stack . Pop (); var area = height [ previousIndex ] * ( stack . Any () ? ( i - stack . Peek () - 1 ) : i ); result = Math . Max ( result , area ); } } return result ; } public int MaximalRectangle ( char [][] matrix ) { var lenI = matrix . Length ; var lenJ = lenI == 0 ? 0 : matrix [ 0 ]. Length ; var height = new int [ lenJ ]; var result = 0 ; for ( var i = 0 ; i < lenI ; ++ i ) { for ( var j = 0 ; j < lenJ ; ++ j ) { if ( matrix [ i ][ j ] == '1' ) { ++ height [ j ]; } else { height [ j ] = 0 ; } } result = Math . Max ( result , MaximalRectangleHistagram ( height )); } return result ; } }
```

### Java

```java
import java.util.Arrays ; import java.util.Stack ; public class Solution { public int maximalRectangle ( char [][] m ) { /* original: "0010", "1111", "1111", "0111", "1100", "1111", "1110" */ /* "01101", "11010", "01110", "11110", "11111", "00000", [0, 1, 1, 0, 1], [1, 2, 0, 1, 0], [0, 3, 1, 2, 0], [1, 4, 2, 3, 0], [2, 5, 3, 4, 1], [0, 0, 0, 0, 0]] */ if ( m == null || m . length == 0 ) { return 0 ; } int row = m . length ; int col = m [ 0 ]. length ; // build dp, dp[i][j]就是当前的第j列的，从上面开始到第i行连续1的个数 int [][] dp = new int [ row ][ col ]; // process first row for ( int j = 0 ; j < col ; j ++) { dp [ 0 ][ j ] = m [ 0 ][ j ] - '0' ; } //@note: assumption, at least 2 rows for ( int i = 1 ; i < row ; i ++) { for ( int j = 0 ; j < col ; j ++) { if ( m [ i ][ j ] - '0' != 0 ) { dp [ i ][ j ] = 1 + dp [ i - 1 ][ j ]; } } } if ( m . length == 1 ) { return findRowMax ( dp [ 0 ]); } // search each row of dp array int max = 0 ; for ( int i = 0 ; i < row ; i ++) { int rowMax = findRowMax ( dp [ i ]); max = max > rowMax ? max : rowMax ; } return max ; } public int findRowMax ( int [] rowOriginal ) { int [] row = new int [ rowOriginal . length + 1 ]; row = Arrays . copyOfRange ( rowOriginal , 0 , rowOriginal . length + 1 ); int max = 0 ; int length = row . length ; // stack store index, not the actual value Stack < Integer > sk = new Stack <>(); int i = 0 ; while ( i < length ) { // if (i == 0 || row[i] >= row[sk.peek()]) { if ( sk . isEmpty () || row [ i ] >= row [ sk . peek ()]) { sk . push ( i ); i ++; } else { // while (!sk.isEmpty() && row[i] < row[sk.peek()]) { // int index = sk.pop(); // int prevIndex = sk.isEmpty()? 0 : sk.peek(); // int area = (i - 1 - prevIndex) * row[index]; // i-1 is the highest bar before i // max = max > area ? max : area; // } int index = sk . pop (); // int prevIndex = sk.isEmpty()? 0 : sk.peek(); // int prevIndex = sk.isEmpty() ? i : sk.peek(); // 这里是：高度(row[index]) * 长度 int area = ( sk . isEmpty () ? i : ( i - 1 - sk . peek ())) * row [ index ]; // i-1 is the highest bar before i max = max > area ? max : area ; // sk.push(i++); } } // final check when reaching end of array. OR add dummy number to array end // while (!sk.isEmpty()) { // int index = sk.pop(); // int prevIndex = sk.isEmpty()? 0 : sk.peek(); // int area = (i - 1 - prevIndex) * row[index]; // i-1 is the highest bar before i // max = max > area ? max : area; // } return max ; } } } ############ class Solution { public int maximalRectangle ( char [][] matrix ) { int n = matrix [ 0 ]. length ; int [] heights = new int [ n ]; int ans = 0 ; for ( var row : matrix ) { for ( int j = 0 ; j < n ; ++ j ) { if ( row [ j ] == '1' ) { heights [ j ] += 1 ; } else { heights [ j ] = 0 ; } } ans = Math . max ( ans , largestRectangleArea ( heights )); } return ans ; } private int largestRectangleArea ( int [] heights ) { int res = 0 , n = heights . length ; Deque < Integer > stk = new ArrayDeque <>(); int [] left = new int [ n ]; int [] right = new int [ n ]; Arrays . fill ( right , n ); for ( int i = 0 ; i < n ; ++ i ) { while (! stk . isEmpty () && heights [ stk . peek ()] >= heights [ i ]) { right [ stk . pop ()] = i ; } left [ i ] = stk . isEmpty () ? - 1 : stk . peek (); stk . push ( i ); } for ( int i = 0 ; i < n ; ++ i ) { res = Math . max ( res , heights [ i ] * ( right [ i ] - left [ i ] - 1 )); } return res ; } }
```

### Python

```python
class Solution : def maximalRectangle ( self , matrix : List [ List [ str ]]) -> int : heights = [ 0 ] * len ( matrix [ 0 ]) ans = 0 for row in matrix : for j , v in enumerate ( row ): if v == "1" : heights [ j ] += 1 # inherite from row above else : heights [ j ] = 0 # check for every row ans = max ( ans , self . largestRectangleArea ( heights )) return ans def largestRectangleArea ( self , heights : List [ int ]) -> int : n = len ( heights ) stk = [] left = [ - 1 ] * n right = [ n ] * n for i , h in enumerate ( heights ): while stk and heights [ stk [ - 1 ]] >= h : stk . pop () if stk : left [ i ] = stk [ - 1 ] stk . append ( i ) return max ( h * ( right [ i ] - left [ i ] - 1 ) for i , h in enumerate ( heights )) ############ class Solution ( object ): def maximalRectangle ( self , matrix ): """ :type matrix: List[List[str]] :rtype: int """ def histogram ( height ): if not height : return 0 height . append ( - 1 ) stack = [] ans = 0 for i in range ( 0 , len ( height )): while stack and height [ i ] < height [ stack [ - 1 ]]: h = height [ stack . pop ()] w = i - stack [ - 1 ] - 1 if stack else i ans = max ( ans , h * w ) stack . append ( i ) return ans ans = 0 dp = [[ 0 ] * len ( matrix [ 0 ]) for _ in range ( 0 , len ( matrix ))] for i in reversed ( range ( 0 , len ( matrix ))): if i == len ( matrix ) - 1 : dp [ i ] = [ int ( h ) for h in matrix [ i ]] else : for j in range ( 0 , len ( matrix [ 0 ])): if matrix [ i ][ j ] != "0" : dp [ i ][ j ] = dp [ i + 1 ][ j ] + 1 ans = max ( ans , histogram ( dp [ i ])) return ans
```

### CPP

```cpp
// OJ: https://leetcode.com/problems/maximal-rectangle/ // Time: O(MN) // Space: O(N) class Solution { public: int maximalRectangle ( vector < vector < char >>& A ) { int M = A . size (), N = A [ 0 ]. size (), ans = 0 ; vector < int > h ( N ), nextSmaller ( N ); for ( int i = 0 ; i < M ; ++ i ) { for ( int j = 0 ; j < N ; ++ j ) { h [ j ] = A [ i ][ j ] == '0' ? 0 : ( h [ j ] + 1 ); } stack < int > s ; for ( int j = N - 1 ; j >= 0 ; -- j ) { while ( s . size () && h [ j ] <= h [ s . top ()]) s . pop (); nextSmaller [ j ] = s . size () ? s . top () : N ; s . push ( j ); } s = {}; for ( int j = 0 ; j < N ; ++ j ) { while ( s . size () && h [ j ] <= h [ s . top ()]) s . pop (); int prevSmaller = s . size () ? s . top () : - 1 ; ans = max ( ans , ( nextSmaller [ j ] - prevSmaller - 1 ) * h [ j ]); s . push ( j ); } } return ans ; } };
```