85. Maximal Rectangle

HardMonotonic Stack and Monotonic QueueMonotonic increasing stack over per-row histogramsRow-by-row histogram reduction

Maximal Rectangle

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

Open official problem prompt ↗

In plain English

Find the biggest solid block of 1's anywhere in the grid, measured by area.

Picture it like this

Stack transparent sheets one row at a time. On each new sheet, a column of 1's grows taller wherever the ground below is also 1; a 0 knocks that tower flat. The biggest shadow the towers cast on any single sheet is the answer.

Example

Input: matrix = [["1","0","1","0","0"],["1","0","1","1","1"],["1","1","1","1","1"],["1","0","0","1","0"]]
Output: 6
Why: The block of 1's spanning columns 2-4 across rows 1-2 (and the reinforcing row 3 columns 2-3) yields a 2 x 3 rectangle of area 6.

Constraints

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

Pattern lesson

See the pattern, then code

Row-by-row histogram reduction

↗

Monotonic Stack and Monotonic Queue

Next greater or smaller value, nearest boundary, histogram, or window extremum.. For each row, build a histogram where each column's height is the number of consecutive 1's ending at that row. The tallest rectangle anchored on this row equals the largest histogram rectangle, so solving problem 84 per row and taking the max solves everything.

New words, made simpleKnow these before the algorithm

Reduction: Rewriting a new problem as an already-solved one; here the grid reduces to a sequence of histogram problems.
Prefix column height: The count of consecutive 1's in a column ending at the current row, which becomes the histogram bar height.

Approaches from first idea to best ideaCompare the trade-offs

ApproachHow it thinksCost

Enumerate all rectangles

Far too slow even for a 200 x 200 grid.

Try every top-left and bottom-right corner and verify it is all 1's.

Time O((rows x cols)^2)Space O(1)

Best choicePer-row histogram + monotonic stack

Linear in the grid size and clean to implement.

Maintain column heights, run largest-rectangle-in-histogram for each row.

Time O(rows x cols)Space O(cols)

The rule we keep true

Invariant

After processing a row, heights[j] equals the number of unbroken 1's in column j ending at that row, so any rectangle resting on this row is captured by the histogram.

Why this is correct

Reasoning

Every all-ones rectangle has a bottom row somewhere. When we process that bottom row, the heights array exactly measures how far up the solid 1's extend in each column, so the largest histogram rectangle on that row includes this rectangle. Taking the max over all rows therefore finds the global optimum.

The algorithm in three movesSay these aloud before coding

1Keep a running heights array, one entry per column

row 1 heights = [2,0,2,1,1]

2For each row, add 1 to a column's height if it is '1', else reset it to 0

row 2 heights = [3,1,3,2,2]

3Run the histogram largest-rectangle routine on the current heights

histogram of row 2 gives area 6 (cols 2-4, height 2)

4Track the maximum area across all rows

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example

1 · Read1 0 1 0 0

2 · AskHeights after row 0?

3 · Update stateheights = [1,0,1,0,0]

4 · ResultLargest histogram area = 1.

Key takeaway

Histogram heights after row 2; columns 2-4 at height 2 form the 6-area rectangle.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

1
Lines 8-11Update column heights
A '1' extends the tower by one; a '0' flattens it to zero so broken columns cannot contribute.
2
Lines 12Solve one histogram
Delegates to the proven largest-rectangle routine for the current row's skyline.
3
Lines 15-27Histogram helper
Identical monotonic-stack logic as problem 84, reused unchanged per row.

Make it stick

Edge cases, mistakes, and one self-check

Edge cases to test

An all-zero matrix returns 0
An all-ones matrix returns rows x cols
A single row reduces to one histogram call
Empty matrix or empty first row returns 0

Common beginner mistakes

Comparing to integer 1 instead of the string '1', since the grid holds characters
Forgetting to reset a column height to 0 on a '0', which invents rectangles that span gaps
Reallocating a fresh heights array each row instead of updating in place (still correct but wasteful)

Check your understanding

Why is it enough to consider each row as a potential rectangle bottom?

PyPython 3 · solution.py

Optimal

1class Solution:2    def maximalRectangle(self, matrix: list[list[str]]) -> int:3        if not matrix or not matrix[0]:4            return 05        cols = len(matrix[0])6        heights = [0] * cols7        max_area = 08        for row in matrix:9            for j in range(cols):10                heights[j] = heights[j] + 1 if row[j] == "1" else 011            max_area = max(max_area, self._largest(heights))12        return max_area1314    def _largest(self, heights: list[int]) -> int:15        stack: list[tuple[int, int]] = []16        max_area = 017        for i, h in enumerate(heights):18            start = i19            while stack and stack[-1][1] > h:20                idx, height = stack.pop()21                max_area = max(max_area, height * (i - idx))22                start = idx23            stack.append((start, h))24        n = len(heights)25        for idx, height in stack:26            max_area = max(max_area, height * (n - idx))27        return max_area

Time complexityO(rows x cols)Optimized

Space complexityO(cols)Explained

Interview rehearsal

Explain before you code

25:00

Restate constraints and edge cases
Explain brute force and its bottleneck
State the invariant and complexity

Seen at

AmazonGoogleMicrosoft

Maximal Rectangle

Maximal Rectangle

See the pattern, then code

Invariant

Reasoning

Follow the data, one decision at a time

Read the solution in small chunks

Edge cases, mistakes, and one self-check

Edge cases to test

Common beginner mistakes

More in Monotonic Stack and Monotonic Queue