Largest Rectangle in Histogram

Signal

"The best rectangle using bar i as its height extends as far left and right as bars stay >= height[i]" — whenever an answer depends on "how far can this element's influence reach before something smaller blocks it," that's a monotonic stack, not a per-bar linear scan.

Approach

Keep a stack of indices with increasing heights. When the current bar is shorter than the stack's top, the top bar can't extend any further right — pop it and finalize its rectangle: height is the popped bar, width is the gap between the current index and the new stack top (exclusive on both ends). Repeat until the stack top is shorter than the current bar, then push. After the scan, drain any remaining bars against the array's end.

Skeleton

stack = []  # indices, heights increasing
best = 0
for i, h in enumerate(heights + [0]):   # sentinel 0 flushes the stack
    while stack and heights[stack.top] > h:
        height = heights[stack.pop()]
        width = i if stack empty else i - stack.top - 1
        best = max(best, height * width)
    stack.push(i)

Solution

def largest_rectangle_area(heights: list[int]) -> int:
    stack: list[int] = []  # indices, heights increasing
    best = 0

    for i, h in enumerate(heights + [0]):  # sentinel flushes remaining bars
        while stack and heights[stack[-1]] > h:
            height = heights[stack.pop()]
            width = i if not stack else i - stack[-1] - 1
            best = max(best, height * width)
        stack.append(i)

    return best

Complexity

O(n) time — each index is pushed once and popped at most once. O(n) space for the stack (the heights + [0] sentinel copy is also O(n)).

Pitfalls

• Forgetting the trailing sentinel (or an equivalent final drain loop) leaves bars stuck on the stack whose rectangles never get finalized — e.g. a strictly increasing input.
• The width formula i - stack[-1] - 1 is easy to get off by one; the popped bar's rectangle spans from just after the new stack top to just before i, exclusive on both ends.
• Brute force (for each bar, expand left/right) is O(n²) and the natural first idea — naming the monotonic stack explicitly is the whole trick here.