Foundation · Module 11 · Lesson 5

Monotonic queue

Sliding extrema and constrained DP.

15–25 min readLesson 62 of 123

Lesson 62 of 123

1d streak

Monotonic Queue: Sliding Window Maximum in O(n)

A Monotonic Queue maintains elements in monotonic order while supporting sliding window bounds. In the classic Sliding Window Maximum problem (find the maximum in every window of size $k$), checking each window naively takes $O(n cdot k)$. A monotonic decreasing deque solves this in strictly O(n) time.

Sliding Window Maximum Trace for nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3text

Invariant: Deque stores indices in strictly decreasing order of their values.
Front of deque ALWAYS holds the maximum element of the active window!

Window [1, 3, -1]:
- Push 1: Deque = [1]
- Push 3: 3 > 1 -> Pop 1. Deque = [3]
- Push -1: -1 < 3 -> Deque = [3, -1]. Max = 3

Window [3, -1, -3]:
- Push -3: Deque = [3, -1, -3]. Max = 3

Window [-1, -3, 5]:
- Index of 3 went out of window bounds -> removeFirst()!
- Push 5: 5 > -3, 5 > -1 -> Pop both! Deque = [5]. Max = 5

Every index enters the deque once and leaves at most once: O(n) total time!

SlidingWindowMax.javajava

public int[] maxSlidingWindow(int[] nums, int k) {
    if (nums == null || k <= 0) return new int[0];
    int n = nums.length;
    int[] result = new int[n - k + 1];
    Deque<Integer> deque = new ArrayDeque<>(); // stores INDICES

    for (int i = 0; i < n; i++) {
        // 1. Remove indices that are outside the current window [i - k + 1, i]
        while (!deque.isEmpty() && deque.peekFirst() < i - k + 1) {
            deque.pollFirst();
        }

        // 2. Remove indices of smaller elements from back (they can never be the max)
        while (!deque.isEmpty() && nums[deque.peekLast()] < nums[i]) {
            deque.pollLast();
        }

        // 3. Add current element index
        deque.offerLast(i);

        // 4. Record current max (front of deque) once first window is formed
        if (i >= k - 1) {
            result[i - k + 1] = nums[deque.peekFirst()];
        }
    }
    return result;
}

Cost Model

Complexity & Trade-offs

OperationTimeSpaceWhy

Full scan

O(n)

O(k)

Each index enters and leaves once.

When to use it

Nested parsing, undo, arrival order, buffering, and nearest-greater queries.
BFS frontiers and producer/consumer scheduling.
Maintaining range extremes or constrained access.

Common mistakes

Reading from an empty structure.
Confusing the logical front with an array index in a circular buffer.
Missing the amortized argument for transfers or monotonic pops.

Practice prompts

Reproduce the worked Monotonic queue example without looking at the trace.
Change one input condition and explain whether the Monotonic queue invariant still holds.
Implement the approach, derive its cost, and compare it with a straightforward baseline.

Mastery check

Can you derive it instead of memorizing it?

State the invariant before looking at code.

Explain why every transition is safe.

Construct a worst-case input.

Name one alternative and its trade-off.