Largest rectangle (bounds by pops)

57 s · title card, the worked example step by step, then a recap. The captions carry the explanation; there is no narration. Download the MP4.

01The intuition

Start with what you would do by hand

Six bars stand side by side with heights 2, 1, 5, 6, 2, 3, each one unit wide. Which rectangle fits inside the skyline with the biggest area? Looking at the picture, the two tall bars 5 and 6 together give a rectangle of height 5 and width 2, area 10. The whole row gives height 1 and width 6, area 6.

By hand you might try every pair of left and right ends: for each pair find the shortest bar between them, multiply by the width. With 6 bars there are 21 pairs, and finding the shortest bar in each costs more looks, so roughly 50 steps. For n bars the pairs alone number n(n + 1)/2, about half a million for a thousand bars, and each needs a scan. That is cubic work, O(n³), or O(n²) if you are careful.

A better question for each single bar: if this bar is the shortest bar of the rectangle, how far can the rectangle stretch left and right before it hits a shorter bar? For bar 5 (index 2) the next shorter bar on the left is 1 (index 1) and on the right is 2 (index 4), so it stretches over indices 2 and 3, width 2, area 10. Every rectangle has some shortest bar, so checking this for every bar finds the maximum. What we need is, for each bar, its nearest shorter neighbour on each side.

Build the structure, one piece at a time

Piece 1: a stack of bars. A stack is a pile where you add to the top and remove from the top. Walk the bars left to right and push each index onto the pile.

Piece 2: keep the pile increasing. Before pushing a new bar, look at the top. If the top bar is taller than the new bar, the new bar is the top bar's nearest shorter neighbour on the right. Pop it. And the bar now underneath it on the pile is its nearest shorter neighbour on the left, because the pile only holds bars shorter than the ones above. So one pop tells us both boundaries, and we can compute the popped bar's rectangle immediately.

Piece 3: a sentinel. At the end, pretend a bar of height 0 arrives, so everything left on the pile gets popped and measured.

The pile on the example (heights shown, boundaries are "the bar below on the pile" and "the new bar"):

The width of a popped bar is (index of the new bar) − (index of the bar below it on the pile) − 1. When the pile is empty below, the left boundary is the start, index −1.

Why it is correct

The invariant: the pile holds bars whose nearest shorter neighbour on the right has not appeared yet, and from bottom to top their heights increase.

A bar stays on the pile only until something shorter arrives, so the pile really is "waiting for a shorter neighbour on the right". A bar is pushed only after every taller bar above it is popped, so the bar below it is shorter or equal, which keeps the pile increasing. When bar i is popped by bar j, no bar between them was shorter than i, or it would have popped i earlier, so j is the nearest shorter bar on the right. And the bar under i on the pile is the nearest shorter bar on the left, because any bar between them that was taller than i was popped before i was pushed.

area(i) = height[i] × (right[i] − left[i] − 1)

Every rectangle in the skyline is limited by its shortest bar, and that bar's rectangle is at least as large, so the maximum over all bars is the true maximum.

Why it is fast

Each bar is pushed once and popped once (the sentinel guarantees the pop). So there are at most 2n pile operations, and each pop does one multiplication. The running time is O(n), compared with the half-million pairs of the by-hand method for a thousand bars.

How to recognise it in an interview

The wording is "largest rectangle", "maximal rectangle in a binary matrix" (treat each row as a histogram of consecutive ones above it), or "sum over all subarrays of the minimum" (each element times how many subarrays it is the minimum of, which is exactly the left and right boundaries). Say: "Each bar is the shortest bar of some rectangle; an increasing stack gives me its nearest shorter neighbour on both sides in one pass."

Largest Rectangle in Histogram is the pattern as shown. Maximal Rectangle runs it once per row. Sum of Subarray Minimums replaces "multiply by height" with "multiply by the count of subarrays", which is (left span) × (right span).

02The idea in one line

An increasing stack; popping a bar fixes its left and right smaller neighbours.

Reach for it when: Largest rectangle in histogram, maximal rectangle, sum of subarray minimums.

Cost: O(n) time.

03The walk-through, step by step

The video works one example: Largest Rectangle in Histogram on [2,1,5,6,2,3]. These are its captions in order, so you can follow without the video or check a step you missed.

1. An increasing stack: popping a bar fixes both of its smaller neighbours
2. Bar 0 (h=2) ≥ top: push index 0
3. Pop 0 (h=2): bounded by the start and 1, width 1, area 2
4. Bar 1 (h=1) ≥ top: push index 1
5. Bar 2 (h=5) ≥ top: push index 2
6. Bar 3 (h=6) ≥ top: push index 3
7. Pop 3 (h=6): bounded by 2 and 4, width 1, area 6
8. Pop 2 (h=5): bounded by 1 and 4, width 2, area 10
9. Bar 4 (h=2) ≥ top: push index 4
10. Bar 5 (h=3) ≥ top: push index 5
11. Pop 5 (h=3): bounded by 4 and 6, width 1, area 3
12. Pop 4 (h=2): bounded by 1 and 6, width 4, area 8
13. Pop 1 (h=1): bounded by the start and 6, width 6, area 6
14. Sentinel 0 flushed the stack
15. Largest rectangle: 5 × 2 = 10 (heights 5 and 6)
16. Each bar is pushed and popped once: O(n)

04Asked at Google

7 Google-tagged LeetCode problems use this pattern. Frequency is LeetCode's Google-tag score (higher means reported more often); "last 6 months" marks problems reported in the most recent window of the export.

05Related patterns

Other patterns in Monotonic Stack: Next greater element, Greedy removal with a stack, Previous and next smaller (both sides).