Module 08 · Monotonic Stacks and Monotonic Deques

075. Largest Rectangle in Histogram

Bridge · Download this solution · All solutions and shared helpers

Problem

Given nonnegative unit-width bar heights, return the largest rectangular area entirely under the histogram. A rectangle spans consecutive bars and uses their minimum height. Empty input returns zero. Do not mutate the heights.

Examples

Example 1

largest_histogram([2,1,5,6,2,3])
=> 10

The height-five rectangle spans the middle two bars.

Example 2

largest_histogram([2,2])
=> 4

Equal heights can combine into a wider rectangle.

Example 3

largest_histogram([])
=> 0

No positive area exists.

Reveal the worked solution and reasoning

Why this mechanism works

A bar can define a candidate rectangle until a shorter bar closes its right boundary. Maintain increasing-height indices. When popping a taller bar, the current index is its first shorter boundary to the right and the new stack top limits its left extension. A final zero-height sentinel closes remaining positive-height candidates.

State and boundaries

stack contains indices in nondecreasing height order. Popping index j finalizes a rectangle of height heights[j] across all bars between its boundaries.

Protocol

Scan bars followed by a zero-height sentinel.
Pop while the current height is smaller.
Compute width as current_index-new_top-1, using -1 for no left blocker.
Update best area.
Push the current index.

Visualization

heights: 2 1 5 6 2 3
when 2 arrives: pop 6, then 5
height 5 spans two bars -> area 10

Python implementation

def largest_histogram(heights):
    stack = []
    best = 0
    for i in range(len(heights) + 1):
        current = heights[i] if i < len(heights) else 0
        while stack and heights[stack[-1]] > current:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        if i < len(heights):
            stack.append(i)
    return best

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

largest_histogram([2,1,5,6,2,3])

L2 largest_histogram: stack = []
heights=[2, 1, 5, 6, 2, 3]; stack=[]

L3 largest_histogram: best = 0
heights=[2, 1, 5, 6, 2, 3]; stack=[]; best=0

L4 largest_histogram: for i in range(len(heights) + 1):
heights=[2, 1, 5, 6, 2, 3]; stack=[]; best=0; i=0

L5 largest_histogram: current = heights[i] if i < len(heights) else 0
heights=[2, 1, 5, 6, 2, 3]; stack=[]; best=0; i=0; current=2

L11 largest_histogram: stack.append(i)
heights=[2, 1, 5, 6, 2, 3]; stack=[0]; best=0; i=0; current=2

L4 largest_histogram: for i in range(len(heights) + 1):
heights=[2, 1, 5, 6, 2, 3]; stack=[0]; best=0; i=1; current=2

L5 largest_histogram: current = heights[i] if i < len(heights) else 0
heights=[2, 1, 5, 6, 2, 3]; stack=[0]; best=0; i=1; current=1

L7 largest_histogram: height = heights[stack.pop()]
heights=[2, 1, 5, 6, 2, 3]; stack=[]; best=0; i=1; current=1; height=2

... 25 intermediate state changes omitted ...

L7 largest_histogram: height = heights[stack.pop()]
heights=[2, 1, 5, 6, 2, 3]; stack=[1]; best=10; i=6; current=0; height=2; left=4

L8 largest_histogram: left = stack[-1] if stack else -1
heights=[2, 1, 5, 6, 2, 3]; stack=[1]; best=10; i=6; current=0; height=2; left=1

L7 largest_histogram: height = heights[stack.pop()]
heights=[2, 1, 5, 6, 2, 3]; stack=[]; best=10; i=6; current=0; height=1; left=1

L8 largest_histogram: left = stack[-1] if stack else -1
heights=[2, 1, 5, 6, 2, 3]; stack=[]; best=10; i=6; current=0; height=1; left=-1

Result: 10. The height-five rectangle spans the middle two bars.

largest_histogram([2,2])

L2 largest_histogram: stack = []
heights=[2, 2]; stack=[]

L3 largest_histogram: best = 0
heights=[2, 2]; stack=[]; best=0

L4 largest_histogram: for i in range(len(heights) + 1):
heights=[2, 2]; stack=[]; best=0; i=0

L5 largest_histogram: current = heights[i] if i < len(heights) else 0
heights=[2, 2]; stack=[]; best=0; i=0; current=2

L11 largest_histogram: stack.append(i)
heights=[2, 2]; stack=[0]; best=0; i=0; current=2

L4 largest_histogram: for i in range(len(heights) + 1):
heights=[2, 2]; stack=[0]; best=0; i=1; current=2

L11 largest_histogram: stack.append(i)
heights=[2, 2]; stack=[0, 1]; best=0; i=1; current=2

L4 largest_histogram: for i in range(len(heights) + 1):
heights=[2, 2]; stack=[0, 1]; best=0; i=2; current=2

... 3 intermediate state changes omitted ...

L9 largest_histogram: best = max(best, height * (i - left - 1))
heights=[2, 2]; stack=[0]; best=2; i=2; current=0; height=2; left=0

L7 largest_histogram: height = heights[stack.pop()]
heights=[2, 2]; stack=[]; best=2; i=2; current=0; height=2; left=0

L8 largest_histogram: left = stack[-1] if stack else -1
heights=[2, 2]; stack=[]; best=2; i=2; current=0; height=2; left=-1

L9 largest_histogram: best = max(best, height * (i - left - 1))
heights=[2, 2]; stack=[]; best=4; i=2; current=0; height=2; left=-1

Result: 4. Equal heights can combine into a wider rectangle.

Why the solution is correct

All bars between a popped bar's blockers are at least its height, so the computed rectangle is valid. For any optimal rectangle, one of its minimum-height bars is eventually popped with a span at least as wide, ensuring the optimum is considered. Sentinel processing prevents unfinished candidates.

Time and space

O(n) time and O(n) stack space.

Common mistakes

Width is not simply the number of stack entries. Forgetting the sentinel misses increasing histograms.

Reasoning card

State: stack contains indices in nondecreasing height order. Popping index j finalizes a rectangle of height heights[j] across all bars between its boundaries.

Invariant: Stack indices have increasing heights and unresolved right boundaries.

Decision to rehearse: A lower bar finalizes rectangles whose heights can no longer extend.

Finish: Push the current index

Transfer exercise

Return the rectangle's start, exclusive end and height, and define a deterministic tie policy for equal areas.