-
Notifications
You must be signed in to change notification settings - Fork 0
057 — Largest Rectangle in Histogram
LeetCode 84 · Hard. Given an array heights representing the heights of histogram bars of width 1, standing side by side, find the area of the largest rectangle that can be formed within the histogram's outline.
Picture a skyline of bars of different heights standing shoulder to shoulder. For any single bar, the tallest rectangle that includes that bar's full height is bounded by how far it can stretch left and right before hitting a bar shorter than itself — because a shorter neighbor is a hard wall; the rectangle can't be that tall past that point. The naive way to find this is, for every bar, walk outward in both directions until a shorter bar blocks you. The clever trick: as you scan left to right, keep a stack of bars in increasing height order. The instant a shorter bar shows up, every taller bar sitting on top of the stack has just found its right wall — pop it, and its left wall was whatever's still on the stack below it (or the very start, if nothing's left). One pass resolves every bar's rectangle.
"Largest rectangle in histogram" is one of the textbook monotonic-stack problems — the phrase to listen for is needing, for every bar, "the nearest shorter bar on both sides" to know exactly how far a rectangle anchored at that bar's height can extend. Whenever the question is "how far can I extend outward from each element before hitting something smaller (or bigger)," a stack that only ever grows in one direction (here, increasing height) and resolves entries the instant they're blocked is the O(n) answer to what looks like an O(n²) problem.
For each bar, expand left and right as far as possible while every bar in that range is at least as tall, then compute the resulting rectangle's area.
func largestRectangleAreaBruteForce(_ heights: [Int]) -> Int {
var maxArea = 0
for i in 0..<heights.count {
var left = i
while left > 0 && heights[left - 1] >= heights[i] {
left -= 1
}
var right = i
while right < heights.count - 1 && heights[right + 1] >= heights[i] {
right += 1
}
let width = right - left + 1
maxArea = max(maxArea, width * heights[i])
}
return maxArea
}Big-O: O(n²) time worst case — a flat or strictly monotonic histogram makes each bar's left/right expansion scan most of the array. O(1) extra space.
Keep a stack of indices with strictly increasing bar heights, bottom to top. When the current bar is shorter than the stack's top, the top bar's rectangle is now fully determined: its height is heights[top], its right wall is the current index, and its left wall is whatever's now exposed below it on the stack (or the very start, if the stack empties). A sentinel height of 0 appended after the last real bar forces every remaining bar on the stack to resolve at the end.
func largestRectangleArea(_ heights: [Int]) -> Int {
var stack: [Int] = [] // indices; heights[stack] strictly increasing bottom to top
var maxArea = 0
for i in 0...heights.count {
let currentHeight = (i == heights.count) ? 0 : heights[i] // sentinel flushes the stack at the end
while let top = stack.last, heights[top] > currentHeight {
stack.removeLast()
let height = heights[top]
let width = stack.isEmpty ? i : i - stack.last! - 1
maxArea = max(maxArea, height * width)
}
stack.append(i)
}
return maxArea
}
// smoke test
print(largestRectangleArea([2, 1, 5, 6, 2, 3])) // 10
print(largestRectangleArea([2, 4])) // 4Big-O: O(n) time — each index is pushed exactly once and popped at most once, so the total work across the entire scan (including the sentinel pass) is linear. O(n) space for the stack in the worst case (a strictly increasing histogram).
The brute force re-derives each bar's left and right boundaries independently, re-walking bars that a previous bar's scan may have already implicitly passed over. The optimal solution recognizes that a bar's right boundary is only ever "discovered" once — the moment a shorter bar appears — and its left boundary is simply whatever bar is left exposed on the stack directly below it once every taller bar in between has been resolved and popped. Because every index is pushed exactly once and popped at most once, the total work is O(n) instead of O(n²), the same "each element handled a constant number of times" guarantee that makes every Monotonic Stack problem linear.
- Monotonic Stack — the genuine pattern: a stack of indices in increasing height order, each popped exactly once when its nearest-shorter-bar-to-the-right is found — this problem is explicitly called out as a classic example in that chapter.
- Stacks — the underlying LIFO structure holding the still-unresolved bars.
-
Arrays & Strings — the
heightsarray being scanned.
Largest Rectangle in Histogram is a skyline where every bar's rectangle is capped the instant a shorter bar shows up beside it — a stack of increasing heights resolves every bar's full width in one pass, no re-walking required.
For [2, 1, 5, 6, 2, 3], trace the optimal algorithm's stack (as indices) through i = 0, 1, 2, 3, then walk through what happens at i = 4 (height = 2) — which two indices get popped, what area does each produce, and why does popping index 3 (height 6) after index 2 (height 5) still use the correct, different width for each?