Pattern Guide
Monotonic Queue
"Sliding window max/min in O(1). Deque keeps candidates in sorted order."
A monotonic queue (deque) solves sliding window maximum/minimum in O(n) total. The deque stores indices in decreasing (for max) or increasing (for min) order of values — elements that can never be the answer are evicted immediately. Extends to DP optimization when transitions look like "max/min over a window of previous states."
Problems you can solve with this pattern
6 problems · click any to start solving
// Sliding window maximum: for every window of size k, find max
// Deque holds indices in DECREASING order of values
function slidingWindowMax(nums, k) {
const deque = []; // indices, front = largest, back = smallest in window
const result = [];
for (let i = 0; i < nums.length; i++) {
// 1. Evict elements outside window from front
while (deque.length && deque[0] <= i - k) deque.shift();
// 2. Maintain decreasing order: pop smaller elements from back
while (deque.length && nums[deque.at(-1)] <= nums[i]) deque.pop();
// 3. Add current index
deque.push(i);
// 4. Window is full — record answer
if (i >= k - 1) result.push(nums[deque[0]]);
}
return result;
}
// For MINIMUM: flip the comparison in step 2 to >=
// while (deque.length && nums[deque.at(-1)] >= nums[i]) deque.pop();A monotonic deque answers "what is the maximum in the last k elements?" for every position in O(1) amortized time. The key invariant: the deque holds indices of elements that are candidates to be the current window's answer. Elements that are both older AND smaller than a newly added element can never win — so we evict them from the back. Expired elements (outside window) are evicted from the front.
// Sliding window maximum: for every window of size k, find max
// Deque holds indices in DECREASING order of values
function slidingWindowMax(nums, k) {
const deque = []; // indices, front = largest, back = smallest in window
const result = [];
for (let i = 0; i < nums.length; i++) {
// 1. Evict elements outside window from front
while (deque.length && deque[0] <= i - k) deque.shift();
// 2. Maintain decreasing order: pop smaller elements from back
while (deque.length && nums[deque.at(-1)] <= nums[i]) deque.pop();
// 3. Add current index
deque.push(i);
// 4. Window is full — record answer
if (i >= k - 1) result.push(nums[deque[0]]);
}
return result;
}
// For MINIMUM: flip the comparison in step 2 to >=
// while (deque.length && nums[deque.at(-1)] >= nums[i]) deque.pop();- Stack: single end, used for "next greater/smaller element"
- Deque: both ends, used for "window max/min" (evict old from front, maintain order from back)
Pattern recognition:
- "Sliding window max/min" → deque, O(n)
- "DP where dp[i] = f(max dp[j]) for j in window" → deque DP optimization
- Two deques (one max, one min) → control window by range constraint
Implementation: Use array as deque: push/pop from back, shift from front (or pointer-based for O(1) shift).