Maximal Rectangle

Hard Monotonic Stack Monotonic Stack Original on LeetCode

Maximal Rectangle is a hard monotonic stack problem solved with the monotonic stack pattern. The best approach, optimal (histogram per row + monotonic stack), runs in O(rows · cols) time and O(cols) space. Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (row run lengths, scan upward) up.

Problem

You are given a rows x cols binary matrix filled with the characters '0' and '1'. Find the largest axis-aligned rectangle that contains only '1' cells and return its area (the number of cells inside it).

Examples

Example 1

Input
matrix = [["1","1","0","1"],["1","1","1","1"],["0","1","1","1"],["0","1","1","0"]]
Output
6
Why
Rows 1 to 3 in columns 1 and 2 form a 3 x 2 block of ones (rows 1 to 2 in columns 1 to 3 is another one of area 6).

Example 2

Input
matrix = [["0"]]
Output
0
Why
There is no 1 at all.

Example 3

Input
matrix = [["1","0","1","1","1"]]
Output
3
Why
With a single row the answer is the longest run of ones.

Constraints

  • 1 <= rows, cols <= 200
  • matrix[i][j] is '0' or '1'.

Solve it here

Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.

00:00
Testcase

Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.

Solutions

Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.

ApproachTimeSpace
Brute force (row run lengths, scan upward)O(rows² · cols)O(rows · cols)
Optimal (histogram per row + monotonic stack)O(rows · cols)O(cols)

1Brute force (row run lengths, scan upward)

TimeO(rows² · cols)For each of the rows · cols cells, the upward scan can visit every row.
SpaceO(rows · cols)The run-length table w.

Let w[i][j] be the number of consecutive ones in row i ending at column j. Treat each cell as the bottom-right corner and walk upward row by row: the rectangle that spans rows k..i can be at most min(w[k..i][j]) wide. Track the best width × height.

  1. Compute w[i][j] = matrix[i][j] == '1' ? w[i][j - 1] + 1 : 0.
  2. For each cell (i, j) with w[i][j] > 0: minW = infinity; for k from i up to 0: minW = min(minW, w[k][j]); stop if 0; best = max(best, minW × (i - k + 1)).
  3. Return best.
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[][] w = new int[m][n];
        for (int i = 0; i < m; i++)
            for (int j = 0; j < n; j++)
                if (matrix[i][j] == '1') w[i][j] = (j > 0 ? w[i][j - 1] : 0) + 1;
        int best = 0;
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                int minW = Integer.MAX_VALUE;
                for (int k = i; k >= 0 && w[k][j] > 0; k--) {
                    minW = Math.min(minW, w[k][j]);
                    best = Math.max(best, minW * (i - k + 1));
                }
            }
        }
        return best;
    }
}

2Optimal (histogram per row + monotonic stack)

TimeO(rows · cols)Each row updates the histogram in O(cols), and every column index is pushed and popped once per row.
SpaceO(cols)The histogram and the stack each hold up to cols entries.

Keep h[j] = number of consecutive ones ending at the current row in column j. Each row turns the matrix into a histogram, and the largest rectangle whose bottom edge lies on this row is the largest rectangle in that histogram. Solve it with an increasing stack of column indices: when a lower bar arrives, pop taller bars and measure the rectangle each one can span.

  1. For each row: h[j] = matrix[i][j] == '1' ? h[j] + 1 : 0.
  2. Scan j = 0..n with a sentinel height 0 at j = n. While the stack top is taller than the current height, pop it as height H; width = j if the stack is now empty, else j - stack.top - 1; update best with H × width.
  3. Push j and continue. Return best after the last row.
class Solution {
    public int maximalRectangle(char[][] matrix) {
        int m = matrix.length, n = matrix[0].length;
        int[] h = new int[n];
        int best = 0;
        int[] stack = new int[n + 1];
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) h[j] = matrix[i][j] == '1' ? h[j] + 1 : 0;
            int top = -1;
            for (int j = 0; j <= n; j++) {
                int cur = j == n ? 0 : h[j];
                while (top >= 0 && h[stack[top]] > cur) {
                    int height = h[stack[top--]];
                    int width = top < 0 ? j : j - stack[top] - 1;
                    best = Math.max(best, height * width);
                }
                stack[++top] = j;
            }
        }
        return best;
    }
}

Edge cases to test

  • All zeros (answer 0)
  • All ones (answer rows × cols)
  • A single row or a single column
  • A tall thin rectangle beating a short wide one, and the other way round

Hints

Hint 1

Fix the bottom row of the rectangle. For each column, how many consecutive ones end at that row?

Hint 2

Those counts form a histogram. The best rectangle with this bottom row is the largest rectangle in that histogram.

Hint 3

Update the histogram row by row in O(cols) and solve each one with a monotonic stack.

FAQ

What is the best time complexity for Maximal Rectangle?

Optimal (histogram per row + monotonic stack) runs in O(rows · cols) time and O(cols) extra space. Each row updates the histogram in O(cols), and every column index is pushed and popped once per row.

Which pattern does Maximal Rectangle use?

It is a monotonic stack problem that uses the monotonic stack pattern. Other problems with the same pattern: Next Greater Element I, Daily Temperatures, Next Greater Element II.

Is there a brute force solution for Maximal Rectangle?

Yes. Brute force (row run lengths, scan upward) takes O(rows² · cols) time and O(rows · cols) space. Let w[i][j] be the number of consecutive ones in row i ending at column j.

Which edge cases should I test for Maximal Rectangle?

All zeros (answer 0); All ones (answer rows × cols); A single row or a single column; A tall thin rectangle beating a short wide one, and the other way round.