Largest Rectangle in Histogram is a classic stack problem. It looks geometric and scary, but it reduces to one idea: a monotonic stack that tells each bar how far it can stretch.
Problem. Given an array heights where each value is the height of a bar of width 1, find the area
of the largest rectangle that fits entirely inside the histogram.
Example: heights = [2, 1, 5, 6, 2, 3] → answer 10 (the rectangle of height 5 spanning the bars at
indices 2 and 3, width 2 → 5 × 2 = 10).
The slow way first
For every bar, you could expand left and right while neighbors are at least as tall, then multiply height by that width. That is O(n²) — each bar can scan most of the array. For 100,000 bars it is far too slow.
The question to ask: while standing on a bar, how do I find its span instantly instead of scanning? The answer is to remember bars in a clever order so the boundary is always one lookup away.
The idea: a monotonic stack
Keep a stack of bar indices whose heights are strictly increasing. Walk left to right. When the next bar is shorter than the bar on top of the stack, that top bar can stretch no further right — so we pop it and finally measure its rectangle.
The popped bar’s height is its own height. Its width runs from just after the new stack top (the first shorter bar to its left) up to the current index (the first shorter bar to its right). One pop, one rectangle.
The trick: width = i - stack[-1] - 1 after popping, because the new top is the nearest shorter bar on the left and i is the nearest shorter bar on the right.
Walk through it
Step through the animation. Increasing bars (2, then 5, 6) just get pushed onto the stack. When bar 1 (height 1) arrives it pops bar 0. The big moment is at i = 4 (height 2): it pops bar 3 (height 6, width 1) and then bar 2 (height 5, width 2 → area 10). A final sentinel bar of height 0 flushes whatever is left so no rectangle is missed.
Pseudocode
stack = empty list of indices # heights along the stack are increasing
best = 0
for each index i over heights + a trailing 0 (sentinel):
while stack is not empty and heights[top of stack] > heights[i]:
top = pop stack
height = heights[top]
width = i if stack is empty else i - (new top) - 1
best = max(best, height * width)
push i onto stack
return bestThe Python solution
def largest_rectangle(heights):
stack = [] # indices, heights strictly increasing
best = 0
for i, h in enumerate(heights + [0]): # 0 sentinel flushes
while stack and heights[stack[-1]] > h:
top = stack.pop()
height = heights[top]
width = i if not stack else i - stack[-1] - 1
best = max(best, height * width)
stack.append(i)
return best- The stack holds indices, not heights, so we can compute widths from positions.
- The appended
[0]is a sentinel: after the real bars, a height of 0 is shorter than everything, so thewhileloop empties the stack and measures every leftover bar. heights[stack[-1]] > his the pop condition — the top bar is taller than the incoming bar, so it stops here.width = i if not stack else i - stack[-1] - 1: if the stack is now empty, the bar reached all the way to the left edge; otherwise it stretches from just past the new top toi.- Every index is pushed once and popped once, so the whole thing is O(n).
Complexity
| Case | Time | Notes |
|---|---|---|
| Brute force (expand each bar) | O(n²) (slow) | scan neighbors per bar |
| Monotonic stack (this solution) | O(n) (moderate) | each index pushed and popped once |
O(n) (moderate)The stack adds O(n) space, and in exchange every bar finds both of its boundaries in amortized O(1). That push-once-pop-once accounting is the signature of a monotonic-stack solution.
When this pattern shows up
A monotonic stack is the go-to whenever you need, for each element, the nearest smaller or larger neighbor. Largest rectangle, "trapping rain water," "next greater element," and "daily temperatures" are all the same machinery: keep a stack ordered, and pop when the order would break.
Do not forget the sentinel. Without the trailing 0, any bars still on the stack at the end (a strictly increasing histogram, for example) are never measured, and you return a wrong, too-small answer.
Practice
At i = 4 (height 2) we pop index 2 (height 5). The stack underneath is now [1]. What width does bar 2 get, and what area?
1. What does the stack hold?
2. When do we pop a bar and measure its rectangle?
3. Why append a trailing 0 (the sentinel)?
4. Why is the algorithm O(n)?