Sliding Window Extrema

In short: a monotonic stack only ever removes from one end, which is fine until old items need to expire out of a sliding window whether or not anything beat them. A deque gives a second exit: new arrivals evict dominated items from the back, and the front is evicted when it slides out of the window. What's left is always sorted, so the front is always the window's max (or min) — and every index enters and leaves once, so the whole scan is O(n) no matter how big the window is.

A deque holding 60, 30, 20 (decreasing front to back): 60 expires off the front when the window slides, and an arriving 50 evicts 30 and 20 from the back because both are weaker and now older

Quarry's live dashboard draws a band under its latency graph: for the last k requests, the fastest and the slowest. Every new request shifts the window by one, so the band has to be recomputed for every request. Rescanning the window each time costs O(k) per request and O(n·k) for a trace. With k = 1000 and a busy engine, that's a thousand comparisons for every request served, just to draw a line.

The previous lesson's stack answered "who is the next bigger one?" because items only ever left from the top. A window needs a second exit: old requests expire off the far end whether or not anything beat them. A structure with two exits is a deque, and a deque kept in sorted order is a monotonic deque.

Three moves, one invariant

You met the sliding-window maximum briefly in the queues lesson. Here is the idea again, stated so it can be reused. Keep a deque of indices whose latencies decrease from front to back. For each new request i:

Evict from the back every index whose latency is less than or equal to the new one. While the new request is in the window, those can never be the maximum, because it is at least as slow and it will stay longer.
Push i onto the back.
Evict from the front if the front index has slid out of the window, which is when it is <= i - k.

After those moves the front is the window's maximum. It's the oldest survivor, and everything behind it is smaller.

python

Watch the deque on that trace. The front, on the left, is always the answer:

watch it move · stack

New requests evict weaker ones from the back, and time evicts old ones from the front. What's left is always sorted, so the front is the window's worst request.

Request 0 enters an empty deque. Deque, 1 item. Head is 40 (#0), tail is 40 (#0).

1 / 10

Each index enters the deque once and leaves at most once, from one end or the other, so the whole pass is O(n) whatever k is.

Why one variable isn't enough

The first idea most people try is a single peak variable: when a request arrives, peak = max(peak, ms). That works perfectly for a window that only grows. It breaks the moment the peak expires. When the 60 ms request slides out of the window, what is the new peak? The variable has forgotten everything below 60, so the only way to find out is to rescan the window, and you're back to O(k).

The deque is the smallest amount of memory that avoids the rescan. It keeps the peak, plus the request that would become the peak if the current one expired, plus the one after that, and nothing else. Every index it drops is one that can provably never be a peak: something newer and at least as slow is already in the window and will outlast it. That's the same domination argument as the monotonic stack. The only new part is the second exit.

❓ Cross-question — "Why do the back evictions happen before the front check?" The order doesn't change the answer, because the new index is never the one that expires. What matters is that both happen before you read the front. Read it too early and a request that has just slid out of the window can still be reported as the peak for one extra step.

Coming from Java/JS: Java's ArrayDeque<Integer> has peekFirst, peekLast, pollFirst, pollLast and offerLast, which is everything this lesson needs. JavaScript has no built-in deque. Use an array plus a head index that moves forward instead of calling shift(), which is O(n).

What does this print?

from collections import deque
trace = [5, 1, 3, 2, 4]
dq = deque()
for i, ms in enumerate(trace):
    while dq and trace[dq[-1]] <= ms:
        dq.pop()
    dq.append(i)
print([trace[j] for j in dq])

Your turn to drive: the window minimum

For the fastest request, flip every comparison: the deque's latencies increase from front to back, and a new request evicts everything at the back that is slower than or equal to it. Run this and scrub through it. Then change k, or change >= to >, and watch what the deque keeps.

your code, drawn · stack

The same three moves with the comparison flipped. The deque increases from front to back, so its front is the window's fastest request.

Ties: `<` or `<=` at the back?

For the maximum, popping on <= keeps only the newest of several equal values. Popping on < keeps all of them. Both give the right peaks, but they hold different amounts:

What does this print?

from collections import deque
trace = [7, 7, 7, 7]
dq = deque()
for i, ms in enumerate(trace):
    while dq and trace[dq[-1]] < ms:
        dq.pop()
    dq.append(i)
print(len(dq))

Prefer <=. The newest equal value is the one that expires last, so it is the only one worth keeping, and a smaller deque means less work at the front.

Two deques: the band

The dashboard needs the fastest and the slowest. Those are two independent deques over the same indices, one decreasing (for the maximum) and one increasing (for the minimum). Each does its own three moves, and both fronts are read after every full window. That's the piece you build in this lesson.

The front-eviction check is the easiest thing to get wrong:

broken — fix it

The windows of size 2 are [9, 1], [1, 1] and [1, 1], so the peaks are [9, 1, 1]. This prints [9, 9, 1] because 9 stays one request too long.

Windows measured in time

Real dashboards don't say "the last 1000 requests". They say "the last five seconds". Now the window's size in requests changes all the time, and several old requests can expire at once when a burst arrives after a quiet spell. The front eviction becomes a while:

step through it

1from collections import deque

2events = [[0, 40], [2, 90], [3, 50], [7, 60], [12, 30]]

3span = 5

4dq = deque()

5peaks = []

6for t, ms in events:

7 while dq and dq[-1][1] <= ms:

8 dq.pop()

9 dq.append((t, ms))

10 while dq[0][0] <= t - span:

11 dq.popleft()

12 peaks.append(dq[0][1])

13print(peaks)

Step to the event at time 12: the while evicts the request at time 7, and 30 ms is alone in the window. Storing (time, value) pairs instead of indices is the usual trick once positions stop mattering.

How many indices does the deque hold?

In the worst case, a trace that keeps getting faster, the deque holds all k indices. On a trace in random order it holds far fewer: an index survives only if nothing after it in the window is slower. On average that's about $\ln k + 0.58$ indices:

window `k`	typical deque size
10	2.9
100	5.2
1,000	7.5
5,000	9.1

The deque grows like a logarithm: it takes a window of about 1,670 requests before it typically holds 8 indices. So on ordinary traffic even a huge window keeps only a handful of candidates, while the rescanning approach would still look at all k requests every time.

Interview problem: the shortest growth burst

Monotonic deques also work on prefix sums, and that is where they solve problems nothing simpler can.

Shortest growth burst. Quarry logs deltas: the change in stored bytes at each tick, which can be negative when compaction frees space. Return the length of the shortest run of consecutive ticks whose total growth is at least target, or -1 if no run gets there.

Constraints: 0 ≤ n ≤ 10⁵, −10⁹ ≤ deltas[i] ≤ 10⁹. Aim for O(n).

Examples:

shortest_burst([4, -6, 3, 5, -1, 6], 10) → 3, from [5, -1, 6]

shortest_burst([1, 2], 10) → -1

With only positive deltas this is the two-pointer window you already know: grow the right edge, and shrink the left while the sum is still big enough. Negative deltas break that, because shrinking can make the sum bigger. So work with prefix sums P, where a run from a to b - 1 grows by P[b] - P[a]. For each b you want the latest a with P[a] <= P[b] - target. Keep a deque of candidate starts with increasing prefix sums:

from the front: while the front start already works for this b, record the length and pop it, since no later b could give it a shorter run;
from the back: pop any start whose prefix sum is at least P[b], because b is a later start that is at least as good.

That's the boss exercise. The capstone uses a deque a third way, inside a dynamic program: when best[i] is score[i] plus the best of the previous k answers, "the best of the previous k" is a sliding-window maximum.

What it costs

operation	cost
max or min of every window of size k	O(n) total, O(k) memory
both at once (two deques)	O(n) total
rescanning each window	O(n·k)
a heap with lazy deletion	O(n log n)
time-based windows	O(n) total, as each event enters and leaves once

Idioms & real-world patterns

Store indices (or timestamps), not values, so you can tell when the front has expired.
Back pops for domination, front pops for expiry. If you ever pop from the front for any other reason, stop and check the invariant.
while at the front for time windows, if for count windows, where exactly one index can expire per step.
Where it shows up: monitoring dashboards (rolling max and min latency), trading systems (rolling highs and lows), network congestion control, and dynamic programs with a "best of the last k" step.

⚡ Advanced — why not a heap?

A max-heap of (latency, index) also gives window maxima: push every request, and before reading the top, pop any entry whose index has expired. It is correct and O(n log n), and it works when you need things a deque can't do, such as the second largest in the window. But the deque is O(n), uses less memory on ordinary traffic, and never holds a stale entry. Reach for the heap only when the question isn't just "the biggest".

python

Quick practice

What does this print?

from collections import deque

def window_peaks(trace, k):
    dq = deque()
    peaks = []
    for i, ms in enumerate(trace):
        while dq and trace[dq[-1]] <= ms:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            peaks.append(trace[dq[0]])
    return peaks

print(window_peaks([10, 50, 20, 70, 30, 15], 2))

broken — fix it

The window minimums should be [10, 20, 20, 30, 15]. This prints [50, 50, 70, 70, 30] — the maxima — because the back-eviction comparison is still the one from a decreasing (maximum) deque.

🎯 Your turn

Build window_band(latencies, k) for Quarry's live dashboard: for every full window of k consecutive requests, return [fastest, slowest]. Return [] if k is less than 1 or longer than the trace.

window_band([4, 2, 12, 3, 8], 3) → [[2, 12], [2, 12], [3, 12]]
window_band([5], 1) → [[5, 5]]

Hint: two deques of indices, one increasing for the minimum and one decreasing for the maximum. Each does its own back and front evictions.

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. ✅

Sliding Window Extrema

Sliding Window Extrema

Three moves, one invariant

Why one variable isn't enough

Your turn to drive: the window minimum

Ties: < or <= at the back?

Two deques: the band

Windows measured in time

How many indices does the deque hold?

Interview problem: the shortest growth burst

What it costs

Idioms & real-world patterns

⚡ Advanced — why not a heap?

Quick practice

🎯 Your turn

Practice — level up

Ties: `<` or `<=` at the back?