The problem
Each number is the height of a bar of width 1 in a histogram. Find the area of the largest rectangle that fits entirely inside the bars.
Input: [2, 1, 5, 6, 2, 3] Output: 10 (height 5 across the bars 5 and 6)
Picture it
Picture a city skyline and a billboard you want to paste flat against it. The billboard can be as tall as the shortest building it spans. We keep a stack of buildings in increasing height. When a shorter building arrives, taller buildings on the stack can’t stretch any further right, so we pop them and measure the biggest billboard each could support.
How to recognise it
- You want the best contiguous range, and its value is (smallest item in the range) × (length of the range).
- For each bar, the widest rectangle at exactly its height stretches until the nearest shorter bar on each side. "Nearest smaller element to the left and right" is the classic job of a monotonic stack (a stack kept in sorted order).
- Up to 10^5 bars, so checking every range is too slow.
Start with brute force
Fix the left edge i, then move the right edge j outward while tracking the lowest bar seen so far. Each range's best rectangle is that minimum times the width.
def largest_brute(h):
best = 0
for i in range(len(h)):
low = h[i]
for j in range(i, len(h)):
low = min(low, h[j])
best = max(best, low * (j - i + 1))
return best
There are about n²/2 ranges, each updated in O(1), so time is O(n²) and space is O(1). For n = 10^5 that is about 5 × 10^9 steps.
From brute force to the idea
- Find the waste. The best rectangle always has the height of some bar, and it spans the full stretch where that bar is the shortest. So only n candidates matter, one per bar, but the brute force tries n²/2 ranges.
- Ask where each bar's stretch ends. Bar
kcan extend right until the first shorter bar, and left until the first shorter bar before it. - Keep a rising stack. Walk left to right with a stack of positions whose heights rise from bottom to top. Each bar on the stack is still waiting to learn where its stretch ends on the right.
- A lower bar closes stretches. When bar
iwith heightxarrives, every stacked bar at least as tall asxcannot extend pasti. Pop it: its right end isi - 1, and its left end is just after the bar now below it in the stack (stack[-1] + 1), or 0 if the stack is empty. Its area isheight * (i - left). - Flush with a sentinel.
h + [0]adds a zero-height bar at the end, which pops everything still waiting. This builds a new list, so the caller'shis not changed. - Equal heights are fine. With
>=, equal bars pop each other and the earlier ones get too small a width, but the last of the run is measured across the whole run, so the maximum is still found.
This is the key idea: a rising stack tells each bar, at the moment it is popped, exactly how far it can stretch left and right.
The key idea
Monotonic increasing stack: when a bar is popped, the current index is its right limit and the new stack top is its left limit. O(n).
Python solution
def largest_rectangle(h):
stack, best = [], 0 # positions with rising heights
for i, x in enumerate(h + [0]):
while stack and h[stack[-1]] >= x:
height = h[stack.pop()]
left = stack[-1] + 1 if stack else 0
best = max(best, height * (i - left))
stack.append(i)
return bestIn the interactive version each line lights up as the animation runs, and you can type your own input to see the algorithm handle it.
Complexity
| Approach | Time | Space |
|---|---|---|
| Brute force | O(n²): every left edge with every right edge | O(1): a running minimum |
| Monotonic stack (shown code) | O(n): each position is pushed once and popped once | O(n): the stack, plus the copy made by h + [0] |
Edge cases
- Empty list: returns 0 (only the sentinel is pushed). LeetCode promises at least one bar.
- One bar (
[4]): returns 4. - All equal (
[3, 3, 3]): returns 9; the last 3 is popped by the sentinel with left edge 0. - Rising (
[1, 2, 3, 4, 5]): nothing is popped until the sentinel arrives; returns 9 (height 3, width 3). - Falling (
[5, 4, 3, 2, 1]): every bar is popped by the next one; returns 9. - Zero-height bars (
[2, 0, 2]): the 0 splits the histogram; returns 2.
Common mistakes
- Forgetting the sentinel. Bars still on the stack at the end are never measured, so
[1, 2, 3]returns 0. - Measuring the width as
i - popped_index. The rectangle also extends left of the popped bar, back to the bar below it in the stack. - Storing heights instead of positions on the stack, so the width cannot be computed.
- Appending the sentinel with
h.append(0), which changes the caller's list.
Given a grid of "0" and "1" cells, find the area of the largest rectangle made only of "1" cells. Describe your approach, then write it if you like.
Compare with our answer
Treat each row as the floor of a histogram. For every column, the bar height is the number of consecutive "1" cells ending at this row (reset to 0 on a "0"). Any all-ones rectangle has its bottom edge on some row, so the answer is the largest histogram rectangle over all rows.
def maximal_rectangle(grid):
if not grid:
return 0
heights = [0] * len(grid[0])
best = 0
for row in grid:
for c, cell in enumerate(row):
heights[c] = heights[c] + 1 if cell == "1" else 0
best = max(best, largest_rectangle(heights))
return best
For R rows and C columns: time O(R · C), space O(C).
A strong answer mentions: how the heights are updated row by row, why every all-ones rectangle is found from its bottom row, and that it reuses the histogram routine unchanged.
1. Given a list of daily rainfall, you must find the longest run of days multiplied by the lowest rainfall in that run. Which approach fits best?
"Minimum × width over a range" is the histogram problem: each day's best run ends at the nearest lower days, found with a monotonic stack in O(n). The score is not monotone as a window grows, so a sliding window fails, and sums are not minimums.
2. When a bar is popped, why is its left edge stack[-1] + 1 rather than its own position?
Bars between them were popped earlier by something no taller than they are, so they are at least as tall as the popped bar and the rectangle can extend over them. The bar below in the stack is not taller (the stack rises), which is exactly why the rectangle stops there.
3. A learner loops over enumerate(h) instead of enumerate(h + [0]). Which input now gives a wrong answer?
A rising histogram never pops anything without the sentinel, so the function returns 0. In the other inputs the best rectangle is measured when a lower bar arrives, before the loop ends.
Score 60% or more and the lesson is marked complete.