Monotonic queue

Monotonic queues are not about finding the maximum. They are about deleting information that the future can never use.

A telemetry pipeline ingests 1,000,000 requests per second and you owe one continuous metric: the peak request latency over the last 30 seconds.

Recomputing the maximum from scratch costs $O(k)$ per sample — hopeless at high throughput. Reach for a max-heap and expired samples accumulate until they surface at the root: every query spends extra work popping stale entries, and every insertion still costs $O(\log k)$. Both approaches waste work paying to remember values that are already irrelevant.

The question becomes: how do we stop remembering values that can never matter again?

Canonical instance: Sliding Window Maximum. General form: maintain the optimum over a forward-moving window while discarding dominated candidates. Every optimization in this pattern follows from that single idea.

Recognition

1. ✓ The window only moves forward — slides right and never rewinds.
2. ✓ You need a continuous max or min, reporting an answer per step.
3. ✓ Recomputing from scratch feels wasteful ($O(nk)$ bottleneck).
4. ✓ Older candidates stop mattering forever once a better candidate appears behind them.

If all four are true, you’re usually looking for a monotonic deque.

Recognition tells you when to use the pattern.

Dominance explains why it works.

Dominance

Suppose element $A$ is older than element $B$, and $B$ is at least as large ($B \ge A$).

Ask yourself: can $A$ ever become the maximum again?

No. Any future window containing $A$ must also contain $B$. Because $B$ is both fresher and larger, no future window can ever select $A$ as its answer.

$A$ is permanently dead. Remove it immediately when $B$ arrives.

Window contains older A
         ↓
Window must contain newer B
         ↓
       B ≥ A
         ↓
Answer cannot be A

We call $A$ dominated by $B$ when:

1. $B$ comes after $A$ ($\text{index}(B) > \text{index}(A)$), and
2. $B \ge A$ (for a maximum).

Invariant

The deque is not the window. It is the frontier of undominated candidates.

Three invariants hold after every step:

• Candidate values are monotonic — strictly decreasing front→back for a maximum (each survivor is beaten by nothing behind it).
• Candidate indices are strictly increasing front→back (we only ever append the newest position).
• The front is the answer — the largest live candidate, and also the oldest, so it is the first to expire.

The Three Policy Decisions

The deque algorithm itself never changes. Only three policy decisions change per problem:

from collections import deque

def window_extreme(nums, k):
    dq = deque()                    # candidate indices, kept monotonic
    out = []
    for i, x in enumerate(nums):
        while dq and evict(dq, x):  # 1. Eviction policy (dominance rule)
            dq.pop()
        dq.append(i)                # 2. Storage policy (store index for expiry)
        if expired(dq, i, k):       # 3. Expiration policy (drop stale head)
            dq.popleft()
        if i >= k - 1:              # First full window reached
            out.append(nums[dq[0]])
    return out

• For Maximum: evict is nums[dq[-1]] <= x (newer, larger value dominates smaller tails); store index i; expired is dq[0] <= i - k.
• For Minimum: flip evict to nums[dq[-1]] >= x (newer, smaller value dominates larger tails).

Visual Walkthrough

Sliding-window maximum with $k = 3$ over 1 3 -1 -3 5 3 6 7. Band W is the active window; caret M is the front of the deque (the window’s max).

Why It Works

Correctness

1. Every dominated candidate is removed immediately upon a newer, better arrival.
2. Surviving candidates remain strictly ordered by value.
3. Expired candidates leave the front the moment they slide out of range.
4. Therefore, the front is always the largest remaining live candidate.

Complexity ($O(1)$ amortized)

A single arrival can evict multiple candidates in one step, which superficially looks superlinear.

Count by candidate lifecycle, not by step: every index is pushed once and popped at most once. Total queue operations over the entire stream $\le 2n = O(n)$ total time $\rightarrow$ $O(1)$ amortized per sample.

Why Not a Heap?

A heap answers “What is the largest value I’ve seen?” A monotonic deque answers “What is the largest value that is still relevant?”

Common Misconceptions

• Thinking the deque stores the window. The deque stores only undominated candidates. If a window has 1,000 strictly increasing elements, the deque holds exactly 1 element.
• Storing values instead of indices. Values reveal the extreme, but not when it expires. Without indices, the front cannot expire as the window slides.
• Mishandling equal values (< vs <=). < keeps duplicate equals; <= evicts older equals. Both yield the correct extreme, but <= keeps the deque smaller and refreshes the expiry position.
• Emitting prematurely. The first valid window of size $k$ ends at index $k - 1$. Only record when i >= k - 1.

The Bigger Idea: Permanent Dominance

Monotonic queues are one concrete instance of a broader algorithmic principle:

Discard choices that can never become optimal again.

The same idea powers:

• Monotonic stack: Pruning dominated elements in LIFO order for next-greater element and histogram area problems.
• Convex Hull Trick: Pruning dominated linear functions whose lines can never achieve the optimum for any slope query.
• Branch-and-Bound: Pruning search subtrees whose computed bounds cannot beat the incumbent best solution.
• Pareto Frontiers: Discarding candidates that are strictly worse across all objective dimensions.

Different data structures; identical mathematical idea.

Variations

Every monotonic queue problem changes exactly one thing:

• Window Extrema: Store raw array indices to track rolling bounds.
• DP Optimization: Store DP state indices to drop $O(k)$ transitions to $O(1)$.
• Transformed State: Store transformed values (prefix sums, algebraic pairings like $y - x$).

Canonical Problems

Window Extrema

• Sliding Window Maximum — Canonical decreasing deque over fixed window $k$.
• Sliding Window Minimum — Inverted invariant (>= eviction comparison).
• Continuous Subarrays — Dual deques (min + max) maintaining dynamic window bounds.

DP Optimization

• Jump Game VI — Sliding maximum accelerating DP state transitions from $O(k) \to O(1)$.

Transformed State

• Shortest Subarray with Sum at Least K (LC 862) — Monotonic deque over prefix sums with greedy matching.

Limits & Production Systems

When It Fails

• Non-FIFO Windows: If the window expands or contracts from arbitrary ends, a deque cannot reorder. Fall back to a heap with lazy deletion.
• Order Statistics: If you need the $k$-th order statistic (e.g. median or p99) rather than the extreme, use a balanced BST, order-statistic tree, or streaming digest (t-digest / DDSketch).
• No Dominance Invariant: If older elements can become optimal again, pruning is unsafe; fall back to plain Sliding window or prefix-sum.

Production Examples

• Rolling Request Latency: Tracking peak p99 response time over a sliding 60-second window in API gateways (Envoy, NGINX).
• Rolling Queue Depth: Monitoring maximum consumer backlog in event streams (Kafka, Celery) over moving intervals.
• Rolling Memory Watermark: Tracking peak heap consumption across GC epochs without allocation overhead.
• Rolling Burst Rate Limits: Tracking maximum request bursts in security firewalls without storing raw event timestamps.

Pattern DNA

Signal         → Repeated extrema queries over forward-sliding state
State          → Frontier of undominated candidates (not the full window)
Invariant      → Monotonic values; oldest candidate sits at front
Transformation → Eagerly evict dominated history upon new arrival
Complexity     → Each element pushed once and popped at most once → O(1) amortized
Failure        → No permanent dominance or window is not forward FIFO
Production     → Rolling latency peaks, queue depth watermarks, burst rate limits
Related        → Monotonic Stack, Convex Hull Trick, Branch-and-Bound, Pareto Frontiers

If you remember only one thing…

A monotonic deque never tries to remember every element. It remembers only the elements that could still become the answer.