Stack · LC #84
Largest Rectangle in Histogram
Find the largest rectangular area in a histogram using a monotonic increasing stack, extending each bar as far left as possible to compute its maximum rectangle.
Statement
Problem & Approach
Problem statement, sample I/O, and key reasoning.
Given an array of integers `heights` representing the height of bars in a histogram where each bar has width 1, return the area of the largest rectangle in the histogram.
Sample I/O
Input: heights = [2,1,5,6,2,3] Output: 10 (bars at index 2 and 3, height=5, width=2) Input: heights = [2,4] Output: 4 Input: heights = [6,2,5,4,5,1,6] Output: 12
Time: O(n) · Space: O(n)
Intuition
How to Think About It
Intuition
For each bar, the maximum rectangle using that bar as the limiting height extends left until a shorter bar is encountered and right until a shorter bar is encountered. Instead of computing left/right boundaries for every bar separately, a monotonic stack lets you process both boundaries in one pass: when a bar is popped because a shorter bar arrived, the shorter bar defines its right boundary, and the popped bar's stored start index defines its left boundary.
Core Concept
Maintain a monotonic increasing stack of `(startIndex, height)` pairs. When a new bar of height `h` is encountered that is shorter than the stack top, pop all taller bars. For each popped bar, its rectangle spans from its stored `startIndex` to the current index - area = `height × (currentIndex - startIndex)`. The current bar can extend leftward as far as the last popped bar's `startIndex`, so inherit it. After the main loop, flush remaining bars using the array length as the right boundary.
When to use
Any problem reducible to "find the maximum rectangle in a histogram": Maximal Rectangle in Binary Matrix (LC #85), Trapping Rain Water (LC #42), largest rectangle under a curve.
When NOT to use
When the histogram is circular or 3D - different formulations are needed. When the problem has additional constraints per cell (e.g., obstacles) that prevent simple height stacking.
Key Insights
What to Know Cold
- The `start` variable is key: each popped bar donates its start index to the current bar, allowing the current bar's rectangle to extend left past bars it consumed.
- Storing `(startIndex, height)` rather than just indices avoids a look-up into the `heights` array after popping.
- The post-loop flush processes bars that were never popped (no shorter bar came after them) - they extend to the right end of the array.
- This is the same monotonic stack direction as the "water trapping" problem but height comparison is inverted (increasing vs. decreasing).
- LC #85 (Maximal Rectangle) applies this exact algorithm row by row on a binary matrix.
1 example
Worked Examples
Trace on heights = [2,1,5,6,2,3]
Find the largest rectangle: answer is 10 (bars 2 and 3, height 5, width 2).
i=0: push (0,2). i=1: h=1 < 2; pop (0,2) area=2*(1-0)=2, start=0; push (0,1). i=2: push (2,5). i=3: push (3,6). i=4: h=2 < 6; pop (3,6) area=6*(4-3)=6, start=3; h=2 < 5; pop (2,5) area=5*(4-2)=10, start=2; push (2,2). i=5: push (5,3). Flush: (5,3)→3*1=3; (2,2)→2*4=8; (0,1)→1*6=6. Max=10.
largestRectangleArea([2,1,5,6,2,3]); // 10 largestRectangleArea([2,4]); // 4
Output: 10
The bar at index 2 (height=5) gets its start set to 2 and right boundary set to 4 when index 4 (height=2) is processed - showing exactly how the inherited `start` and current index combine to compute the rectangle width.