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.

Example 1:

Input: heights = [4, 2, 8, 9, 3, 5]
Output: 16

Example 2:

Input: heights = [5, 7]
Output: 10

Example 3:

Input: heights = [9]
Output: 9

Constraints:

• 1 <= heights.length <= 10^4
• 0 <= heights[i] <= 10^4

Solution Breakdown

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 [4, 2, 8, 9, 3, 5]: when the 2 at index 1 arrives, it pops 4 (width 1, area 4); when the 3 at index 4 arrives, it pops 9 (width 1, area 9) then 8 (width 2, area 16), and 16 is the max - the 8-and-9 pair forming an 8x2 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.