Maximal Rectangle

Maximal Rectangle looks intimidating — a 2-D grid, find the biggest block of 1s — but it secretly reduces to a problem you may already know: largest rectangle in a histogram. The trick is to turn each row of the grid into a histogram and reuse the monotonic-stack solution.

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

The slow way first

The brute force is brutal: pick every pair of corners for a candidate rectangle and check that every cell inside is a 1. There are O((rows·cols)²) corner pairs and each check scans the rectangle, landing somewhere around O(rows² · cols²) or worse. For anything but a tiny grid that is hopeless.

The question to ask: what sub-problem do I already know how to solve fast? If I look at just one row and ask "how tall is the column of 1s ending at this row," I get a histogram — and largest-rectangle-in-a-histogram is a clean O(n) monotonic-stack problem.

The idea: turn each row into a histogram

Sweep the grid top to bottom while keeping a heights array, one entry per column:

• If matrix[row][c] == 1, the column of 1s got one taller: heights[c] += 1.
• If it is 0, the column is broken, so the height resets to 0.

After updating heights for a row, that array is a histogram of consecutive 1s ending on this row. Run largest rectangle in histogram on it and keep the global maximum. Any all-1s rectangle in the grid has some bottom row, and on that row it shows up as a rectangle in the histogram — so we are guaranteed to see it.

The histogram solver itself uses a stack of column indices whose heights are strictly increasing; when a shorter bar arrives we pop and measure each rectangle. Here we treat it as a reusable building block.

Walk through it

Step through the animation. The grid sweeps row by row. The heights row underneath grows by 1 where a cell is a 1 and snaps to 0 where it is a 0. After each row we read off the best rectangle in that histogram. Row 0 gives 1, row 1 gives 4 (a width-4 bar of height 1), and row 2 gives 6 (height 2 across columns 1–3) — the final answer.

Pseudocode

cols = number of columns
heights = array of cols zeros
best = 0
for each row in matrix:
    for each column c:
        if matrix[row][c] == 1: heights[c] += 1   # column got taller
        else:                   heights[c] = 0     # column broken, reset
    area = largest_rectangle(heights)              # monotonic-stack solver
    best = max(best, area)
return best

The Python solution

def maximal_rectangle(matrix):
    cols = len(matrix[0])
    heights = [0] * cols
    best = 0
    for row in matrix:
        for c in range(cols):
            # extend the column or reset it to 0
            heights[c] = heights[c] + 1 if row[c] == 1 else 0
        area = largest_rectangle(heights)   # monotonic stack
        best = max(best, area)
    return best

• heights[c] is how many consecutive 1s sit in column c ending at the current row.
• The inner loop is the histogram update: +1 when the cell is a 1, hard reset to 0 when it is a 0.
• largest_rectangle(heights) is the standard monotonic-stack histogram solver (see that lesson) — it returns the biggest rectangle area for the current row in O(cols).
• We take max over every row, because each candidate rectangle is measured on its bottom row.

Complexity

Each row costs one linear histogram pass, and there are rows of them, so the whole thing is O(rows · cols) — we touch each cell a constant number of times. The only extra memory is the single heights row, O(cols).

When this pattern shows up

Practice