LeetCode #85 Hard

Maximal Rectangle

Given a binary matrix, find the largest rectangle containing only 1s and return its area.

monotonic-stackmatrixdp

02

Intuition

The trap is treating this as its own 2D problem instead of recognizing it as Largest Rectangle in Histogram wearing a matrix costume. Treat every row as the ground line of a histogram, where each bar's height is the number of consecutive 1s stacked directly above that column — the largest rectangle in the matrix with its bottom on this row is then the largest rectangle in that histogram, solved in O(n) with a monotonic stack. Run it once per row and take the best over all rows.

How to spot this pattern

Each row becomes a histogram: the height at a column is how many consecutive 1s sit above it. Then Largest Rectangle in Histogram runs once per row. Reducing a 2-D problem to a known 1-D one, row by row, is the transferable move.

03

Approach

1

Build the histogram row by row

Keep a heights array of width n. For each row, heights[j] += 1 when the cell is 1 — but the easy-to-miss half is heights[j] = 0 when it is 0, not just skipping the increment. A single zero breaks the column's vertical run completely, so the height resets to 0 rather than freezing at whatever it was; forgetting the reset silently treats a broken column as still standing and inflates every rectangle above it. This is a small DP carried across rows in O(1) extra space per step.

2

Reuse Largest Rectangle in Histogram

For each histogram, a monotonic increasing stack finds, for every bar, the nearest smaller bar on each side. The rectangle with that bar as its limiting height spans between those boundaries, giving area height * (right - left - 1). Take the maximum over all bars.

3

Take the maximum across rows

Every rectangle of 1s has a bottom row, and when that row is processed the rectangle appears in its histogram — so no rectangle is missed. With m rows and n columns the total is O(mn) time and O(n) space, versus O(m^2 n^2) for the naive enumeration. The prerequisite really is Largest Rectangle in Histogram; without it this looks unapproachable.

04

Solution & live demo

▶1class Solution:
▶2    def maximalRectangle(self, matrix):
▶3        if not matrix:
▶4            return 0
▶5        n = len(matrix[0])
▶6        heights = [0] * n
▶7        best = 0
▶8        for row in matrix:
▶9            for j in range(n):
▶10                heights[j] = heights[j] + 1 if row[j] in (1, '1') else 0
▶11            st = []
▶12            for j in range(n + 1):
▶13                h = heights[j] if j < n else 0
▶14                while st and heights[st[-1]] >= h:
▶15                    ht = heights[st.pop()]
▶16                    left = st[-1] if st else -1
▶17                    best = max(best, ht * (j - left - 1))
▶18                st.append(j)
▶19        return best

05

Common pitfalls

Not resetting the height on a zero

✗ Wrong

if row[j] == '1': heights[j] += 1

✓ Right

heights[j] = heights[j] + 1 if row[j] in (1, '1') else 0

A zero breaks the vertical run, so the accumulated height above it can no longer support a rectangle at this row. Leaving the old value lets rectangles span straight through obstacles.

Omitting the sentinel column

✗ Wrong

for j in range(n):

✓ Right

for j in range(n + 1):
    h = heights[j] if j < n else 0

Bars still on the stack when the scan ends never get measured. A virtual zero-height column at the end forces every remaining bar to pop and be evaluated.

Computing the width from the popped index

✗ Wrong

best = max(best, ht * (j - st[-1]))

✓ Right

left = st[-1] if st else -1
best = max(best, ht * (j - left - 1))

The rectangle spans from just after the new stack top to just before j, giving a width of j - left - 1. Using the popped index measures only part of the span, and an empty stack means the bar extends all the way to the left edge.

06

Edge cases

Empty matrix

Return 0 before any processing.

All zeros

The heights array stays flat at zero and 0 is returned.

All ones

The answer is the full area, m * n.

Single row

It degenerates to plain largest-rectangle-in-histogram on a 0/1 array.

07

Complexity

Time

O(m*n)

Space

O(n)

One histogram pass per row; the naive enumeration is O(m^2 * n^2).