Largest Rectangle in Histogram
Each bar's widest rectangle spans until a shorter bar on either side.
Stack Trace
Problem
Given an array of nonnegative bar heights, where every bar has width 1, determine the maximum area of a rectangle that fits entirely within consecutive bars. The rectangle's height is limited by the shortest bar in its chosen range. Return the largest possible area.
Examples
Input: heights = [2,1,5,6,2,3]
Output: 10
Input: heights = [2,4]
Output: 4
The Goal
Bars of width 1 stand side by side. Find the largest rectangle that fits under consecutive bars. Its height is the lowest bar it covers.
For [2, 1, 5, 6, 2, 3], bars 2 and 3 (heights 5 and 6) hold a rectangle 5 high and 2 wide: area 10.
So every bar is a candidate height. A bar's rectangle stretches left and right until it meets a lower bar.
Height times width
A bar of height h stretches over every neighbor at least as tall. Its area is h times that width.
The first lower bar on each side ends it.
Key Idea: A Stack of Open Bars
Keep the bars whose rectangle is still open on a stack, with heights rising from bottom to top.
When a new bar is no taller than the top, pop the top and measure its rectangle. It ends just before the new bar. It starts just after the bar now on top, which is lower.
Then push the new bar.
i − left − 1: both edges are outside the rectangle.
4 − 1 − 1 = 2, so 5 × 2 = 10.
The Algorithm
def largest_rectangle_area(heights):
# Bars whose rectangle is still open, with heights rising to the top.
stack = []
best = 0
for i in range(len(heights) + 1):
h = heights[i] if i < len(heights) else 0
while stack and heights[stack[-1]] >= h:
top = stack.pop()
left = stack[-1] if stack else -1
best = max(best, heights[top] * (i - left - 1))
stack.append(i)
return bestThe loop runs one step past the last bar and reads a height of 0 there. No bar is lower, so that step closes every rectangle still open.
| Approach | Time | Space | How |
|---|---|---|---|
| Expand from every bar | O(n^2) | O(1) | Scan left and right from each bar |
| Stack of open bars | O(n) | O(n) | Measure a bar when a bar no taller closes it |
| Divide and conquer | O(n log n) on average | O(n) at worst | Split around the lowest bar |
Walkthrough
Run it on [2, 1, 5, 6, 2, 3].
Bar 1 (height 1) pops bar 0: area 2. Then heights 1, 5 and 6 rise, so nothing pops.
Bar 4 (height 2) pops bar 3 (6 × 1 = 6), then bar 2, whose rectangle covers bars 2 and 3: 5 × 2 = 10. That's the answer.
Past the end, height 0 pops bars 5, 4 and 1, for areas 3, 8 and 6.
Checkpoint · predict the next step
Step 13 of 38 on the stage: Bar 2 is 5, lower than 6: its rectangle can still grow. Stop popping.
i on 6 (index 3) · stack = [1, 2] · best 2
Pitfalls
- Measure after the pop: the left edge is the bar now on top.
- Both edges are outside the rectangle, so the width is
i - left - 1, withleft = -1for an empty stack. - Don't skip the step past the end.
[1, 2, 3, 4, 5]pops nothing before it, and its best is 9. - Equal heights pop each other. In
[3, 3, 3, 3], the end pops the last 3 with the whole width: 12.
Past the end of [2, 1, 5, 6, 2, 3], i = 6 pops bar 4, leaving bar 1 on top. What width does bar 4's rectangle get?
Complexity
Each bar is pushed once and popped at most once, so all the pops together cost O(n), even when one bar pops several. Time is O(n).
When the heights only rise, every bar waits on the stack until the end, so space is O(n).
One pass over the bars, plus one step past the end
- Scan the barsPlus one step past the end.dominantO(n)
- Pushes and popsEach bar goes on once and comes off once.dominantO(n)
- Measure a popped barHeight times width.O(1)
- The stackRising bars all wait.dominantO(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
Linear, because no bar is pushed or popped twice.
In short
Keep an increasing stack of bar indices. When a shorter bar arrives, pop taller bars and compute the area each can form, using the new index and the stack's next element as the width bounds. A sentinel zero at the end flushes the stack.
Common mistake
Getting the width wrong after a pop — it spans from the element now below on the stack (exclusive) to the current index (exclusive).