Maximal Rectangle

Turn each matrix row into a histogram, solve that histogram with a monotonic stack, and keep only the state that can still affect future rows.

Recognize the row-to-histogram reduction

The matrix contains '0' and '1' characters. We need the largest axis-aligned rectangle containing only '1' cells.

The direct search has four boundaries: top, bottom, left, and right. That is the wrong state to carry. A better decomposition anchors every candidate rectangle at its bottom row.

For the current row r, define:

heights[c] = consecutive '1' cells ending at row r in column c

If the current height array is:

[3, 1, 3, 2, 2]

then columns 2 through 4 support a rectangle of height 2 and width 3:

area = 2 × 3 = 6

The array is now a histogram. Its largest rectangle represents the largest all-ones rectangle whose bottom row is r.

The complete algorithm is therefore:

1. Update cumulative column heights for the current matrix row.
2. Solve the resulting histogram.
3. Keep the largest area found across all rows.

This reduction is complete because every nonempty matrix rectangle has exactly one bottom row. When that row is processed, the rectangle appears as a histogram interval.

The two states have different lifetimes:

• heights persists from one matrix row to the next.
• The histogram stack is discarded and rebuilt for every row.

That separation is the central implementation detail.

Why brute force repeats work

A brute-force solution enumerates possible top, bottom, left, and right boundaries, then checks whether the rectangle contains only ones. Overlapping rectangles repeatedly inspect the same vertical runs.

A row-pair approach improves this by fixing the top and bottom rows, but it still processes many row pairs. Its typical time complexity is O(R²C) for R rows and C columns.

The optimized solution stores one reusable vertical fact per column:

vertical state:   heights[c]
horizontal state: monotonic stack

The vertical work is accumulated once as the scan moves downward. The horizontal work is delegated to the largest-rectangle-in-histogram algorithm.

This is still an exhaustive solution. It examines every possible bottom row. It simply compresses repeated validity checks into cumulative state.

Build cumulative heights

Process the matrix from top to bottom. After processing row r, heights[c] means:

The number of consecutive '1' cells in column c ending at row r.

The update is local:

if matrix[r][c] == "1":
    heights[c] += 1
else:
    heights[c] = 0

A zero is a hard boundary. It destroys the vertical run at that column immediately. A rectangle cannot pass through it.

For the canonical matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

the cumulative histograms are:

Bottom row	Heights
0	[1, 0, 1, 0, 0]
1	[2, 0, 2, 1, 1]
2	[3, 1, 3, 2, 2]
3	[4, 0, 0, 3, 0]

At row 2, columns 2 through 4 all have height at least 2. They form a valid matrix rectangle with area 2 × 3 = 6.

The histogram records vertical capacity. The stack will determine how far that capacity can extend horizontally.

Solve each histogram with a monotonic stack

For a histogram bar of height h, a rectangle using that bar as its limiting height can extend across every contiguous bar with height at least h.

Its area is:

height × width

The width ends immediately before the first smaller bar on the right and begins immediately after the first smaller bar on the left.

Use a stack of indices whose heights are increasing. When a new height is smaller than the height at the stack top, the taller bars can no longer extend through the current position. Pop them and calculate their areas.

For a popped index p at current index i:

left = stack[-1] + 1 if stack else 0
width = i - left
area = bars[p] * width

The new stack top determines the nearest smaller boundary on the left. The current index is the exclusive boundary on the right.

The stack must store indices, not only heights. The height gives the area multiplier; the index gives the width.

Equality policy

Use one explicit policy throughout the code and proof:

• Pop while the stack-top height is greater than or equal to the current height.
• Push the current index afterward.

With this policy, equal heights replace earlier representatives. The later equal-height bar has the same height and the same effective left boundary after the earlier bar is popped, while it can extend at least as far to the right.

The stack invariant is then:

Before processing the current index, stack indices have strictly increasing heights.

Flush the histogram

Bars at the right edge may never encounter a smaller real bar. Append a sentinel height 0 so every positive bar is finalized:

bars = heights + [0]

The sentinel is processed like an ordinary height. It pops every remaining positive bar, then can be pushed harmlessly as the final stack entry.

This is not cleanup after the algorithm. It is part of the boundary logic. Without it, rectangles reaching the final column can disappear.

The two-state invariant

The full algorithm composes two separate invariants.

Vertical invariant

After processing matrix row r:

heights[c] equals the number of consecutive ones ending at (r, c).

A '1' extends the run. A '0' resets it.

Horizontal invariant

During one histogram scan:

The stack contains unresolved indices with strictly increasing heights.

An index remains unresolved while no smaller height has appeared to its right. Once a smaller height arrives, the index is popped and its maximum legal width is known.

Each index is pushed at most once and popped at most once. The nested while loop is therefore linear over one histogram.

Do not reuse the stack across matrix rows. The heights are related across rows, but each row is a separate histogram with separate horizontal boundaries. Carrying the stack forward mixes positions from different problems.

Width rule: after popping an index, calculate the left boundary from the new stack top. The width is not generally current_index - popped_index.

Why the reduction is correct

A passing example is evidence. A proof explains why the method cannot miss the answer.

Heights represent vertical runs

For the first row, each '1' creates height 1, and each '0' creates height 0.

Assume the invariant holds after row r - 1.

• If matrix[r][c] == "1", the run ending at (r, c) extends by one, so heights[c] += 1.
• If matrix[r][c] == "0", no all-ones rectangle ending at (r, c) can include that cell, so heights[c] = 0.

Therefore the heights correctly represent consecutive vertical runs after every row.

Histogram rectangles are valid matrix rectangles

Consider a contiguous histogram interval of width w whose minimum height is h.

Every column in that interval has at least h consecutive ones ending at the current row. The bottom h cells in those w columns are therefore all ones.

They form a valid matrix rectangle of area:

h × w

So every rectangle reported by a histogram is legal in the original matrix.

The stack finds each maximum span

When index p is popped at index i, the current height is less than or equal to bars[p]. Because the scan moves left to right, i is the first position on the right that blocks height bars[p].

After removing p, the new stack top is the nearest surviving position on the left with a smaller height. The rectangle for p therefore spans:

left boundary = stack[-1] + 1, or 0
right boundary = i - 1

and has width:

i - left

The sentinel guarantees that every positive bar eventually receives this treatment.

Every optimal matrix rectangle is represented

Take an optimal all-ones rectangle with:

• bottom row r
• height h
• width w

When row r is processed, every column inside the rectangle has cumulative height at least h. Therefore the corresponding histogram contains a width-w interval with minimum height at least h.

The histogram solver considers that interval and obtains an area of at least:

h × w

Because every histogram rectangle is valid in the matrix, the maximum histogram area for row r is exactly the best rectangle ending at that row. Scanning every row includes the bottom row of the global optimum, so the global maximum is correct.

Complete dry run of the boundary logic

Use this histogram:

[2, 1, 5, 6, 2, 3]

Append the sentinel:

[2, 1, 5, 6, 2, 3, 0]

With the >= equality policy:

Index	Height	Stack before	Pops and areas
0	2	[]	—
1	1	[0]	pop 2: width 1, area 2
2	5	[1]	—
3	6	[1, 2]	—
4	2	[1, 2, 3]	pop 6: width 1, area 6; pop 5: width 2, area 10
5	3	[1, 4]	—
6	0	[1, 4, 5]	pop 3: width 1, area 3; pop 2: width 4, area 8; pop 1: width 6, area 6

At index 4, the height 2 causes a pop chain. The height-6 bar spans only column 3. After it is removed, the height-5 bar spans columns 2 and 3, producing area 10.

At the sentinel, every remaining positive bar is finalized. The final stack contains only the sentinel index. Nothing is left unresolved.

The same flush occurs for every matrix row, including histograms that end with a long positive suffix.

Python implementation

The code mirrors the two-state derivation:

• heights persists across rows.
• stack is fresh for each histogram.
• The sentinel finalizes the right edge.
• Equal heights are handled by popping with >=.

from typing import List


class Solution:
    def maximalRectangle(self, matrix: List[List[str]]) -> int:
        if not matrix or not matrix[0]:
            return 0

        cols = len(matrix[0])
        heights = [0] * cols
        best = 0

        def largest_histogram_rectangle(current_heights: List[int]) -> int:
            bars = current_heights + [0]
            stack: List[int] = []
            histogram_best = 0

            for i, height in enumerate(bars):
                while stack and bars[stack[-1]] >= height:
                    popped = stack.pop()
                    left = stack[-1] + 1 if stack else 0
                    width = i - left
                    histogram_best = max(
                        histogram_best,
                        bars[popped] * width,
                    )

                stack.append(i)

            return histogram_best

        for row in matrix:
            for col, cell in enumerate(row):
                if cell == "1":
                    heights[col] += 1
                else:
                    heights[col] = 0

            best = max(best, largest_histogram_rectangle(heights))

        return best

The comparison with "1" follows the problem contract exactly. Other values are treated as zeros by the else branch; valid input contains only '0' and '1'.

The expression current_heights + [0] creates a temporary copy for one histogram. It uses O(C) space and does not accumulate across rows. A virtual sentinel could avoid the copy, but the explicit list makes the boundary behavior easier to inspect and debug.

Complexity and edge cases

Let R be the number of rows and C the number of columns.

For each row:

• Updating heights costs O(C).
• Each histogram index is pushed once.
• Each histogram index is popped at most once.

Therefore:

Time:  O(RC)
Space: O(C) auxiliary, excluding the input matrix

The temporary histogram copy, heights array, and stack are all bounded by the number of columns.

Check these cases deliberately:

• All zeros: every height is zero; the answer is 0.
• All ones: the final histogram represents the full matrix; the answer is R × C.
• One cell: '0' produces 0; '1' produces 1.
• One row: the algorithm becomes the ordinary histogram problem.
• One column: each vertical run is evaluated correctly.
• Alternating zeros: each zero resets its column and blocks horizontal spans.
• Trailing positive heights: the sentinel must pop them.
• Equal heights: the comparison policy must match the invariant and proof.
• Empty input: the defensive guard returns 0, even though the stated constraints describe a nonempty matrix.
• Uneven rows: the contract requires equal row lengths; the implementation relies on that condition.

Common implementation failures are predictable:

1. Omitting the sentinel: rectangles reaching the last column are never evaluated.
2. Using the popped index for the width: the new stack top defines the left boundary.
3. Failing to reset on zero: a rectangle crosses a zero cell illegally.
4. Reusing the stack across rows: unrelated histograms share horizontal state.
5. Mixing equality policies: the code may contradict its invariant or proof.
6. Swapping dimensions: cols is len(matrix[0]), not len(matrix).

The transferable recognition rule is this:

When a two-dimensional all-ones rectangle can be anchored by a row and expressed as cumulative column capacity, preserve the vertical state, reset the horizontal state, and solve each row as a histogram.

Before coding, name both states: persistent heights and per-row stack. Then verify the finalization rule: every candidate must be popped by a smaller height or by the sentinel. That is the reasoning pattern to carry into the next problem—not the code template alone.