Largest Rectangle in Histogram
On this page
Problem statement
Given the heights of bars in a histogram, each bar 1 unit wide and standing next to each other, return the area of the largest rectangle that fits entirely under the bars.
The textbook use of a monotonic stack: for every bar, you need the first lower bar on each side, and the stack finds all of them in one pass. It is also the building block for "largest rectangle of 1s in a matrix". Original problem: LeetCode 84.
Example

heights = [2, 4, 5, 1, 3, 3]
Output: 8 # height 4 across the bars 4 and 5
heights = [1, 2, 3, 4, 5]
Output: 9 # height 3 across the last three bars
Constraints (assumed)
- 1 ≤ n ≤ 10⁵; 0 ≤ height ≤ 10⁴.
What this question tests
- Reframing: the best rectangle uses some bar's full height, and extends until a lower bar on each side.
- Using a monotonic increasing stack to find both boundaries in O(n).
- Exact width arithmetic and flushing the stack at the end.
Questions to ask first
- Can heights be 0? (Yes; a 0 splits the histogram.)
- Are bars always width 1? (Here: yes.)
- Return the area or the rectangle? (Here: the area.)
- How large can n and the heights get? The area can need 64 bits if both are large.
Try it yourself first
You have the full problem. Sketch your answer, then sign up free to read the complete walkthrough.
- The complete design, flow by flow, with pictures
- Deep dives into the hard parts
- What mid, senior and staff candidates are expected to say
- Full company question lists
Free forever. No card needed.