Largest Rectangle in Histogram
Given bar heights, find the largest rectangle that fits under the histogram.
- 1 <= heights.length <= 10⁵
- 0 <= heights[i] <= 10⁴
Intuition
Largest rectangle in histogram asks for the biggest rectangle that fits under a row of bars. The search space looks enormous, but one observation cuts it down enormously: the optimal rectangle's height always equals some bar's full height. If it were shorter, it could be raised until it hit the top of its shortest bar.
So instead of searching over rectangles, search over bars. For each bar, find the widest rectangle having exactly that bar's height. That rectangle extends left and right until it meets a strictly shorter bar — a shorter bar caps the height, so the rectangle must stop there.
The problem is now: for every bar, find the nearest shorter bar on each side. A monotonic increasing stack gets both boundaries in a single pass, and the way it does it is worth seeing clearly.
Keep indices of bars whose heights increase from bottom to top. When a bar shorter than the stack top arrives, that top can never extend any further right — so it is settled:
- The arriving bar is its right boundary, and the new stack top is its left boundary.
Width is i − stack.top − 1 after popping. Both boundaries fall out of one pop, which is what makes this O(n) rather than two separate passes.
Append a sentinel bar of height 0 at the end to force every remaining bar to pop and settle, avoiding a separate drain loop.
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
Before reading on: price up what enumerating every case costs here, then ask what ordering you can maintain so the answer is always at one end. Aim for O(n) time and O(n) space.
Anchor each rectangle to a bar
The best rectangle's height matches some bar exactly — otherwise it could be raised. This turns a search over rectangles into a search over bars, which is a linear number of candidates instead of a quadratic one.
Define the reach of a bar
A bar's rectangle extends left and right until it meets a strictly shorter bar, since a shorter bar would force the height down. Finding those two boundaries for every bar is the whole computation.
Keep a stack of increasing heights
Push indices while heights are non-decreasing. The stack holds bars still waiting to learn their right boundary — the same waiting-room idea as Next Greater Element, with the comparison flipped.
Settle a bar when a shorter one arrives
While the current height is less than the stack top's, pop it. The arriving index is its right boundary and the new stack top is its left, so the width is i - stack.top - 1 and the area is that width times the popped height.
Use the width formula, not the pop index
After popping, the width spans between the two boundaries exclusive, hence the - 1. Using the popped index itself as the left edge is the most common error here and silently understates every area.
Flush with a zero-height sentinel
Append a bar of height 0 so every remaining index is forced to pop before the loop ends. This removes the separate drain loop and the duplicated width logic it would need.
Cost of the single pass
Each index is pushed once and popped once, so the total is O(n) time despite the inner while loop. Space is O(n) for the stack, worst case on a strictly increasing histogram where nothing pops until the sentinel.
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.