Largest Rectangle in a Skyline

Difficulty: Hard · Pattern: Monotonic Stack · Concept: General Coding (DSA) — Core Patterns to Drill

Given a list of non-negative integers representing bar heights in a histogram (each bar has width 1, standing side by side), find the area of the largest rectangle that can be formed using contiguous bars, where the rectangle's height is limited by the shortest bar it spans.

The brute force checks every pair of left/right bounds and finds the minimum height in between — $O(n^2)$ or worse. The $O(n)$ trick: for every bar, its own height only matters if you can figure out, cheaply, how far it can extend left and right before hitting something shorter. A monotonic stack (indices kept in increasing-height order) computes exactly that in one pass.

Your task: implement largest_rectangle_area(heights) in $O(n)$ time. Return 0 for an empty list.

Implement it yourself

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

Next: Daily Temperatures (another monotonic-stack problem), or continue to Design a Min Stack