The problem
Given bar heights of width 1, return the area of the largest rectangle that fits inside the histogram.
Stuck? Reveal hints one at a time
How to approach it
- 1Iterate i over bars plus one virtual 0-height bar at the end.
- 2While the current height is less than the stack-top bar’s height: pop it — its height h is fixed.
- 3Its width spans from the element under the pop (exclusive) to i (exclusive): width = stack empty ? i : i − stackTop − 1.
- 4Track max(h × width); push i.
Key insight
A bar is popped precisely when its right boundary arrives, and the new stack top IS its left boundary — both boundaries materialize at pop time for free.
The solution
Watch out for
- The empty-stack width case (width = i) covers bars that are the minimum so far.
- Skipping the sentinel leaves the tallest suffix unmeasured.