Largest Rectangle in Histogram

Free with account Updated Nov 19, 2026 · 5 min read
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

    The bars of height 4 and 5 hold a rectangle of height 4 and width 2, area 8, larger than any other choice.
    The bars of height 4 and 5 hold a rectangle of height 4 and width 2, area 8, larger than any other choice.
    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

    1. Can heights be 0? (Yes; a 0 splits the histogram.)
    2. Are bars always width 1? (Here: yes.)
    3. Return the area or the rectangle? (Here: the area.)
    4. How large can n and the heights get? The area can need 64 bits if both are large.