Queue & Monotonic Deque

At a glance

The instinct

Two closely related tools live here. A plain queue handles anything that happens in arrival order: requests from the last 3000 ms (Number of Recent Calls), people cycling through a ticket line (Time Needed to Buy Tickets), or a deck you deal from the top and tuck under the bottom.

A monotonic deque is a queue with a bouncer. When a new element arrives at the back, it throws out everyone behind it who can never be the answer again. When the window slides, stale elements leave from the front. What survives is always sorted, so the best value of the current window sits at the front. That turns "max of every window" from O(n·k) into O(n) - the heart of Sliding Window Maximum.

Recognise it

Not this pattern if...

• You need the k-th largest overall or a running median - use a heap.
• You need the next greater element and nothing ever expires - a monotonic stack suffices (only one end changes).
• The window condition is a sum or count, not a max/min - a plain two-pointer sliding window is enough.
• It is shortest path on an unweighted graph - same queue, but think BFS.

Memory hack

Analogy - the talent-show line. Acts queue in arrival order and each act only stays for k minutes. When a new act shows up who is better than the people at the back, those acts go home: they are older (they will time out first) and worse, so they can never win. The judge only ever looks at the front of the line.

Say it out loud:

1. "Each deque entry is an index; values are decreasing front-to-back because I want the max."
2. "On arrival I pop the back while the new value dominates; each step I pop the front if it is out of the window."
3. "The front is this window's answer, and every index is pushed and popped at most once, so it is O(n)."

How it works

Store indices, not values, so you can tell when an element has slid out of range. For a maximum keep values strictly decreasing from front to back; for a minimum keep them increasing.

Trace for nums = [1, 3, -1, -3, 5, 3], k = 3 (deque shown as values for readability):

Notice that at i = 4 the value 5 wipes out the whole deque in one go. That looks expensive, but those elements were each pushed once and can only be popped once, so the total work across the run is linear.

Java template

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

class MonotonicDequeTemplate {
    // Max of every window of size k. For a window minimum, flip <= to >=.
    static int[] windowMax(int[] nums, int k) {
        int n = nums.length;
        int[] out = new int[Math.max(0, n - k + 1)];
        Deque<Integer> dq = new ArrayDeque<>();            // indices; values decreasing front -> back
        for (int i = 0; i < n; i++) {
            while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) {
                dq.pollLast();                             // bounce the weak from the back
            }
            dq.offerLast(i);
            if (dq.peekFirst() <= i - k) dq.pollFirst();   // expire the old from the front
            if (i >= k - 1) out[i - k + 1] = nums[dq.peekFirst()]; // front = champion
        }
        return out;
    }
}

import java.util.ArrayDeque;
import java.util.Queue;

// Time-window queue: how many events happened in the last `window` time units?
class RecentEventCounter {
    private final Queue<Integer> q = new ArrayDeque<>();
    private final int window;

    RecentEventCounter(int window) { this.window = window; }

    int record(int t) {                        // timestamps arrive in non-decreasing order
        q.offer(t);
        while (q.peek() < t - window) q.poll(); // drop events older than the window
        return q.size();
    }
}

For the DP flavour (Jump Game VI), keep the deque over dp values instead of nums: compute dp[i] = nums[i] + dp[front], then push i with the same back-popping rule.

Complexity

• Monotonic deque: O(n) time, because each index enters and leaves once; O(k) extra space.
• Time-window queue: amortised O(1) per event; space equals the number of events inside the window.
• Deque-optimised DP: O(n) instead of O(n·k) brute force or O(n log n) with a heap.
• Round-robin simulation: proportional to total work done; often there is a counting shortcut (for the ticket line, sum min(tickets[j], tickets[k]), adjusted for people behind position k).

Variations

• Time-window counter - expire by timestamp rather than position. Number of Recent Calls.
• Round-robin simulation - poll, do one unit of work, re-offer if work remains. Time Needed to Buy Tickets.
• Reverse simulation - simulate the dealing process on indices with a queue, then drop sorted values into those slots. Reveal Cards In Increasing Order.
• Fixed window max/min - a single decreasing (or increasing) deque. Sliding Window Maximum.
• Two deques, variable window - one for max, one for min; advance the left pointer while max - min exceeds the limit. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit.
• DP over a sliding window - the deque holds the best previous states. Jump Game VI, Max Value of Equation.

Common mistakes

• Storing values instead of indices, leaving no way to know whether the front has slid out of the window.
• Emitting an answer before the first window is full - only record once i >= k - 1.
• Using ArrayList.remove(0) as a dequeue: that shifts every element and is O(n) per call. Use ArrayDeque.
• Comparing two boxed values with ==, e.g. maxDq.peekFirst() == minDq.peekFirst(); this compares Integer references, which breaks for values outside the small-integer cache. Unbox or use .equals.
• In deque DP, comparing against nums instead of the dp values that actually live in the window.

All practice problems

7 problems on this site use this pattern, easiest first. Solve them in order and say the instinct out loud before you code.