These are the notes for DSA episode 28, one of the most famous hard stack problems. Given the heights of bars that stand side by side, find the largest rectangle that fits inside them. The obvious way gives every bar its own rectangle and stretches it left and right: on 2 lakh equal bars that is O(n²) and it times out. The fix: a bar's rectangle stops at its previous smaller and next smaller bar, and a monotonic stack (episode 27) finds both for every bar in one pass. With a sentinel bar of height 0 at the end, the whole solution is O(n) time, O(n) space. Every program below was run in the SyntaxPilot compiler (8-second time limit), and the outputs shown are real.
The problem, in real life
A shop owners' association wants to paste one rectangular banner (a hoarding) across the fronts of a row of shops. Every shop is the same width; their heights are 2, 1, 5, 6, 2 and 3 floors. The banner must cover shops that stand next to each other, and it can't be taller than the shortest shop it covers, or part of it would hang in the air. The biggest banner goes over the shops of height 5 and 6: 5 floors × 2 shops = 10.
| On the street | In the code |
|---|---|
| A shop of height h | A bar h[i] of width 1 |
| The row of shops | The histogram (the heights array) |
| One banner over neighbouring shops | A rectangle over a range of bars [l, r] |
| The banner's height | The shortest bar in the range |
| The first shorter shop on each side | The previous smaller and next smaller bar (the "walls") |
Problem statement
Given an array heights where each bar has width 1, return the area of the largest rectangle in the histogram.
heights = [2, 1, 5, 6, 2, 3] → 10 (bars 5 and 6, at height 5)
heights = [2, 4] → 4
A rectangle over bars l..r has height min(h[l..r]) and width r - l + 1.
Edge cases: one bar ([5] → 5), all equal ([3, 3, 3, 3] → 12), increasing ([1, 2, 3, 4, 5] → 9), decreasing ([5, 4, 3, 2, 1] → 9). Constraints are usually up to 10⁵ bars, so O(n²) is too slow.
Brute force: give every bar its own banner
The best rectangle has some shortest bar in it. So try every bar i as the shortest: its rectangle is h[i] tall, and it stretches left and right while the neighbours are at least as tall.
static int brute(int[] h) {
int n = h.length, best = 0;
for (int i = 0; i < n; i++) {
int l = i, r = i;
while (l > 0 && h[l - 1] >= h[i]) l--;
while (r < n - 1 && h[r + 1] >= h[i]) r++;
best = Math.max(best, h[i] * (r - l + 1));
}
return best;
}
On the two examples it printed 10 and 4. Correct.
The big input: 2 lakh bars
200000 bars, all of height 1 (Arrays.fill(h, 1)): Time Limit Exceeded.
Why the brute force fails
When all bars are equal, every bar stretches across the whole street: n steps for each of n bars, O(n²).
| Bars | Steps (about n²) |
|---|---|
| 1,000 | 10 lakh |
| 20,000 | 40 crore |
| 2,00,000 | 4 × 10¹⁰: TLE |
Each bar re-walks the street to learn what its neighbour just learned. But look at where each walk stops: on the left at the first shorter bar (the previous smaller bar) and on the right at the first shorter bar (the next smaller bar). Finding the next smaller or next greater element for every position in one pass is exactly what the monotonic stack did in episode 27.
The key insight: a shorter bar finishes every taller bar
Keep a stack of indices whose heights increase from bottom to top (a monotonic stack). Walk the bars left to right:
- While bars get taller, push them: nobody's rectangle has ended yet.
- When bar
iis shorter than (or equal to) the bar on top, bariis the top's next smaller bar: the top's rectangle can't go past here. Pop it and finish its rectangle now. - After popping, the new top is shorter than the popped bar: it is the popped bar's previous smaller bar, its left wall. If the stack is empty, there is no wall: use
-1. - The rectangle sits strictly between the two walls:
width = i - left - 1,area = height × width. - Sentinel: bars still in the stack at the end never met a shorter bar. Pretend there is one more bar of height 0 at index n. It is shorter than everything, so it pops (and measures) every remaining bar.
Popping on >= (not just >) is fine: an equal bar's rectangle is measured later by the last of the equal bars, which reaches further left.
Dry run on [2, 1, 5, 6, 2, 3] with the sentinel 0 at index 6:
| i | h[i] | Pops (height × width) | Stack after (indices) | best |
|---|---|---|---|---|
| 0 | 2 | none | [0] | 0 |
| 1 | 1 | 2 × (1 − (−1) − 1) = 2 | [1] | 2 |
| 2 | 5 | none | [1, 2] | 2 |
| 3 | 6 | none | [1, 2, 3] | 2 |
| 4 | 2 | 6 × (4 − 2 − 1) = 6, then 5 × (4 − 1 − 1) = 10 | [1, 4] | 10 |
| 5 | 3 | none | [1, 4, 5] | 10 |
| 6 | 0 (sentinel) | 3 × 1 = 3, 2 × (6 − 1 − 1) = 8, 1 × (6 − (−1) − 1) = 6 | [6] | 10 |
Every index is pushed once and popped once.
The optimal solution in Java
import java.util.*;
public class Main {
static int largest(int[] h) {
Deque<Integer> st = new ArrayDeque<>();
int best = 0;
for (int i = 0; i <= h.length; i++) {
int cur = (i == h.length) ? 0 : h[i];
while (!st.isEmpty() && h[st.peek()] >= cur) {
int height = h[st.pop()];
int left = st.isEmpty() ? -1 : st.peek();
int width = i - left - 1;
best = Math.max(best, height * width);
}
st.push(i);
}
return best;
}
public static void main(String[] args) {
System.out.println(largest(new int[]{2, 1, 5, 6, 2, 3}));
System.out.println(largest(new int[]{2, 4}));
System.out.println(largest(new int[]{5}));
System.out.println(largest(new int[]{3, 3, 3, 3}));
System.out.println(largest(new int[]{1, 2, 3, 4, 5}));
System.out.println(largest(new int[]{5, 4, 3, 2, 1}));
}
}
Output:
10
4
5
12
9
9
ArrayDeque used with push, pop and peek is Java's recommended stack (faster than the old Stack class). On the 2 lakh bars of height 1 it printed area 200000 in a few milliseconds (34 ms in our run).
The same solution in C++
#include <bits/stdc++.h>
using namespace std;
long long largest(const vector<int>& h) {
stack<int> st;
long long best = 0;
int n = h.size();
for (int i = 0; i <= n; i++) {
int cur = (i == n) ? 0 : h[i];
while (!st.empty() && h[st.top()] >= cur) {
int height = h[st.top()]; st.pop();
int left = st.empty() ? -1 : st.top();
best = max(best, (long long)height * (i - left - 1));
}
st.push(i);
}
return best;
}
int main() {
vector<vector<int>> tests = {{2, 1, 5, 6, 2, 3}, {2, 4}, {5}, {3, 3, 3, 3}, {1, 2, 3, 4, 5}, {5, 4, 3, 2, 1}};
for (auto& t : tests) cout << largest(t) << "\n";
}
Output: the same six lines as Java. In C++ st.pop() returns nothing, so read st.top() first. The long long avoids overflow (bug 3 below).
The same solution in Python
def largest(h):
st = [] # indices, heights increasing
best = 0
n = len(h)
for i in range(n + 1):
cur = 0 if i == n else h[i] # sentinel 0 at the end
while st and h[st[-1]] >= cur:
height = h[st.pop()]
left = st[-1] if st else -1
best = max(best, height * (i - left - 1))
st.append(i)
return best
for t in ([2, 1, 5, 6, 2, 3], [2, 4], [5], [3, 3, 3, 3], [1, 2, 3, 4, 5], [5, 4, 3, 2, 1]):
print(largest(t))
Output: the same six lines as Java. A Python list is the stack (append / pop / [-1]), and Python integers never overflow.
Three real bugs
Bug 1: no sentinel (i < h.length)
The loop stops at the last bar. On the example it still printed 10 (by luck: bar 2 at index 4 popped the 6 and the 5), but on [1, 2, 3, 4, 5] it printed 0: increasing bars are never popped, so their rectangles are never measured. Fix: loop to i <= h.length with cur = 0 at the end.
Bug 2: width = i - left
On the example it printed 15 instead of 10: when height 5 was popped, it got width 3 and "covered" the bar of height 1. Both i and left are walls (shorter bars the rectangle can't include), so width = i - left - 1.
Bug 3: int overflow when heights are huge
100000 bars of height 50000: the real answer is 5,000,000,000, but height * width overflows int (max 2,147,483,647) and the program printed 2147450000. On LeetCode 84 (heights ≤ 10⁴, n ≤ 10⁵) int is enough; when a problem allows bigger values, use long best and (long) height * width.
Also seen: int left = st.peek(); without the empty check throws
Exception in thread "main" java.lang.NullPointerException: Cannot invoke "java.lang.Integer.intValue()" because the return value of "java.util.Deque.peek()" is null
because peek() on an empty ArrayDeque returns null, and unboxing null into an int fails.
Complexity
| Approach | Time | Extra space | 2 lakh bars of height 1 |
|---|---|---|---|
| All pairs (l, r) with a running minimum | O(n²) | O(1) | Time Limit Exceeded |
| Stretch every bar left and right | O(n²) worst case | O(1) | Time Limit Exceeded |
| Divide and conquer on the minimum | O(n log n) average, O(n²) sorted input | O(log n) to O(n) | risky |
prevSmaller[] + nextSmaller[] arrays |
O(n) | O(n) | fast |
| One-pass monotonic stack + sentinel | O(n) | O(n) | milliseconds |
The while loop looks nested, but every index is pushed once and popped at most once, so the total work is about 2n.
Common mistakes
| Mistake | What you see | Why | Fix |
|---|---|---|---|
i < h.length (no sentinel) |
0 for [1, 2, 3, 4, 5] |
bars left in the stack are never measured | loop to i <= n with height 0 |
width = i - left |
15 instead of 10 |
both walls are outside the rectangle | width = i - left - 1 |
int best, height * width with huge heights |
2147450000, not 5000000000 |
int overflows past 2.1 billion |
long best, (long) height * width |
left = st.peek() on an empty stack |
NullPointerException ... peek() is null |
empty ArrayDeque.peek() returns null |
st.isEmpty() ? -1 : st.peek() |
| Pushing heights instead of indices | wrong widths | you need positions to measure width | push i, read h[i] |
| Stretching every bar | TLE on 2 lakh bars | O(n²) | monotonic stack |
Mini project: the biggest hoarding on your street
Write the heights of the shops on a street in an array and print the best banner: its area and which shops it covers. Track the left and right index whenever best improves: when a popped bar gives a bigger area, the banner covers shops left + 1 to i - 1. For {3, 7, 7, 8, 2, 6, 6, 5, 1} the program prints [21, 1, 3]: area 21, shops 1 to 3 at height 7. Extension: also print the banner's height, and draw the street with # characters.
Practice
- Maximal rectangle of 1s in a binary matrix (LeetCode 85).
Solution
Each row is the floor of a histogram: h[j] = number of consecutive 1s ending at this row in column j. Run largest on every row.
static int maximalRectangle(char[][] m) {
if (m.length == 0) return 0;
int[] h = new int[m[0].length];
int best = 0;
for (char[] row : m) {
for (int j = 0; j < row.length; j++) h[j] = row[j] == '1' ? h[j] + 1 : 0;
best = Math.max(best, largest(h));
}
return best;
}
For the matrix 10100 / 10111 / 11111 / 10010 it prints 6. O(rows × cols).
- Write it with two arrays:
prevSmaller[]andnextSmaller[].
Solution
Two monotonic-stack passes (episode 27), one from each side; the width is next[i] - prev[i] - 1.
static int twoArrays(int[] h) {
int n = h.length;
int[] prev = new int[n], next = new int[n];
Deque<Integer> st = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
while (!st.isEmpty() && h[st.peek()] >= h[i]) st.pop();
prev[i] = st.isEmpty() ? -1 : st.peek();
st.push(i);
}
st.clear();
for (int i = n - 1; i >= 0; i--) {
while (!st.isEmpty() && h[st.peek()] >= h[i]) st.pop();
next[i] = st.isEmpty() ? n : st.peek();
st.push(i);
}
int best = 0;
for (int i = 0; i < n; i++) best = Math.max(best, h[i] * (next[i] - prev[i] - 1));
return best;
}
[2, 1, 5, 6, 2, 3] → 10.
- Return the left and right index of the best rectangle.
Solution
static int[] where(int[] h) {
Deque<Integer> st = new ArrayDeque<>();
int best = 0, bl = 0, br = -1;
for (int i = 0; i <= h.length; i++) {
int cur = (i == h.length) ? 0 : h[i];
while (!st.isEmpty() && h[st.peek()] >= cur) {
int height = h[st.pop()];
int left = st.isEmpty() ? -1 : st.peek();
if (height * (i - left - 1) > best) { best = height * (i - left - 1); bl = left + 1; br = i - 1; }
}
st.push(i);
}
return new int[]{best, bl, br};
}
[2, 1, 5, 6, 2, 3] → [10, 2, 3].
- Largest square instead of rectangle.
Solution
When a bar is popped, its rectangle is height tall and width wide; the biggest square inside it has side min(height, width).
int side = Math.min(height, i - left - 1);
best = Math.max(best, side * side);
[2, 1, 5, 6, 2, 3] → 4; [4, 4, 4, 4, 1] → 16.
Quick quiz
System.out.println(largest(new int[]{4, 2, 0, 3, 2, 5}));
5684
Answer
6. The 0 splits the street. On the right, bars 3, 2, 5 (indices 3 to 5) at height 2 give 2 × 3 = 6, which beats the single 5. On the left, 4 and 2 give at most 4. (Real output: 6.)
Interview questions
- Largest rectangle in a histogram in O(n). Monotonic stack of indices with increasing heights; a shorter bar pops the taller ones; for each popped bar,
width = i - newTop - 1(oriif the stack is empty); a sentinel 0 at the end flushes the stack. - Why is it O(n) when there's a loop inside a loop? Each index is pushed once and popped at most once: at most 2n stack operations in total (amortised analysis).
- Why push indices and not heights? The width needs positions; the height can always be read back from
h[index]. - What does the sentinel do? It is a fake bar of height 0 after the end; it is shorter than every bar, so every remaining index gets popped and measured.
>=or>when popping? Both give the right answer. With>=, the earlier of two equal bars is measured short, but the later one covers the full width.- How do you solve "maximal rectangle" in a 0/1 matrix? Build a histogram per row (consecutive 1s above each cell) and run this algorithm on every row.
- How is this related to "next greater element"? It is the same stack pattern looking for the next smaller element, plus reading the previous smaller element from the stack below.
- When does the answer overflow
int? Whenmax height × nexceeds about 2.1 × 10⁹; uselong.
Glossary
| Term | Meaning |
|---|---|
| Histogram | A bar chart whose bars have width 1 and stand side by side with no gaps |
| Rectangle in a histogram | A range of neighbouring bars [l, r], as tall as its shortest bar |
| Previous smaller bar | The nearest bar to the left that is shorter: the rectangle's left wall |
| Next smaller bar | The nearest bar to the right that is shorter: the rectangle's right wall |
| Stack | A pile where you add (push) and remove (pop) only at the top: last in, first out |
| Monotonic stack | A stack whose values stay sorted (here: heights increasing from bottom to top) |
| Sentinel | A fake value added at the end (height 0) to force a final clean-up |
ArrayDeque |
Java's double-ended queue; with push / pop / peek it is the recommended stack |
peek() |
Look at the top of the stack without removing it (null if empty, in ArrayDeque) |
| Amortised O(n) | The total work over the whole run is O(n), even if one step does more |
| Integer overflow | A result bigger than the type can hold wraps around to a wrong number |
| Time Limit Exceeded (TLE) | Too slow for the judge's limit (8 s in the SyntaxPilot compiler) |
Summary
- A rectangle's height is its shortest bar; stretching every bar left and right is O(n²) and times out on 2 lakh bars.
- Every bar's rectangle ends at its previous smaller and next smaller bar. A monotonic stack (increasing heights) finds both: a shorter bar pops the taller ones, the new top is the left wall,
width = i - left - 1. - A sentinel height 0 at index n flushes the stack. O(n) time, O(n) space; use
longwhen heights are huge.
Next episode: Min stack and evaluating reverse Polish notation.