The problem
Given heights, the bar heights of a histogram whose bars are each 1 wide, return the area of the largest rectangle that fits inside it.
Examples
01
- Input
heights = [2, 1, 5, 6, 2, 3]
- Output
10
02
- Input
heights = [2, 4]
- Output
4
Constraints
- 1 ≤ heights.length ≤ 10⁵
- 0 ≤ heights[i] ≤ 10⁴
The idea
The largest rectangle is as tall as some bar, and stretches left and right from it until a shorter bar stops it. So for each bar we need where it starts and where it is cut off.
Keep a stack of bars in increasing height, each with the leftmost index it can reach. When a shorter bar arrives, every taller bar on the stack is cut off here: pop it and measure height × (i − start). The new bar can reach back to the start of the last bar it popped. A final bar of height 0 cuts off everything left.
- Time
- O(n) — each bar is pushed and popped once
- Space
- O(n)
Solution · every language run against every case
class Solution: def largestRectangleArea(self, heights: List[int]) -> int: stack = [] # (start index, height); heights increase upward best = 0 for i, h in enumerate(heights + [0]): # a final 0 flushes the stack start = i while stack and stack[-1][1] >= h: j, hj = stack.pop() best = max(best, hj * (i - j)) # hj could stretch from j up to i start = j # the new bar can reach back as far as the popped one did stack.append((start, h)) return best