Monotonic queues are the secret weapon for sliding window maximum/minimum problems. While a naive approach takes O(nk) and a priority queue takes O(n log k), a monotonic queue solves it in O(n)—linear time.
But here's what confuses most developers: Why use a deque instead of a stack? And why does maintaining decreasing order give us the maximum?
This comprehensive guide will teach you the complete monotonic queue template, why deque is essential, how it achieves O(n) complexity, and when to use queue vs stack.
Use monotonic queue when:
Template:
from collections import deque
dq = deque() # Store indices
for i in range(n):
# Remove out-of-window elements from front
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order (for max)
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]]) # Front is maxTime: O(n), Space: O(k)
Monotonic Stack:
Monotonic Queue:
A deque (pronounced "deck") allows efficient operations at both ends:
from collections import deque
dq = deque()
dq.append(x) # Add to back: O(1)
dq.pop() # Remove from back: O(1)
dq.appendleft(x) # Add to front: O(1)
dq.popleft() # Remove from front: O(1)Why we need both ends:
A regular stack can't remove from the front efficiently!
Given an array and a window size k, find the maximum element in each sliding window.
Example:
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Windows:
[1 3 -1] -3 5 3 6 7 → max = 3
1 [3 -1 -3] 5 3 6 7 → max = 3
1 3 [-1 -3 5] 3 6 7 → max = 5
1 3 -1 [-3 5 3] 6 7 → max = 5
1 3 -1 -3 [5 3 6] 7 → max = 6
1 3 -1 -3 5 [3 6 7] → max = 7
Output: [3, 3, 5, 5, 6, 7]1. Brute Force: O(nk)
# For each window, scan k elements to find max
for i in range(n - k + 1):
max_val = max(nums[i:i+k]) # O(k)
result.append(max_val)
# Total: O(nk)2. Priority Queue (Heap): O(n log k)
import heapq
heap = []
for i in range(n):
heapq.heappush(heap, (-nums[i], i)) # O(log k)
# Remove out-of-window elements
while heap[0][1] < i - k + 1:
heapq.heappop(heap) # O(log k)
if i >= k - 1:
result.append(-heap[0][0])
# Total: O(n log k)3. Monotonic Queue (Deque): O(n)
from collections import deque
dq = deque()
for i in range(n):
# Remove out-of-window: O(1) amortized
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order: O(1) amortized
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
# Total: O(n)Winner: Monotonic queue is asymptotically faster.
from collections import deque
def sliding_window_maximum(nums, k):
"""
Find maximum in each sliding window of size k.
Args:
nums: List of integers
k: Window size
Returns:
List of maximum values for each window
Time: O(n) - each element added and removed at most once
Space: O(k) - deque stores at most k elements
"""
if not nums or k == 0:
return []
result = []
dq = deque() # Store indices, maintain decreasing order of values
for i in range(len(nums)):
# Remove elements outside current window (from front)
while dq and dq[0] < i - k + 1:
dq.popleft()
# Remove elements smaller than current (from back)
# They'll never be maximum while current is in window
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
# Add current element
dq.append(i)
# Add to result once we have a full window
if i >= k - 1:
result.append(nums[dq[0]]) # Front is always maximum
return result
# Example
print(sliding_window_maximum([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Output: [3, 3, 5, 5, 6, 7]function slidingWindowMaximum(nums, k) {
if (!nums || nums.length === 0 || k === 0) return [];
const result = [];
const dq = []; // Use array as deque
for (let i = 0; i < nums.length; i++) {
// Remove out-of-window elements from front
while (dq.length > 0 && dq[0] < i - k + 1) {
dq.shift(); // Remove from front
}
// Maintain decreasing order
while (dq.length > 0 && nums[i] > nums[dq[dq.length - 1]]) {
dq.pop(); // Remove from back
}
dq.push(i);
if (i >= k - 1) {
result.push(nums[dq[0]]);
}
}
return result;
}
// Example
console.log(slidingWindowMaximum([1, 3, -1, -3, 5, 3, 6, 7], 3));
// Output: [3, 3, 5, 5, 6, 7]Note: JavaScript arrays support shift() (remove from front) and pop() (remove from back), making them suitable as deques. However, shift() is O(n) in worst case. For better performance, use a proper deque library or circular buffer.
import java.util.*;
public int[] slidingWindowMaximum(int[] nums, int k) {
if (nums == null || nums.length == 0 || k == 0) {
return new int[0];
}
int n = nums.length;
int[] result = new int[n - k + 1];
Deque<Integer> dq = new ArrayDeque<>();
for (int i = 0; i < n; i++) {
// Remove out-of-window elements
while (!dq.isEmpty() && dq.peekFirst() < i - k + 1) {
dq.pollFirst();
}
// Maintain decreasing order
while (!dq.isEmpty() && nums[i] > nums[dq.peekLast()]) {
dq.pollLast();
}
dq.offerLast(i);
if (i >= k - 1) {
result[i - k + 1] = nums[dq.peekFirst()];
}
}
return result;
}Deque maintains:
Visual:
Deque (indices): [2, 5, 6]
Values: [5, 3, 1] ← Decreasing
Front (index 2, value 5) is always the maximumInsight 1: If a new element is larger than elements at the back, those elements will never be maximum while the new element is in the window.
Proof:
Insight 2: The front of the deque is always the maximum of the current window.
Proof:
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
i=0, val=1: dq=[0]
i=1, val=3:
- 3 > nums[0]=1, pop 0
- dq=[1]
i=2, val=-1:
- -1 < 3, just add
- dq=[1,2]
- Window full, max = nums[1] = 3 ✓
i=3, val=-3:
- -3 < -1, just add
- dq=[1,2,3]
- max = nums[1] = 3 ✓
i=4, val=5:
- Remove 1 (out of window: 1 < 4-3+1=2)
- 5 > nums[3]=-3, pop 3
- 5 > nums[2]=-1, pop 2
- dq=[4]
- max = nums[4] = 5 ✓
i=5, val=3:
- 3 < 5, just add
- dq=[4,5]
- max = nums[4] = 5 ✓
i=6, val=6:
- 6 > nums[5]=3, pop 5
- 6 > nums[4]=5, pop 4
- dq=[6]
- max = nums[6] = 6 ✓
i=7, val=7:
- 7 > nums[6]=6, pop 6
- dq=[7]
- max = nums[7] = 7 ✓
Result: [3, 3, 5, 5, 6, 7] ✓from collections import deque
def maxSlidingWindow(nums, k):
"""
LeetCode #239: Sliding Window Maximum
Time: O(n)
Space: O(k)
"""
if not nums or k == 0:
return []
if k == 1:
return nums
result = []
dq = deque()
for i in range(len(nums)):
# Remove out-of-window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain decreasing order
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])
return resultChange: Maintain increasing order instead of decreasing.
def sliding_window_minimum(nums, k):
"""
Find minimum in each sliding window.
Time: O(n)
Space: O(k)
"""
result = []
dq = deque()
for i in range(len(nums)):
# Remove out-of-window
while dq and dq[0] < i - k + 1:
dq.popleft()
# Maintain INCREASING order (for minimum)
while dq and nums[i] < nums[dq[-1]]: # Changed to <
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]]) # Front is minimum
return result
# Example
print(sliding_window_minimum([1, 3, -1, -3, 5, 3, 6, 7], 3))
# Output: [-1, -3, -3, -3, 3, 3]Given an array and an integer k, return the maximum sum of a non-empty subsequence such that for every two consecutive integers in the subsequence, their indices differ by at most k.
def constrainedSubsetSum(nums, k):
"""
LeetCode #1425: Constrained Subsequence Sum
DP: dp[i] = max sum ending at i
dp[i] = nums[i] + max(0, max(dp[i-k:i]))
Use monotonic queue to find max in window efficiently.
Time: O(n)
Space: O(n)
"""
n = len(nums)
dp = [0] * n
dq = deque()
for i in range(n):
# Remove out-of-window
while dq and dq[0] < i - k:
dq.popleft()
# dp[i] = nums[i] + max previous dp in window
dp[i] = nums[i]
if dq:
dp[i] += max(0, dp[dq[0]])
# Maintain decreasing order of dp values
while dq and dp[i] >= dp[dq[-1]]:
dq.pop()
dq.append(i)
return max(dp)
# Example
print(constrainedSubsetSum([10, 2, -10, 5, 20], 2))
# Output: 37
# Explanation: [10, 2, 5, 20]Key insight: Monotonic queue optimizes the DP transition from O(nk) to O(n).
Question: What's the problem type?
├─ Finding next/previous greater/smaller
│ └─ Use STACK (monotonic stack)
│
├─ Sliding window maximum/minimum
│ └─ Use QUEUE (monotonic deque)
│
└─ Need to remove from both ends?
├─ YES → Use QUEUE (deque)
└─ NO → Use STACKSliding window maximum/minimum
Need to remove from both ends
DP optimization with window constraint
Next/previous greater/smaller element
Histogram problems
Only need to remove from one end
See detailed comparison: Monotonic Stack vs Other Patterns
❌ Wrong:
# Can't remove from front efficiently!
stack = []
# How to remove out-of-window elements?✅ Correct:
from collections import deque
dq = deque()
dq.popleft() # O(1) removal from front❌ Wrong:
# Forgot to remove old elements
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
# Deque may contain elements outside window!✅ Correct:
# Always remove out-of-window first
while dq and dq[0] < i - k + 1:
dq.popleft()❌ Wrong:
while dq and dq[0] < i - k: # Off by one!
dq.popleft()✅ Correct:
while dq and dq[0] < i - k + 1: # Correct
dq.popleft()Explanation: Window is [i-k+1, i], so elements at index < i-k+1 are outside.
❌ Wrong:
for i in range(len(nums)):
# ...
result.append(nums[dq[0]]) # Adds before window is full!✅ Correct:
for i in range(len(nums)):
# ...
if i >= k - 1: # Only after window is full
result.append(nums[dq[0]])See guide: Sliding Window Maximum Mistakes
# Every element is its own window maximum
if k == 1:
return nums# Single window containing all elements
if k >= len(nums):
return [max(nums)]if not nums:
return []nums = [3, 3, 3, 3], k = 2
# Output: [3, 3, 3]Amortized analysis:
Even with nested while loops, each element is processed a constant number of times.
Deque size: At most k elements (window size)
Best case: O(1) if window is strictly increasing/decreasing
See detailed proof: Why Stack Beats Brute Force
| Operation | Deque | Priority Queue |
|---|---|---|
| Add element | O(1) amortized | O(log k) |
| Remove max | O(1) amortized | O(log k) |
| Total | O(n) | O(n log k) |
Winner: Deque is asymptotically faster.
See detailed comparison: Deque vs Priority Queue
Master the monotonic queue with these problems:
Beginner:
Intermediate:
3. Constrained Subsequence Sum (#1425) - DP + deque
4. Shortest Subarray with Sum at Least K (#862) - Deque + prefix sum
5. Jump Game VI (#1696) - DP optimization
Advanced:
6. Longest Continuous Subarray (#1438) - Two deques
7. Maximum Number of Robots (#2398) - Deque + sliding window
8. Minimum Window Subsequence (#727) - Complex window
Q: Why deque instead of stack?
A: Sliding window requires removing from both ends:
Stack only supports one end.
Q: Why is it O(n) and not O(nk)?
A: Each element is added and removed at most once. Even though there are nested loops, the total operations across all iterations is bounded by 2n.
Q: When should I use priority queue instead?
A: Priority queue is useful when:
For sliding window max/min, deque is always better.
Q: Can I use this for 2D sliding windows?
A: Yes, but it's more complex. You'd need to apply monotonic queue on each row, then on the results. See advanced problems.
The monotonic queue (deque) is the optimal solution for sliding window maximum/minimum problems, achieving O(n) time complexity.
Key principles:
The template:
from collections import deque
dq = deque()
for i in range(n):
while dq and dq[0] < i - k + 1:
dq.popleft()
while dq and nums[i] > nums[dq[-1]]:
dq.pop()
dq.append(i)
if i >= k - 1:
result.append(nums[dq[0]])When to use:
Master this pattern, and you'll solve sliding window problems with optimal efficiency. For stack-based patterns, see Monotonic Decreasing Stack and Monotonic Increasing Stack. For the complete overview, see Monotonic Stack & Queue Guide.
Next time you see "sliding window maximum," reach for the monotonic queue.
LeetCopilot is a free browser extension that enhances your LeetCode practice with AI-powered hints, personalized study notes, and realistic mock interviews — all designed to accelerate your coding interview preparation.
Also compatible with Edge, Brave, and Opera
Add to Chrome for free