LeetCode 84 ·
Hard
Largest Rectangle in Histogram
Find the area of the largest rectangle that fits under the histogram.
Try it
Step through the core mechanic. The simulator below runs the stack / monotonic stack shape this problem is built on.
Interactive · monotonic stack pop while the new value beats the top
input
73 0
74 1
75 2
71 3
69 4
72 5
76 6
73 7
stack (value@index)
empty
answer (days until warmer)
00000000
empty stack of indices (temperatures decreasing top→down)
The approach
Increasing stack of bar indices. When a shorter bar arrives, pop and compute each popped bar's maximal rectangle, using the new index and the stack's new top as its right/left bounds.
| Aspect | Value |
|---|---|
| Pattern | Stack / monotonic stack |
| Recognise it by | Biggest axis-aligned rectangle under a bar chart. |
| Time complexity | O(n) |
| Space complexity | O(n) |
| Difficulty | Hard |
Who asks it
Companies known to ask this problem, from public LeetCode company-tag aggregations. A signal of where to expect it, not a guarantee.