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.

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

python

▶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

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.

06

Complexity

Time

O(m*n)

Space

O(n)

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