Largest Rectangle in Histogram
Given bar heights, find the largest rectangle that fits under the histogram.
Open on LeetCode ↗Intuition
The best rectangle using bar i as its height extends to the nearest shorter bar on each side. A monotonic increasing stack finds both boundaries in one pass: when a bar pops, the popper is its right boundary and the new stack top its left.
A monotonic stack shows up when every element needs to know its nearest smaller (or greater) neighbour on each side. Keeping indices in increasing height order means the moment a shorter bar arrives, everything taller is finalised — the new bar is its right boundary and the stack entry below is its left. Next-greater-element, daily-temperatures and maximal-rectangle all run on this engine.
Approach
Every rectangle is pinned by a bar
The optimal rectangle's height equals some bar's full height — so compute, for each bar, its widest reach.
Pop = settle
Keep indices of increasing heights. When h[i] < top, the top pops: its width is i − (new top) − 1, area = height × width. Settle all taller bars.
Sentinel flush
Append a 0-height bar to force every index to settle by the end. Each bar pushes and pops once → O(n).
Solution & live demo
Common pitfalls
Forgetting the sentinel and leaving bars unprocessed
for i, h in enumerate(heights):
...for i, h in enumerate(heights + [0]):
...On an increasing histogram like [1, 2, 3] nothing ever pops, so no rectangle is ever measured and the answer comes back 0. Appending a zero-height bar is shorter than everything, forcing the stack to drain through the normal code path instead of a duplicated post-loop block.
Computing the width from the popped index
best = max(best, height * (i - stack[-1]))
left = stack[-1] if stack else -1 best = max(best, height * (i - left - 1))
The rectangle spans the gap strictly between its two boundaries, so the width is i - left - 1, not i - left. And when the stack empties, the bar extends all the way to the start, which is what the -1 sentinel encodes.
Popping with >= instead of >
while stack and heights[stack[-1]] >= h:
while stack and heights[stack[-1]] > h:
For equal heights the earlier bar's true right boundary lies further right, so settling it now measures it short. It still gets the right final answer — the last of the equal run spans the full width — but only by accident, and the reasoning stops holding under small changes.
Edge cases
Nothing settles until the sentinel; widths then span from each bar to the end.
Left boundary is −1 → width is the full prefix, handled by the ternary.