Monotonic Stacks & Next Greater
In short: keep a stack of items still waiting for an answer, in sorted order. When a new value arrives, pop everyone it beats — each popped item is dominated: something nearer and at least as extreme has shown up, so it can never be the answer for anything later. Every item is pushed once and popped at most once, so the whole scan is O(n) even though there's a loop inside a loop. One structure answers next-greater, next-smaller, previous-greater and previous-smaller — the only choice is which side records the answer and whether ties pop.
From here on the course builds Quarry, a search-and-storage engine: the kind of program that sits under a search box or an analytics dashboard, stores records, indexes them and answers queries about them. This section builds Quarry's query planner, the part that reads what the engine has been doing and decides what to do next. Its raw material is a latency trace: one number per request, the milliseconds that request took, in the order the requests arrived.
The worst request is easy. The planner's real questions are about neighbours: after this slow request, how long until an even slower one? Before it, where was the last faster one? Over how wide a stretch was this request the slowest thing happening? Asked naively, each question scans outwards from every request, and a trace of n requests costs O(n²). This lesson answers all of them in O(n) with one structure.
A quick recap, and what changes now
In the stacks lesson you met next_greater: walk left to right, keep a stack of
indices still waiting for a bigger value, and let each new value answer every
smaller one on top. The stack's values only ever decrease from bottom to top, so it
is called a monotonic stack.
That was one question. There are really four, and they all use the same loop:
| question | scan | pop the top while it is… |
|---|---|---|
| next greater (first later value that is bigger) | left to right | smaller than the new value |
| next smaller | left to right | bigger than the new value |
| previous greater (last earlier value that is bigger) | left to right, read the top after popping | smaller than or equal to the new value |
| previous smaller | left to right, read the top after popping | bigger than or equal to the new value |
The first two record an answer when an item is popped: the arrival that pops it is its answer. The last two record an answer when an item is pushed: after the pops, whatever is left on top is the nearest earlier item that survived, and that survivor is the answer.
Why is it safe to throw 40 away when 30 arrives? Any later value that 40 is
smaller than, 30 is smaller than too, and 30 is nearer. 40 can never again be
the nearest smaller value to anything. That argument, "this item is dominated
and can never be an answer again", is the whole technique. Every monotonic stack
you write should come with one sentence saying why the popped item is useless.
❓ Cross-question — "Couldn't I just sort the trace and look things up?" Sorting throws away the one thing these questions are about, which is position. "The nearest faster request before this one" depends on what is near, not only on what is faster. A sorted copy tells you which values are smaller but not which of them is closest, and recovering that costs more than the stack's single pass. A monotonic stack keeps both orders at once: it is ordered by position because you push in arrival order, and ordered by value because you pop anything that breaks the sort.
Coming from Java/JS: in Java, use an
ArrayDeque<Integer>withpush,popandpeek, or a plainint[]with a top index for speed. In JavaScript an array withpush,popandat(-1)is the idiom.
lat = [40, 30, 35, 10, 50]
st, out = [], []
for x in lat:
while st and st[-1] >= x:
st.pop()
out.append(st[-1] if st else -1)
st.append(x)
print(out)Watching the stack reach both ways
Take the planner's question about reach: over how wide a stretch of requests,
containing request i, was request i the slowest? The stretch ends just before
the first request on the right that is strictly slower, and just after the
first one on the left that is strictly slower. So reach needs a next-greater
pass and a previous-greater pass.
Here is the rightward pass on the trace above. Watch the two counters in the note:
every request is pushed once, and most are popped once. The inner while never
does more work in total than the pushes paid for.
Each pop is a request finding the first slower request to its right. Pushes and pops are both capped at n, so the whole pass is O(n) even with a loop inside a loop.
Request 0 has nothing to compare with yet, so it waits. Stack, 1 item. Top is 120 ms (#0).
pushes=1 pops=0
Now drive it yourself. This is the same pass drawn on the trace instead of the
stack: waiting requests are highlighted as candidates, and requests whose right
edge is known are done. Change < to <= and run it again to see what ties do.
Every request is pushed once and popped at most once. Change the comparison to <= and the second 60 will end the first one's stretch.
Ties decide what "strictly" means
Duplicates are where monotonic stacks go wrong, and there's no clever fix, only a
decision. Popping on < means an equal value does not end a stretch. Popping on
<= means it does.
trace = [60, 60, 60]
right = [3, 3, 3]
waiting = []
for i, ms in enumerate(trace):
while waiting and trace[waiting[-1]] <= ms:
right[waiting.pop()] = i
waiting.append(i)
print(right)For reach, the definition says strictly slower, so both passes pop on <: three
equal 60s each reach across all three. For some problems you will want < on one
side and <= on the other. That comes up at the end of this lesson.
How much work does the naive way do?
The brute-force way scans right from every request until it finds a slower one. On
a trace where a spike arrives every s requests, each scan walks about s / 2
requests, so the whole thing costs about n · s / 2. The stack never does more
than 2n pushes and pops. The ratio is (s/2) / 2 = s/4: spikes 20 requests apart cost
the brute force 5 times the stack's work, and spikes 100 apart cost it 25 times. The
stack's cost doesn't depend on s at all, because each request is pushed once and
popped at most once however the trace is shaped.
That independence is the point. You can't tune the brute force out of trouble, because its cost depends on the data. The stack's doesn't.
trace = [9, 8, 7, 6, 5, 10]
stack, pops = [], 0
for x in trace:
while stack and stack[-1] < x:
stack.pop()
pops += 1
stack.append(x)
print(pops)The biggest block of free pages
Quarry stores data in segments laid side by side, and each segment has some number of free pages. A big import needs a rectangular allocation: the same number of pages in each of several consecutive segments. The largest block is the best choice of stretch times the smallest free count inside it.
Think about each segment as the shortest one in the block. It can stretch left
and right until it meets a segment with fewer free pages, which is a
previous-smaller and a next-smaller question. You can answer both in one pass: when
a segment is popped, the arrival that popped it is its right wall, and the item
beneath it on the stack is its left wall. Carry the left wall along as a start
index so nothing needs recomputing:
The trailing 0 matters. Without it, bars that were never popped are never
measured:
The biggest block is 5 pages across the last two segments, which is 10. This prints 9.
Keeping the smallest key: a greedy stack
Monotonic stacks also solve greedy problems where you're allowed to throw a few
things away. Quarry shortens shard keys by deleting exactly k characters, keeping
the rest in order, and it wants the result that sorts first. Walk the key, and while
the character on top of the stack is bigger than the incoming one and you still
have deletions left, delete it. A smaller character earlier always beats anything
that comes after it.
Step through it: a removes u and then q, which uses up both deletions. If the
key had been sorted already, nothing would pop, and the last line would trim the
leftover deletions off the end, where they do the least harm.
Interview problem: spike reach
This is the piece of Quarry you build in this lesson.
Spike reach. You're given a latency trace
latencies, one whole number of milliseconds per request. For each requesti, return the length of the longest run of consecutive requests that includesiand contains no request strictly slower than requesti.Constraints: 0 ≤ n ≤ 10⁵ and 1 ≤
latencies[i]≤ 10⁹. Aim for O(n).Examples:
spike_reach([3, 1, 4, 1, 5])→[2, 1, 4, 1, 5]spike_reach([2, 2, 2])→[3, 3, 3], since equal requests don't cut each other offspike_reach([])→[]
The plan: one pass for right[i], the first index to the right that is strictly
slower (or n), and one for left[i], the nearest strictly slower index to the
left (or -1). The run is everything strictly between them, so its length is
right[i] - left[i] - 1.
What it costs
| operation | cost |
|---|---|
| next / previous greater or smaller for every item | O(n) time, O(n) stack |
| largest rectangle in a row of bars | O(n) |
| smallest subsequence after k deletions | O(n) |
| the same questions by scanning outwards | O(n²) in the worst case |
Idioms & real-world patterns
- Push indices, not values, whenever the answer is a distance or has to be written back to a position.
- State the domination argument in a comment above the
while. If you can't say why the popped item is useless, the stack is wrong. - Decide ties on purpose. Write
<or<=knowing which one the problem needs. - A sentinel flushes the stack. A
0(or-inf) at the end forces every waiting item to be measured. - Where it shows up: stock-style span reports, skyline and histogram layouts, compilers deciding operator precedence, and the greedy "smallest after removals" family.
⚡ Advanced — adding up over every window
The sum of max(window) over every window of a list sounds like O(n²) windows.
Count it the other way round instead: xs[i] is the maximum of exactly
(i - left[i]) * (right[i] - i) windows. When values repeat, a window's maximum
must be credited to one of the tied positions, so pop on < on one side and
<= on the other. Otherwise ties are counted twice or not at all.
The capstone exercise below uses the same idea twice.
Quick practice
def next_greater(xs):
out = [-1] * len(xs)
stack = []
for i, x in enumerate(xs):
while stack and xs[stack[-1]] < x:
out[stack.pop()] = x
stack.append(i)
return out
print(next_greater([3, 5, 2, 4, 1]))The first 2 (index 0) is strictly smaller than nothing until the 4 arrives, so its answer should be 4. This prints [2, 2, 4, -1, -1] — the first 2 is wrongly popped by the second 2, which is only equal, not greater.
🎯 Your turn
Build spike_reach(latencies) from the interview problem above: for each request,
the length of the widest run of consecutive requests around it with nothing
strictly slower.
spike_reach([3, 1, 4, 1, 5])→[2, 1, 4, 1, 5]spike_reach([2, 2, 2])→[3, 3, 3]
Hint: two monotonic-stack passes, one from each end, both popping on <. The
answer for i is right[i] - left[i] - 1.
Then press ▶ Run, tap the Live App try chips to call it with different inputs, and hit ✓ Check. Green = this piece of the app is built. ✅