Appearance
4.8.7 — Largest Rectangle in Histogram
LeetCode 84 · Hard
The problem
You are given a list called heights. Each number is the height of a bar, and every bar is 1 unit wide. The bars stand side by side with no gaps, like a bar chart. Find the area of the largest rectangle that fits completely inside the bars.
heights = [2, 1, 5, 6, 2, 3] → 10
heights = [2, 4] → 4In the first example, the 10 comes from the bars of height 5 and 6. A rectangle of height 5 fits across both of them, so its area is 5 \times 2 = 10. It cannot be taller than 5, because the bar of height 5 would not reach.
There are up to 100,000 bars, each up to 10,000 tall.
What the problem is really asking
A rectangle that sits on a stretch of bars can only be as tall as the shortest bar in that stretch. That gives a way to turn the problem around.
Every rectangle has a shortest bar. So ask, for each bar: if this bar is the shortest one in the rectangle, how wide can the rectangle be?
A rectangle with the height of bar i can stretch left until it meets a bar shorter than bar i, and right until it meets a shorter bar. It cannot cross a shorter bar, because that bar would not reach.
So for each bar, we need two things:
- the nearest shorter bar on its left, and
- the nearest shorter bar on its right.
The rectangle fills everything strictly between them:
\text{width}_i = \text{right}_i - \text{left}_i - 1
Read it as "the position of the shorter bar on the right, minus the position of the shorter bar on the left, minus one". The minus one is there because neither of those shorter bars is part of the rectangle.
Finding "the nearest smaller bar" is the next smaller element question. It is 4.8.5 Daily Temperatures with the comparison flipped, done in both directions.
Think of building a stage on top of a row of uneven pillars. For each pillar, ask: "if the stage is exactly as high as this pillar, how far left and right can I build before a pillar is too short to hold it up?" Work out the area for each pillar, and keep the biggest.
The brute force, and where it wastes work
Try every stretch of bars. For each one, the height is its shortest bar.
python
def largestRectangleArea(heights):
best = 0
n = len(heights)
for i in range(n):
shortest = heights[i]
for j in range(i, n):
shortest = min(shortest, heights[j]) # shortest bar from i to j
best = max(best, shortest * (j - i + 1))
return bestThat is O(n^2), about five billion steps for 100,000 bars.
The waste in one sentence: it tries every stretch, when only one stretch per bar matters, the widest one that bar can be the shortest of.
The idea
You could run the next-smaller-element method twice, once from each side, store two lists, and then compute every width. That is a perfectly good O(n) answer, and it is the one to describe first in an interview.
The version below does it in one pass, using one monotonic stack of bar positions whose heights go up from the bottom of the stack to the top.
The common mental block is trying to work out a bar's area when it is pushed. At that moment you do not know how far right it will reach, so nothing can be computed. The fix is the sentence from 4.8.5:
A monotonic stack does its work when an item is popped, not when it is pushed.
When a bar is popped, both its edges become known at that exact moment.
- The right edge is the new bar that caused the pop. It is the first bar to the right that is shorter. That is exactly why the pop happened.
- The left edge is whatever is on top of the stack after the pop. The stack's heights go up, so the item just beneath is the nearest bar to the left that is shorter.
The figure shows one such pop.
The solution
python
class Solution:
def largestRectangleArea(self, heights: List[int]) -> int:
stack = [] # (1)
best = 0
heights.append(0) # (2)
for i, h in enumerate(heights): # (3)
while stack and heights[stack[-1]] > h: # (4)
height = heights[stack.pop()] # (5)
left = stack[-1] if stack else -1 # (6)
width = i - left - 1 # (7)
best = max(best, height * width) # (8)
stack.append(i) # (9)
heights.pop() # (10)
return bestts
function largestRectangleArea(heights: number[]): number {
const stack: number[] = []; // (1)
let best = 0;
heights.push(0); // (2)
for (let i = 0; i < heights.length; i++) { // (3)
while (stack.length && heights[stack[stack.length - 1]] > heights[i]) { // (4)
const height = heights[stack.pop()!]; // (5)
const left = stack.length ? stack[stack.length - 1] : -1; // (6)
const width = i - left - 1; // (7)
best = Math.max(best, height * width); // (8)
}
stack.push(i); // (9)
}
heights.pop(); // (10)
return best;
}Line by line
(1) The stack holds bar positions, and their heights go up from bottom to top. Each bar on the stack is waiting to find its right edge.
(2) Add a bar of height 0 at the end. This extra bar is called a sentinel, a fake item added to make the code simpler. A height of 0 is shorter than every real bar. So when the loop reaches it, every bar still on the stack gets popped and measured through the normal code. Without it, bars left on the stack at the end would need a second loop.
(3) Walk the bars, including the sentinel.
(4) Is the newest waiting bar taller than this bar? If so, this bar is the first shorter bar to its right. Its right edge has been found, so it can be measured. The while repeats, because one short bar can end several taller ones.
(5) Pop it and read its height. This is the height of the rectangle we are about to measure.
(6) Find the left edge. After the pop, the top of the stack is the nearest shorter bar on the left. If the stack is empty, no shorter bar exists anywhere to the left, so the rectangle reaches all the way to position 0. We pretend the left edge is at position −1, just before the start. That makes line (7) give the right width with no extra if.
(7) The width. The rectangle covers the bars strictly between the left edge and the right edge i, so the width is i - left - 1. Check it on the figure: i = 4, left = 1, and the width is 4 - 1 - 1 = 2. That is bars 2 and 3, which is correct.
(8) Keep the best area.
(9) Push this bar. After the pops, everything on the stack is no taller than this bar, so the heights still go up.
(10) Remove the sentinel. Line (2) changed the caller's list. Undoing it is good manners, because someone else may use that list after this function returns.
Trace
Take heights = [2, 1, 5, 6, 2, 3], with the sentinel 0 added at position 6.
i | h | Pops: height, left edge, width, area | Stack after (positions) |
|---|---|---|---|
| 0 | 2 | — | [0] |
| 1 | 1 | height 2, left −1, width 1, area 2 | [1] |
| 2 | 5 | — | [1, 2] |
| 3 | 6 | — | [1, 2, 3] |
| 4 | 2 | height 6, left 2, width 1, area 6; then height 5, left 1, width 2, area 10 | [1, 4] |
| 5 | 3 | — | [1, 4, 5] |
| 6 | 0 | height 3, left 4, width 1, area 3; height 2, left 1, width 4, area 8; height 1, left −1, width 6, area 6 | [6] |
The best area is 10.
Look at the last pop. The bar of height 1 at position 1 is shorter than everything, so its rectangle spans the whole chart, width 6, area 6. It was only measured because the sentinel forced it off the stack.
Complexity, derived
Time. There is a while inside a for, and once again it is not O(n^2). Each position is pushed exactly once in line (9) and popped at most once in line (5). So over the whole run there are at most 2n stack operations in total. Each one comes with a constant amount of arithmetic. So the time is O(n).
Space. In the worst case the heights only go up, like [1, 2, 3, 4, 5]. Then nothing is popped until the sentinel, and the stack holds all n positions. So the space is O(n).
Edge cases
- One bar. The sentinel pops it with left −1 and width 1, so the answer is its height.
- Heights only go up. Everything waits for the sentinel. The sentinel then measures each bar with its full width to the right.
- Heights only go down. Each bar pops the one before it straight away.
- Equal heights, like
[3, 3, 3]. Line (4) uses>, so equal bars stay on the stack together. The last one to be popped measures the full width. The earlier ones measure shorter widths, which is harmless, because the maximum is still found. - A bar of height 0 in the middle. It pops everything before it and splits the chart in two.
Variations you will meet
- Maximal Rectangle. Find the largest rectangle of 1s in a grid of 0s and 1s. Treat each row as the floor of a bar chart. Each bar's height is the number of 1s stacked directly above that cell, counting the cell itself. Run this page's code once per row. It is one of the most satisfying reductions in the whole NeetCode list.
- Trapping Rain Water. The same stack, but working out water instead of area, filling it in horizontal layers. See 4.5.5.
- Sum of Subarray Minimums. For each number, count how many stretches it is the smallest number of. The left and right edges come from the same stack.
The general lesson: when the answer for each item depends on the nearest smaller (or larger) item on each side, use a monotonic stack and do the work when you pop.
What the interviewer will push on
"Explain the width formula." The right edge is the bar that caused the pop. The left edge is the new top of the stack. The rectangle is strictly between them, so right - left - 1.
"Why can't you work out the area when you push?" The right edge is not known yet. This question separates people who understand monotonic stacks from people who copied one.
"What is the extra 0 for?" To push every remaining bar through the normal code, instead of writing a second loop.
"Prove it is O(n)." Each position enters and leaves the stack once.
"Can you solve it without a stack?" Yes, by divide and conquer. Find the shortest bar, measure it across the whole range, then solve the left side and the right side separately. That is O(n^2) in the worst case, when the bars are already in order. Worth naming, not worth writing.
One thing to volunteer: say "every rectangle has a shortest bar, so for each bar I ask how far it can reach" before writing anything. That change of view is the whole solution.
Next: 4.9 Linked List Problems. We leave arrays behind for careful pointer work: dummy heads, slow and fast pointers, and the reversal that half of those problems are built from.