Appearance
4.8.7 — Largest Rectangle in Histogram
LeetCode 84 · Hard
The problem
Bars of width 1 stand side by side with the given heights. Find the area of the largest rectangle that fits entirely inside the histogram.
heights = [2, 1, 5, 6, 2, 3] → 10The 10 comes from the bars of height 5 and 6: take height 5 across both, giving 5 × 2 = 10.
Up to 100,000 bars.
The pattern
The trap is trying to grow a rectangle outwards from each bar and getting lost in "how far can I extend". Turn the question around instead:
Every rectangle in the answer has some bar as its shortest bar. So ask, for each bar: if this bar is the shortest one in the rectangle, how wide can the rectangle be?
That turns one hard question into n easy ones. A rectangle of height heights[i] extends left until it meets a bar shorter than heights[i], and right until it meets a shorter bar. So:
\text{width}_i = (\text{first shorter to the right}) - (\text{first shorter to the left}) - 1
That is next-smaller-element on both sides — 4.8.5 with the comparison flipped, computed in both directions. You could literally run that algorithm twice, store two arrays, and then take the maximum of height × width. That is a perfectly good O(n) solution and it is the one to describe first.
The version below does it in one pass.
Where the mental block usually is
Most people get stuck trying to work out a bar's area when it is pushed. At that moment you do not know how far right it will extend, so nothing can be computed and the whole thing feels impossible.
The fix is the sentence from 4.8.5:
A monotonic stack computes on eviction, not on insertion.
When a bar is popped, both of its boundaries are known at that exact instant, and neither was known before:
- The right boundary is the bar that triggered the pop. It is the first bar to the right that is shorter — that is precisely why the pop happened.
- The left boundary is whatever is on the stack after the pop. The stack is increasing, so the item beneath is the nearest bar to the left that is shorter.
So the pop event is the moment a bar's entire rectangle becomes computable. Nothing before it, nothing after it.
The solution
python
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = [] # indices, heights increasing
best = 0
heights.append(0) # sentinel: forces everything to be popped
for i, h in enumerate(heights):
while stack and heights[stack[-1]] > h:
height = heights[stack.pop()]
left = stack[-1] if stack else -1
width = i - left - 1
best = max(best, height * width)
stack.append(i)
heights.pop() # undo the mutation
return bestts
function largestRectangleArea(heights: number[]): number {
const stack: number[] = [];
let best = 0;
heights.push(0); // sentinel
for (let i = 0; i < heights.length; i++) {
while (stack.length && heights[stack[stack.length - 1]] > heights[i]) {
const height = heights[stack.pop()!];
const left = stack.length ? stack[stack.length - 1] : -1;
const width = i - left - 1;
best = Math.max(best, height * width);
}
stack.push(i);
}
heights.pop();
return best;
}The sentinel 0 at the end is the trick that removes a whole second loop. Without it, bars left on the stack when the array runs out would need separate handling. A zero is shorter than every bar, so appending it forces every remaining bar to be popped and measured through the normal path. One code path, no special case.
Pop it again afterwards, since you mutated the caller's array. On a judge nobody notices; in real code that is a side effect.
left = stack[-1] if stack else -1. An empty stack means no shorter bar exists anywhere to the left, so the rectangle reaches all the way to index 0. Using -1 as the imaginary boundary makes i - (-1) - 1 = i come out right without a branch.
width = i - left - 1. The rectangle spans the bars strictly between the two boundaries. Check it on the diagram: i = 4, left = 1, width 4 - 1 - 1 = 2, which is bars 2 and 3. Correct.
Trace
heights = [2, 1, 5, 6, 2, 3] with the sentinel appended.
| i | h | pops (height, left, width, area) | stack after |
|---|---|---|---|
| 0 | 2 | — | [0] |
| 1 | 1 | pop 2: left −1, width 1, area 2 | [1] |
| 2 | 5 | — | [1,2] |
| 3 | 6 | — | [1,2,3] |
| 4 | 2 | pop 6: left 2, width 1, area 6 · pop 5: left 1, width 2, area 10 | [1,4] |
| 5 | 3 | — | [1,4,5] |
| 6 | 0 | pop 3: left 4, width 1, area 3 · pop 2: left 1, width 4, area 8 · pop 1: left −1, width 6, area 6 | [6] |
Best is 10.
Look at the second-to-last pop: the bar of height 1 spans the entire histogram, width 6, area 6. The sentinel is what produced it.
Complexity
O(n) time. Each index is pushed once and popped once — 2n operations across the whole run, not n per iteration.
O(n) space for the stack, worst case an increasing histogram where nothing is popped until the sentinel.
Where this goes next
- Maximal Rectangle (LeetCode 85) — the largest rectangle of 1s in a binary matrix. Treat each row as the base of a histogram whose heights are the runs of consecutive 1s above it, then run this algorithm once per row. O(rows × cols), and it is one of the most satisfying reductions in the whole set. Chapter 4.24.
- Trapping Rain Water — the same structure computing water instead of area, filling horizontally rather than vertically. 4.5.5.
- Sum of Subarray Minimums — for each element, how many subarrays it is the minimum of. Same boundaries, different thing computed from them.
The rule: when the answer for an element depends on the nearest smaller or larger element on each side, use a monotonic stack and compute at the pop.
What the interviewer will push on
"Explain the width formula." Right boundary is the bar that caused the pop; left boundary is the new stack top; the rectangle is what lies strictly between them, hence right - left - 1.
"Why can you not compute the area when pushing?" The right boundary is not known yet. This is the question that separates people who understand monotonic stacks from people who copied one.
"What is the sentinel for?" To flush the stack through the normal code path instead of writing a second loop.
"Prove it is O(n)." Each index enters and leaves the stack once.
"Solve it without a stack." There is a divide-and-conquer solution — find the minimum bar, take min × width, then recurse left and right — but it is O(n^2) in the worst case without a sparse table for range minimums. Worth naming, not worth writing.
One thing to volunteer: say "every rectangle has a shortest bar, so I will ask for each bar how far it can extend" before writing anything. That reframing is the entire solution, and stating it first is what makes the rest look easy.
Next: 4.9 leaves arrays behind for pointer discipline — dummy heads, slow and fast pointers, and the reversal that half of those problems are built from.