Track sliding window maximums or minimums in O(n) using a double-ended queue that maintains sorted order.
A monotonic queue (or monotonic deque) is a double-ended queue where the elements are always in increasing (or decreasing) order from front to back. When a new element would violate this order, we remove elements from the back until the order is restored. The front of the deque always holds the current answer.
We maintain a deque of indices. Elements enter from the back and leave from both ends. The front holds the current window's extreme value (max or min). Elements that can never be the answer are discarded from the back before they even get a chance.
Why does this work? If a newer element is larger than an older one in the deque, the older element can never be the window maximum — the newer element will outlive it in the window. So we discard the older element from the back. The front always holds the largest (and oldest) element currently in the window.
Look for these recognition signals in the problem statement. If you spot one, a monotonic queue is very likely the intended approach.
"Sliding window maximum" or "sliding window minimum"
"Maximum/minimum in subarray" with constraints
"Shortest subarray with sum at least K"
"DP with bounded lookback"
The key clue: You need the maximum or minimum within a sliding window of fixed or variable size. A brute-force scan of each window would be O(nk). The monotonic queue solves it in O(n) by maintaining only the "useful" candidates in sorted order and removing stale elements from the front.
The deque holds indices whose values are in decreasing order (front to back). When a new element is larger than the back, we pop from the back. The front of the deque is always the index of the current window maximum. This is the most common variant.
Find the maximum in every window of size 3. Result: [3, 3, 5, 5, 6, 7]
The deque holds indices whose values are in increasing order (front to back). When a new element is smaller than the back, we pop from the back. The front always holds the current window minimum. This is the mirror image of Variant 1.
Find the minimum in every window of size 3. Result: [1, 1, 1]
Choosing the variant: If you want the window maximum, use a decreasing deque (remove from back when new > back). If you want the window minimum, use an increasing deque (remove from back when new < back). The front always holds the answer.
Here is the annotated Java template for the sliding window maximum. Adapt the comparison operator for sliding window minimum.
// Sliding Window Maximum using Monotonic Deque int[] maxSlidingWindow(int[] nums, int k) { int n = nums.length; int[] result = new int[n - k + 1]; Deque<Integer> dq = new ArrayDeque<>(); // stores INDICES for (int i = 0; i < n; i++) { // 1. Remove front if it's outside the window if (!dq.isEmpty() && dq.peekFirst() < i - k + 1) { dq.pollFirst(); } // 2. Remove smaller elements from back while (!dq.isEmpty() && nums[dq.peekLast()] < nums[i]) { dq.pollLast(); } // 3. Add current index to back dq.offerLast(i); // 4. Record answer once window is full if (i >= k - 1) { result[i - k + 1] = nums[dq.peekFirst()]; } } return result; }
// Change < to > in the back-removal loop while (!dq.isEmpty() && nums[dq.peekLast()] > nums[i]) { dq.pollLast(); }
Two removal points. Unlike a monotonic stack (which only pops from one end), the deque removes elements from both ends: stale elements leave from the front (out of window), and dominated elements leave from the back (can never be the answer). This double-ended removal is what makes it a deque, not a stack.
Let us trace through the classic example step by step, showing the deque contents, window boundaries, and output at every stage.
Finding the sliding window maximum for each window of size 3.
| STEP | ACTION | DEQUE (vals) | OUTPUT |
|---|---|---|---|
| i=0 (4) | Push 0 | [4] | — |
| i=1 (3) | 3 ≤ 4, push 1 | [4, 3] | — |
| i=2 (5) | Remove 3, 4 from back, push 2 | [5] | 5 |
| i=3 (4) | 4 ≤ 5, push 3 | [5, 4] | 5, 5 |
| i=4 (3) | Front idx 2 out of [2..4]? No. 3 ≤ 4, push 4 | [5, 4, 3] | 5, 5, 5 |
| i=5 (3) | Front idx 2 < 3, remove front. 3 ≤ 4, push 5 | [4, 3, 3] | 5, 5, 5, 4 |
| i=6 (6) | Remove 3, 3, 4 from back, push 6 | [6] | 5, 5, 5, 4, 6 |
| i=7 (7) | Remove 6 from back, push 7 | [7] | 5, 5, 5, 4, 6, 7 |
Two types of removal: Notice at i=5, the front was removed because it fell outside the window (stale), while at i=6, elements were removed from the back because they were smaller (dominated). This dual removal — front for staleness, back for dominance — is the hallmark of the monotonic queue.
These are the classic LeetCode problems that use the monotonic queue pattern, listed in rough order of difficulty.
Practice tip: Start with #239 (the direct application of the template). Then try #1438 which uses two monotonic deques simultaneously — one for max and one for min. For an advanced challenge, #862 applies the deque to prefix sums with a variable-size window, which is a common pattern in competitive programming.
Enter an array and window size, then step through the sliding window maximum algorithm. Watch the deque grow and shrink from both ends, and see the result array fill in as each window completes.
Each element is added to the deque exactly once (pushed to back) and removed at most once (from either end). Over the entire algorithm, the total additions and removals are at most 2n. Even though the inner while loop might run multiple times for a given i, the amortized cost across all iterations is O(n).
Space: The deque holds at most k elements at any time (the current window), so space is O(k). The output array of size n - k + 1 is additional but considered part of the output, not auxiliary space.
| APPROACH | TIME | SPACE |
|---|---|---|
| Brute force | O(nk) | O(1) |
| Heap / TreeMap | O(n log k) | O(k) |
| Monotonic Deque | O(n) | O(k) |
Amortized analysis: The inner while loop might remove multiple elements for a single i, but those elements were each added exactly once in a previous iteration. Across all iterations, total removals cannot exceed total additions (n). This amortized cost is what makes the algorithm linear despite the nested loop.
Double-ended removal is the key insight. Unlike a monotonic stack (one end), the deque removes stale elements from the front and dominated elements from the back. This dual mechanism is what enables O(n) sliding window queries.
Decreasing deque for max, increasing for min. The deque's order invariant matches what you are looking for. For sliding window maximum, maintain decreasing order. For minimum, maintain increasing order. Flip the comparison to switch.
Store indices, not values. The deque stores indices so you can check whether the front element is still within the current window. You can always look up the value via the original array.
The front is always the answer. After processing each new element, the front of the deque holds the index of the maximum (or minimum) for the current window. This is guaranteed by the deque's order invariant combined with the front-staleness check.
Extends to DP optimization and variable windows. When a DP recurrence needs the best value from the last k states, a monotonic deque turns O(nk) into O(n). For variable-size windows (like #862), the deque works on prefix sums and removes from the front when optimality conditions are met rather than staleness.