Largest Rectangle in Histogram

Interview Prep

HardStackstackmonotonic-stack

The problem

Given an array h of non-negative bar heights (each bar width 1), find the area of the largest axis-aligned rectangle that fits inside the histogram. The classic application: dynamic programming on a 2D binary matrix reduces to running this on each row.

Why the brute force fails

def largest_rect_brute(h: list[int]) -> int:
    """For each bar, expand outwards to find the largest rectangle with it as the min height."""
    best, n = 0, len(h)
    for i in range(n):
        l = r = i
        while l > 0 and h[l - 1] >= h[i]: l -= 1
        while r < n - 1 and h[r + 1] >= h[i]: r += 1
        best = max(best, h[i] * (r - l + 1))
    return best
# O(n^2) worst case (sorted-decreasing input)

For each bar, you find the largest rectangle where it is the bottleneck (i.e., the shortest bar in its span). The expand-outwards walk is O(n) per bar, giving O(n²). The cleverest trick in this problem is that those left/right extensions for every bar can be computed amortised in O(1) using a monotonic stack.

Pattern: monotonic-increasing stack

Sweep left to right keeping a stack of bar indices whose heights are non-decreasing. When a new bar x is shorter than the top of the stack, that top bar's rectangle is finally bounded on the right (by x's position) — pop it and compute the area:

Keep popping until the top is ≤ x, then push i. Appending a sentinel 0 at the end flushes every remaining bar from the stack uniformly.

Each index is pushed and popped at most once, so the total work is O(n).

Solution

def largest_rect(h: list[int]) -> int:
    """O(n) via a monotonic-increasing stack of indices.
    When a smaller bar arrives, pop all taller bars and finalize their rectangle:
    the popped bar's rectangle ends at the new bar's index, and starts just after
    the new top of the stack (or 0 if the stack is empty).
    """
    stack: list[int] = []                  # indices of bars in non-decreasing height order
    best = 0
    for i, x in enumerate(h + [0]):        # sentinel 0 at the end flushes the stack
        while stack and h[stack[-1]] > x:
            top = stack.pop()
            height = h[top]
            left = stack[-1] if stack else -1
            width = i - left - 1
            best = max(best, height * width)
        stack.append(i)
    return best

Trace

h = [2, 1, 5, 6, 2, 3]    (sentinel 0 appended)

stack = [], best = 0

i=0, x=2:  stack empty.  push.  stack=[0].
i=1, x=1:  h[0]=2 > 1.  pop 0: height=2, left=-1, width=1-(-1)-1=1, area=2.  best=2.
           stack empty.  push.  stack=[1].
i=2, x=5:  h[1]=1 <= 5.  push.  stack=[1, 2].
i=3, x=6:  h[2]=5 <= 6.  push.  stack=[1, 2, 3].
i=4, x=2:  h[3]=6 > 2.  pop 3: height=6, left=2, width=4-2-1=1, area=6.  best=6.
           h[2]=5 > 2.  pop 2: height=5, left=1, width=4-1-1=2, area=10. best=10.
           h[1]=1 <= 2.  push.  stack=[1, 4].
i=5, x=3:  h[4]=2 <= 3.  push.  stack=[1, 4, 5].
i=6, x=0 (sentinel):  flush.
           pop 5: height=3, left=4, width=6-4-1=1, area=3.
           pop 4: height=2, left=1, width=6-1-1=4, area=8.
           pop 1: height=1, left=-1, width=6-(-1)-1=6, area=6.
           stack=[], best=10.

return 10   (rectangle spanning bars 2..3 at height 5)

Complexity

Why monotonic stacks generalize

The monotonic stack is the canonical answer to "for each position, find the nearest smaller / larger neighbor". Largest Rectangle needs both nearest-smaller-left and nearest-smaller-right; the single-pass version above implicitly computes both at the moment of pop. Mastering this pattern unlocks Sliding Window Maximum (deque variant), Sum of Subarray Minimums, Daily Temperatures, and many DP optimizations.

Variations worth knowing