Monotonic Queue
The Intuition
Picture a line of people waiting to get into a club, but the bouncer has a strange rule: if you're taller than the people already in line ahead of you, they have to leave. So when a 6'2" person walks up, everyone shorter standing in front of them gets kicked out. The tallest person is always at the front of the line.
Now add a second rule: the line only holds the last k people who arrived. Anyone who got in line too long ago gets removed from the front, even if they're tall. So the front of the line is always the tallest person within the current window of k arrivals.
That's your monotonic queue. It's a deque (double-ended queue) where you add to the back and can remove from both ends. When a new element arrives, you pop everything smaller off the back because those elements will never be the answer for any future window. They're both older and smaller than the new arrival. Then you check the front: if the element there has fallen outside the current window, pop it off. The front always gives you the window's maximum in O(1).
The beautiful part is the amortized cost. Every element enters the deque exactly once and leaves exactly once. Even though there are inner loops popping elements, the total number of pops across the entire traversal is at most n. So the whole thing runs in O(n) time, not O(nk). You get the max of every sliding window position without ever scanning the full window.
Sliding window maximum/minimum, shortest subarray with sum >= k, jump game variants, or any problem needing the extreme value within a moving window.
- Need arbitrary element removal (use balanced BST/TreeMap)
- Window doesn't slide linearly
- Need both min and max simultaneously (use two deques)
Variations:
- Decreasing deque: Front holds the maximum. Used for sliding window max.
- Increasing deque: Front holds the minimum. Used for sliding window min.
- Combined with prefix sums: Shortest subarray with sum at least K.
- window size 1
- all increasing values
- negative values
Key Points
- •Deque maintains elements in decreasing (or increasing) order
- •Front of deque always holds the current window's max (or min)
- •Remove from back when a new element violates monotonic order
- •Remove from front when the element falls outside the window
- •Each element is added and removed at most once. Amortized O(1).
Code Template
1 from collections import deque
2
3 def sliding_window_max(nums, k):
4 """Maximum in each sliding window of size k."""
5 result = []
6 dq = deque() # stores indices, front = max
7
8 for i in range(len(nums)):
9 # Remove elements outside the window
10 while dq and dq[0] < i - k + 1:
11 dq.popleft()
12
13 # Remove smaller elements from back
14 while dq and nums[dq[-1]] <= nums[i]:
15 dq.pop()
16
17 dq.append(i)
18
19 if i >= k - 1:
20 result.append(nums[dq[0]])
21
22 return result
23
24 def sliding_window_min(nums, k):
25 """Minimum in each sliding window of size k."""
26 result = []
27 dq = deque() # stores indices, front = min
28
29 for i in range(len(nums)):
30 while dq and dq[0] < i - k + 1:
31 dq.popleft()
32 while dq and nums[dq[-1]] >= nums[i]:
33 dq.pop()
34 dq.append(i)
35 if i >= k - 1:
36 result.append(nums[dq[0]])
37
38 return resultCommon Mistakes
- Not removing expired elements from the front of the deque
- Storing values instead of indices (can't check window bounds)
- Confusing with monotonic stack. The queue maintains a sliding window; the stack does not