Largest Rectangle in Histogram (LeetCode 84)

The problem

You get an array heights of non-negative integers, the heights of bars in a histogram, each of width 1, standing side by side. Return the area of the largest rectangle that fits entirely inside the histogram.

Input:  [2, 1, 5, 6, 2, 3]
Output: 10

The bars of height 5 and 6 (indices 2 and 3) together hold a rectangle of height 5 and width 2, so area 10.

How to think about it

Start with brute force. Try every pair (i, j) of left and right ends, keep the minimum height in between, and compute min * (j - i + 1). Tracking the running minimum makes this O(n²), which times out for n = 100,000.

Change what you enumerate. Every best rectangle has some shortest bar inside it, and its height equals that bar’s height. So instead of enumerating ranges, enumerate bars: for each bar k, ask “how wide can a rectangle of exactly height heights[k] be?” It stretches left until the first shorter bar and right until the first shorter bar. Area = heights[k] * (right - left - 1).

The key insight: an increasing stack gives both limits at the moment a bar is popped. Keep a stack of indices whose heights are increasing from bottom to top. When bar i arrives and is not taller than the top, the top bar’s right limit is i (the first bar that is not taller). Its left limit is the index just below it on the stack, because the stack is increasing, so that is the nearest shorter bar to its left. If the stack is now empty, nothing to the left is shorter and the width is i. Pop, compute the area, repeat, then push i.

Which pattern is this? Monotonic stack, specifically “previous smaller and next smaller”. The tell is a rectangle or range whose value is set by its minimum. Appending a sentinel 0 at the end forces every remaining bar to be popped and measured.

Approach

1. Append 0 to heights so the last bars get flushed.
2. Keep a stack st of indices with increasing heights, and best = 0.
3. For each index i with height h:
   • While the stack is non-empty and heights[st[-1]] >= h: pop the top as the rectangle’s height. Its width is i if the stack is now empty, else i - st[-1] - 1. Update best.
   • Push i.
4. Return best.

Solution

def largest_rectangle(heights):
    st = []; best = 0; heights = heights + [0]          # sentinel flushes the stack
    for i, h in enumerate(heights):
        while st and heights[st[-1]] >= h:              # bar on top can't extend past i
            height = heights[st.pop()]
            width = i if not st else i - st[-1] - 1     # left limit is the new top
            best = max(best, height * width)
        st.append(i)
    return best
# largest_rectangle([2,1,5,6,2,3]) -> 10

Dry run

On [2, 1, 5, 6, 2, 3] plus the sentinel 0 at index 6:

When index 2 (height 5) is popped at i = 4, the new top is index 1, so the width is 4 - 1 - 1 = 2. The answer is 10.

Complexity

• Time: O(n). Every index is pushed once and popped once, so the total work of the inner loop is O(n).
• Space: O(n). The stack, plus the copy made by heights + [0].

Edge cases and pitfalls

• Forgetting the sentinel leaves bars on the stack after the loop, and their rectangles are never measured. [1, 2, 3] would return 0.
• Width when the stack is empty is i, not i - 1: the bar was the shortest so far, so it stretches all the way to index 0.
• Equal heights: popping on >= is fine. An equal bar is popped with a too-short width, but the later bar of the same height measures the full width.
• All the same height [3, 3, 3] returns 9; a single bar returns its height.
• Zero heights are fine and act as natural separators.

Related problems

• Trapping Rain Water (LeetCode 42): another histogram problem, also solvable with a monotonic stack or two pointers.
• Maximal Square (LeetCode 221): the 2-D cousin, solved with DP over a binary matrix.
• Daily Temperatures (LeetCode 739): the gentler introduction to “pop when a new element breaks the order”.