Monotonic Deque

Objectives and sequence#

• Store indices so candidates can expire when the fixed window moves.
• Remove dominated candidates under an explicit equal-value tie policy.
• Explain the amortized O(n) bound by counting each index's deque lifetime.
• Distinguish a monotonic deque from a monotonic stack and a heap.

Recognition boundaries#

From baseline to method#

Simple baseline: Scan all k values for every one of the n-k+1 windows. It is correct but costs O(nk), repeating almost the same maximum search after each one-position shift.

1. Store indices rather than values because expiration depends on position and duplicate values must remain distinguishable.
2. Before using the deque for the window ending at i, remove a front index when it is less than or equal to i-k.
3. While the back value is less than or equal to the arriving value, remove it. The newer index lasts at least as long and is no smaller, so the older candidate is dominated.
4. Append the arriving index. Once i ≥ k-1, the front value is the maximum for that complete window.
5. Every index is appended once and removed at most once from either end, so all deque work is O(n) amortized.

Worked example#

Return the maximum of every length-3 window, retaining the newest index when equal values compete.

Input

values = [4, 2, 2, 5, 1, 5], k = 3

Contract

1 ≤ k ≤ values.length; values are integers; output maxima appear in left-to-right window order.

Expected

[4, 5, 5, 5]

Trace summary: At each index, expire indices outside [i-k+1,i], remove no-larger values from the back, append i, and read the front after the first complete window.

Pseudocode and tested references#

The pseudocode names deque-end operations abstractly. The tested references implement the same newest-equal policy with Python collections.deque and Java ArrayDeque; neither is a submitted-code runner.

fixedWindowMax(values, k):
  deque = empty deque of indices
  answer = empty list
  for i from 0 through values.length - 1:
    while deque not empty and deque.front <= i - k: pop front
    while deque not empty and values[deque.back] <= values[i]: pop back
    push i at back
    if i >= k - 1: append values[deque.front] to answer
  return answer

from collections import deque

def fixed_window_max(values, k):
    if k < 1 or k > len(values):
        raise ValueError("k must be within the input length")
    candidates = deque()
    answer = []
    for i, value in enumerate(values):
        while candidates and candidates[0] <= i - k:
            candidates.popleft()
        while candidates and values[candidates[-1]] <= value:
            candidates.pop()
        candidates.append(i)
        if i >= k - 1:
            answer.append(values[candidates[0]])
    return answer

import java.util.ArrayDeque;
import java.util.Deque;

public final class MonotonicDequeReference {
    public static int[] fixedWindowMax(int[] values, int k) {
        if (k < 1 || k > values.length) {
            throw new IllegalArgumentException("k must be within the input length");
        }
        int[] answer = new int[values.length - k + 1];
        int write = 0;
        Deque<Integer> candidates = new ArrayDeque<>();
        for (int i = 0; i < values.length; i++) {
            while (!candidates.isEmpty() && candidates.peekFirst() <= i - k) {
                candidates.removeFirst();
            }
            while (!candidates.isEmpty() && values[candidates.peekLast()] <= values[i]) {
                candidates.removeLast();
            }
            candidates.addLast(i);
            if (i >= k - 1) answer[write++] = values[candidates.peekFirst()];
        }
        return answer;
    }
}

Time

O(n) amortized: each index enters once and leaves at most once.

Space

O(k) for the deque, plus O(n-k+1) for the returned output.

Assumptions

1 ≤ k ≤ n; deque operations at either end are O(1) amortized; output construction cost is included separately from auxiliary space.

Failure modes and edges#

Edge cases

• k=1 returns every input value.
• k=n returns one global maximum.
• All values equal repeatedly exercise the newest-equal tie policy.
• Strictly decreasing values keep up to k live candidates.
• Negative values require no special sentinel.
• An empty input has no valid k under this lesson's explicit precondition.

Wrong approaches

Three-stage hint ladder#

Narrated reasoning

I need both dominance by value and expiration by age, so I will store indices in a deque. A newer value at least as large as an older one dominates it: the older one cannot win now and expires sooner. I am choosing newest-equal, so the back-removal comparison is ≤ rather than <. Before each output I remove an index at or before i-k, making the front legal for the current window. The nested while loops are still linear overall because no index can be removed twice.

Reasoning checkpoints#

Guided exercises

• Change the invariant to return fixed-window minima while still retaining the newest equal value.
  Checkpoint: Reverse the monotonic comparison: remove back values greater than or equal to the arrival; expiration logic is unchanged.

Practice and transfer#

Unseen variant: Return each length-k window's minimum and the newest index that attains it. Preserve the index in the output.

Checkpoint: Use an increasing deque, remove older equals with ≥, and output both candidates.front and its value.

Practice handoffs

• Practice sliding-window maximumApply the exact index-expiration and dominance invariant.
• Compare ordinary sliding windowsSeparate aggregate-validity windows from fixed-window extrema.

Follow-up constraints

• Retain the oldest equal candidate instead; which comparison changes, and what output remains identical?
• Compare the deque with a lazy-deletion max heap when arbitrary window removal is later introduced.
• Explain why the structure is not sufficient for the median of each window.

Sources and review#

This original Engineering Foundry lesson received Codex self-review on 2026-09-05; independent human editorial review is not claimed.

• Minimum Stack / Minimum Queue (opens in a new tab) - Dominated-candidate removal, queue-window expiration, and linear sliding-extrema construction.
• collections - Container datatypes (opens in a new tab) - Python deque end-operation semantics used by the reference implementation.
• ArrayDeque (opens in a new tab) - Java deque operations used by the portable Java 17+ reference implementation.