Largest rectangle in a histogram

Question

Given bar heights of unit width, find the area of the largest rectangle that fits entirely under the skyline. A rectangle of height h can extend left and right as far as bars of height at least h continue.

heights = [2,1,5,6,2,3]  ->  10

Return the largest rectangle area. Aim for $O(n)$ time.

Accepted Answer

For each bar, the widest rectangle capped at that bar's height runs from the first shorter bar on its left to the first shorter bar on its right. A monotonic increasing stack of indices finds both boundaries in one pass: while the incoming bar is shorter than the stack top, that top's right boundary is here, and its left boundary is the new stack top after popping. Tracing [2,1,5,6,2,3]: the 1 pops the 2, area 2. Later the 2 at index 4 pops the 6 (width 1, area 6) then the 5 (spanning indices 2 to 3, width 2, area 10). The trailing sentinel 0 flushes the rest, none beating 10. Answer 10. Each…

Largest rectangle in a histogram

Your answer

More Coding questions