Lesson 18 — Monotonic Stack: Rectangles

~25 minutes · monotonic stack · Python · Day 18

Tonight's interview problem is Largest Rectangle in Histogram. You are given bar heights and must find the biggest rectangle that fits inside the histogram. The hard part is not computing one rectangle; it is knowing exactly when a bar's best rectangle is finally ready to calculate.

The invariant

When a shorter bar appears, each taller bar you pop can no longer extend right, so finalize its rectangle. (Hard — go slow.)

Largest rectangle: the slow way first

The brute-force approach is to choose every left edge, grow the right edge, and keep the minimum height inside that range. That is O(n²), because many ranges repeat the same height work. The problem statement is on LeetCode; Python's list-as-stack operations give us the stack tool.

def largestRectangleArea(heights):
    best = 0
    for left in range(len(heights)):
        min_h = float("inf")
        for right in range(left, len(heights)):
            min_h = min(min_h, heights[right])
            best = max(best, min_h * (right - left + 1))
    return best

Largest rectangle: the stack way

Keep a stack of bars whose heights are increasing. Each stack entry stores the earliest index where that height can start. When the current bar is shorter, it blocks every taller bar on the stack from extending any farther right, so those taller bars are ready to score.

At index 4, height 2 is the first shorter bar, so the taller 6 and 5 are popped and scored.

def largestRectangleArea(heights):
    best = 0
    stack = []                         # (start_index, height), increasing heights
    for i, h in enumerate(heights + [0]):
        start = i                      # where the current height can begin
        while stack and stack[-1][1] > h:
            idx, height = stack.pop()  # height's right edge is i - 1
            best = max(best, height * (i - idx))
            start = idx                # shorter h inherits this left reach
        stack.append((start, h))
    return best

The added 0 is a sentinel: it forces every remaining bar to be popped at the end. The width formula is the whole trick: if a popped bar started at idx and the first shorter bar is at i, its rectangle width is i - idx.

The popped height can stretch from its stored start index up to the bar before the first shorter height.

Transfer: same pattern, new costume

Maximal Rectangle: given a grid of 0s and 1s, find the largest rectangle containing only 1s.

Before opening the reveal: predict the bridge. How could each grid row become a histogram? Once you have that histogram, what exact stack invariant would you reuse?

heights = [0] * cols
for row in matrix:
    for c, cell in enumerate(row):
        heights[c] = heights[c] + 1 if cell == "1" else 0
    best = max(best, largestRectangleArea(heights))

What the trade buys you

The O(n) claim is amortized: every index is pushed once and popped once. One short bar may trigger many pops, but those bars never return to the stack.

Practice — answer before you scroll past

Your move (tonight)

Solve this on LeetCode, logging it in your Notion tracker with the cycle — predict → attempt → compare → encode:

1. Largest Rectangle in Histogram — predict the brute force first, then code the monotonic stack from the invariant.

For the encode step, write why a shorter bar gives popped bars their right boundary, and why each bar is pushed and popped at most once.

Stuck or curious? Ask your teacher (the agent) — that's what it's for.