Largest Rectangle in Histogram: The Monotonic Stack Pattern
Solve Largest Rectangle in Histogram in O(n) with a monotonic increasing stack — intuition, a full worked walkthrough, JavaScript code, and complexity analysis.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Largest Rectangle in Histogram looks geometric, but the winning idea is pure bookkeeping. You're given bar heights and asked for the biggest axis-aligned rectangle that fits under them — and the naive answer re-measures the same spans thousands of times.
The fix is a monotonic stack: a stack you deliberately keep sorted by height. It turns a quadratic search into a single left-to-right pass where every bar is pushed once and popped once. Learn the reasoning here and you've got the template for Trapping Rain Water, Maximal Rectangle, and the entire "next smaller element" family.
The problem
Given an array heights where heights[i] is the height of the i-th bar (each bar has width 1), return the area of the largest rectangle that can be formed using contiguous bars.
The catch: a rectangle of height h can only span bars that are all at least h tall. Widen it past a shorter bar and it no longer fits under the histogram.
Input: heights = [2, 1, 5, 6, 2, 3]
Output: 10 // bars at index 2 and 3 (heights 5 and 6),
// rectangle of height 5 and width 2The best rectangle here isn't the tallest bar (6, area 6) or the widest span. It's height 5 across the two bars [5, 6] — 5 × 2 = 10. Every bar is a candidate height; the job is finding how far each one can stretch sideways before a shorter bar blocks it.
The brute force baseline
For each bar, expand left and right while neighbors stay at least as tall, then compute its rectangle:
function largestRectangleArea(heights) {
let maxArea = 0;
for (let i = 0; i < heights.length; i++) {
let left = i, right = i;
while (left > 0 && heights[left - 1] >= heights[i]) left--;
while (right < heights.length - 1 && heights[right + 1] >= heights[i]) right++;
maxArea = Math.max(maxArea, heights[i] * (right - left + 1));
}
return maxArea;
}This is correct and easy to reason about, but for each of the n bars it can scan almost the entire array to find its boundaries — O(n²) total. On a histogram like [5, 4, 3, 2, 1] (or the reverse), every bar walks the full width. At n = 10⁵ that's ten billion comparisons. We need each boundary discovered once, not re-derived per bar.
The key insight: pop the bar the moment its right wall appears
A bar's rectangle is capped by the first shorter bar to its right. Until you meet that shorter bar, the bar's rectangle can keep growing; the instant you meet it, the width is fixed forever.
So walk left to right and hold bars on a stack that stays monotonically increasing in height. As long as the new bar is taller, just push it — its story isn't over. But when the new bar at index i is shorter than the stack top, that top bar has just hit its right wall. Pop it and finalize its rectangle: its height times the width from where it started up to i.
One more trick makes it clean. When you pop taller bars, the shorter new bar can extend backwards over the ground they vacated. So each stack entry stores a pair — { index, height } — where index is the effective start the bar can reach, not necessarily where you first saw it. That's what lets a bar claim the full width it deserves.
The optimal solution
This is the exact algorithm the visualizer steps through — a stack of { index, height } pairs, plus a cleanup pass for bars that never met a shorter neighbor:
function largestRectangleArea(heights) {
let maxArea = 0;
const stack = []; // pairs: { index, height }
for (let i = 0; i < heights.length; i++) {
let start = i;
// Maintain a monotonic increasing stack
while (stack.length > 0 && stack[stack.length - 1].height > heights[i]) {
const popped = stack.pop();
const area = popped.height * (i - popped.index);
maxArea = Math.max(maxArea, area);
start = popped.index; // The new bar can extend backwards
}
stack.push({ index: start, height: heights[i] });
}
// Calculate areas for remaining bars in stack extending to the end
const n = heights.length;
for (let popped of stack) {
const area = popped.height * (n - popped.index);
maxArea = Math.max(maxArea, area);
}
return maxArea;
}Two phases. The main loop finalizes every bar that gets blocked by a shorter bar on its right. The cleanup loop handles the survivors — bars still on the stack when the array ends never met a shorter bar, so they stretch all the way to index n, giving width n - popped.index.
Walkthrough
Trace heights = [2, 1, 5, 6, 2, 3]. Each stack entry is written {start, height}.
| i | height | What happens | Stack after | maxArea |
|---|---|---|---|---|
| 0 | 2 | empty stack → push {0,2} | [{0,2}] | 0 |
| 1 | 1 | 2 > 1 → pop {0,2}, area 2×(1−0)=2; push {0,1} | [{0,1}] | 2 |
| 2 | 5 | 1 < 5, no pop → push {2,5} | [{0,1},{2,5}] | 2 |
| 3 | 6 | 5 < 6, no pop → push {3,6} | [{0,1},{2,5},{3,6}] | 2 |
| 4 | 2 | 6 > 2 → pop {3,6}, area 6×(4−3)=6; 5 > 2 → pop {2,5}, area 5×(4−2)=10; push {2,2} | [{0,1},{2,2}] | 10 |
| 5 | 3 | 2 < 3, no pop → push {5,3} | [{0,1},{2,2},{5,3}] | 10 |
Now the cleanup pass over the three survivors, each extending to n = 6:
| popped | width = 6 − start | area | maxArea |
|---|---|---|---|
{0,1} | 6 | 1×6 = 6 | 10 |
{2,2} | 4 | 2×4 = 8 | 10 |
{5,3} | 1 | 3×1 = 3 | 10 |
Answer: 10. The decisive moment is i = 4: bar 6 gets popped for area 6, then bar 5 gets popped and — because it started at index 2 and the wall is at index 4 — claims width 2 for area 10. Notice the new bar of height 2 inherits start = 2, the index of the last bar it popped, so it "remembers" it can reach back over that vacated ground.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force expand | O(n²) | O(1) | each bar may scan the whole array for its walls |
| Monotonic stack | O(n) | O(n) | each bar is pushed once and popped once — 2n operations total |
The stack version looks like it has a nested while loop, but the total number of pops across the entire run is bounded by the number of pushes, which is exactly n. That's amortized O(n): every bar enters and leaves the stack a single time. Space is O(n) for a strictly increasing input like [1, 2, 3, 4, 5], where nothing pops until cleanup and all n bars sit on the stack at once.
Common mistakes
- Using
>=instead of>in the pop condition. With equal heights you can pop early and shrink the width prematurely. Popping only on strictly greater (stack top height > heights[i]) keeps equal-height bars merged into one span. The visualizer's[3, 3, 3, 3]case (answer 12) is the check. - Forgetting the cleanup loop. Bars that never meet a shorter neighbor — the whole of an ascending histogram — stay on the stack forever. Skip the final pass and you undercount every one of them.
- Storing the raw index instead of the effective
start. If a pushed bar keeps the indexiwhere you saw it rather than thepopped.indexit inherited, it can't extend backward over popped bars and its width comes out too small. - Computing width as
i - popped.index - 1. Becausestartalready points at the leftmost reachable column, the width is exactlyi - popped.index. Sentinel-based variants that store the previous stack index need the-1; this pair-based version does not.
Where this pattern shows up next
The "pop when the boundary arrives" move is the core of every monotonic-stack problem:
- Car Fleet — process elements in order and collapse them against a running boundary, the same one-pass, each-element-handled-once discipline.
You can also step through Largest Rectangle in Histogram interactively to watch the stack grow, the pops fire, and the winning rectangle light up bar by bar.
FAQ
Why is the monotonic stack solution O(n) if it has a nested loop?
Because the inner while loop can only pop bars that were previously pushed, and each bar is pushed exactly once. Across the whole run there are at most n pushes and therefore at most n pops, so the inner loop does n total iterations spread over the outer loop — not n per outer step. That amortizes to O(n) time overall, even though any single outer iteration might pop several bars.
What does each entry on the stack actually represent?
Each entry is a { index, height } pair standing for a candidate rectangle that is still growing. The height is the bar's height; the index is the leftmost column that rectangle can reach — which may be earlier than where the bar first appeared, because a bar inherits the starting index of the shorter bars it popped. The stack stays increasing in height, so the entry just below any bar is its nearest shorter bar on the left, which is exactly its left boundary.
Why do we need a separate cleanup loop at the end?
Bars still on the stack after the main pass never encountered a shorter bar to their right, so their rectangles were never finalized. These bars can extend all the way to the right edge of the histogram, giving each a width of n - index. The cleanup loop computes those final areas. Without it, any ascending run — the extreme case being a fully sorted [1, 2, 3, 4, 5] — would contribute nothing to the answer.
How do I handle equal-height bars correctly?
Pop only when the stack's top is strictly taller than the current bar (>), never on equal (>=). Equal-height bars should merge into a single wide rectangle, and using strict-greater keeps the earlier bar on the stack so the span isn't cut short. For [3, 3, 3, 3] this yields one rectangle of height 3 and width 4, area 12 — the right answer.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.