Problem 14 · Stacks

Largest Rectangle in Histogram

HardClassic DSA & systems

01Problem

Given bar heights of a histogram with width 1, return the area of the largest rectangle.

02Key insight

For each bar, the rectangle using it as the shortest extends to the nearest smaller bar on each side. An increasing stack finds both boundaries when a bar is popped; a sentinel 0 flushes the stack.

03Solution

solution.pypython10 lines

def largest_rectangle_area(heights: list[int]) -> int:
    stack: list[int] = []  # indices with increasing heights
    best = 0
    for i, h in enumerate(heights + [0]):  # sentinel flushes stack
        while stack and heights[stack[-1]] >= h:
            height = heights[stack.pop()]
            left = stack[-1] if stack else -1
            best = max(best, height * (i - left - 1))
        stack.append(i)
    return best

Try it first.

TimeO(n)

SpaceO(n)

tests.py · 4 passing

tests.pypython4 lines

assert largest_rectangle_area([2,1,5,6,2,3]) == 10
assert largest_rectangle_area([2,4]) == 4
assert largest_rectangle_area([]) == 0
assert largest_rectangle_area([3,3,3]) == 9

04Staff-level follow-up

Maximal rectangle of 1s in a binary matrix? Build per-row histograms of consecutive 1s and run this routine on each row: O(rows*cols).