Largest Rectangle in Histogram

Hard#84increasing stack

You get the heights of bars standing side by side, each one unit wide. Find the area of the largest rectangle that fits inside them. Our example: [2, 5, 6, 3, 4, 1] gives 12, height 3 over the bars at indices 1 to 4.

84 Largest Rectangle in HistogramWalkthrough · 1×

Example: [2, 5, 6, 3, 4, 1]. The stack keeps indices of bars whose heights rise towards the top; a bar is measured when a lower one pops it. The dashed rectangle is the best so far.

205162334415stack—
not reachedbar ion the stackbar being checked or measuredmeasured

No rectangle yet: best = 0

01/61
restart · back · play · step
Speed
1function largestRectangleArea(heights):
2 best = 0
3 stack = empty stack // indices, rising heights
4 for i from 0 to len(heights): // one past the end
5 h = heights[i] if i < len(heights) else 0
6 while stack not empty and h < heights[top]:
7 bar = pop from stack
8 left = top + 1 if stack not empty else 0
9 area = heights[bar] * (i - left)
10 best = max(best, area)
11 push i onto stack
12 return best
state
best
0
stack
–
i
–
h
–
bar
–
left
–
area
–
historyclick a step to go back

← → step · space play/pause

Why it works

  1. The largest rectangle is as high as the lowest bar under it, and it can stretch from that bar to the first lower bar on each side. So it is enough to measure every bar once, at that full width.
  2. A bar is popped by the first lower bar on its right, at i. The bar under it on the stack is the first lower one on its left: the bars in between were taller and already popped. So it spans left to i − 1.
  3. The extra step with height 0 is lower than every bar, so no bar stays unmeasured at the end.

Complexity

Time O(n): each bar is pushed once and popped once, and each pop is measured in O(1). Memory O(n) for the stack.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.