Largest Rectangle in Histogram

Problem

Building permit software needs to find the largest rectangular floor plan that fits within a city skyline profile. Given an array of non-negative integers representing bar heights in a histogram (each bar has width 1), find the area of the largest rectangle that can be formed within the histogram.

Input:  [2, 1, 5, 6, 2, 3]  → 10
Input:  [2, 4]               → 4
Input:  [1]                  → 1

Solution

Approach: Monotonic increasing stack of bar indices.

Keep a stack of indices whose heights increase from bottom to top. For each bar, while the stack is non-empty and the top bar is taller than the current one (heights[stack[-1]] > heights[index]), that taller bar can extend no further right - pop it and measure the largest rectangle it anchors. Its height is heights[popped]. Its right boundary is the current index (the first shorter bar); its left boundary is the new stack top after the pop. So width is index - stack[-1] - 1 when the stack is non-empty, or index when empty (the bar reaches all the way to the left edge). Track the running max_area, then push the current index.

The insight is that a bar's maximal rectangle is bounded by the nearest shorter bar on each side, and the increasing stack surfaces both boundaries at the exact moment a shorter bar arrives. Appending a sentinel 0 height guarantees every remaining bar gets popped and measured at the end. Trace [2, 1, 5, 6, 2, 3]: when the 2 at index 4 arrives, it pops 6 (width 1, area 6) then 5 (width 2, area 10), and 10 is the max - the 5-and-6 pair forming a 5x2 rectangle.

Edge cases: The appended sentinel flushes the stack so an all-increasing input like [1, 2, 3] is still measured. An empty stack after a pop means no shorter bar exists to the left, so the rectangle spans from index 0 and width is index.

Complexity: O(n) time, O(n) space - each bar is pushed and popped exactly once over the n+1 iterations; the stack holds up to n indices on a strictly increasing histogram.