In Part 1 and Part 2, every problem had a clean O(1) update per window slide — add an element, remove an element, done. That worked because we were tracking sums or counts, which are trivially updatable.
But what if you need the maximum of each window?
You can’t just subtract the outgoing element from “the max” — the max might not change, or it might have been the element you just removed. A naive approach would scan the entire window for the new max each time, giving O(nk). For large inputs, that’s too slow.
This is where the monotonic deque comes in — arguably the most elegant data structure trick in the sliding window toolkit.
Problem 8: Sliding Window Maximum (LC 239)
Difficulty: Hard
Problem: Given an array nums and a sliding window of size k, return the maximum value in each window position as it slides from left to right.
Example
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Window position Max
----------------- -----
[1 3 -1] -3 5 3 6 7 3
1 [3 -1 -3] 5 3 6 7 3
1 3 [-1 -3 5] 3 6 7 5
1 3 -1 [-3 5 3] 6 7 5
1 3 -1 -3 [5 3 6] 7 6
1 3 -1 -3 5 [3 6 7] 7
Output: [3, 3, 5, 5, 6, 7]
Why a Regular Queue Doesn’t Work
In earlier problems, we used a queue to maintain the window (LC 346). But a queue only gives O(1) access to the front — there’s no efficient way to find the maximum among all elements in the queue.
You might think of using a priority_queue (max-heap), but the problem is removal: when the window slides, you need to remove the oldest element, and heaps don’t support efficient deletion of arbitrary elements. You’d need lazy deletion, which adds complexity.
The Monotonic Deque Idea
A deque (double-ended queue) lets you push and pop from both the front and the back in O(1). The trick is to maintain the deque in decreasing order — the front is always the current maximum.
Here’s the core insight: you don’t need to store every element in the window. If a newer element is larger than older elements in the deque, those older elements can never be the maximum for any future window. They’re permanently shadowed. So we remove them.
The Two Rules
When inserting a new element:
- While the deque is not empty AND the back of the deque is smaller than the new element → pop the back.
- Then push the new element to the back.
This ensures the deque stays in decreasing order. The front is always the largest.
When the window slides (removing the oldest element):
- Check if the front of the deque equals the element leaving the window.
- If so, pop the front.
- If not, do nothing — that element was already removed by the insertion rule.
This is why the deque doesn’t store all window elements. Smaller elements that appeared before a larger one get purged during insertion and never need explicit removal.
Solution (C++)
cpp
class Solution {
public:
vector<int> maxSlidingWindow(vector<int>& nums, int k) {
deque<int> maxNums;
for (size_t i = 0; i < k; ++i) {
while (!maxNums.empty() && maxNums.back() < nums[i]) {
maxNums.pop_back();
}
maxNums.push_back(nums[i]);
}
vector<int> result = {maxNums.front()};
for (size_t i = k; i < nums.size(); ++i) {
if (maxNums.front() == nums[i-k]) {
maxNums.pop_front();
}
while (!maxNums.empty() && maxNums.back() < nums[i]) {
maxNums.pop_back();
}
maxNums.push_back(nums[i]);
result.push_back(maxNums.front());
}
return result;
}
};
Step-by-Step Trace
Let’s trace through nums = [1, 3, -1, -3, 5, 3, 6, 7] k = 3
Phase 1: Build the initial window [0..2]
| i | nums[i] | Action | Deque State |
|---|---|---|---|
| 0 | 1 | Push 1 | [1] |
| 1 | 3 | 3 > 1, pop 1. Push 3 | [3] |
| 2 | -1 | -1 < 3, just push | [3, -1] |
First result: front() = 3
Phase 2: Slide the window
| i | Leaving | nums[i] | Remove front? | Insert logic | Deque | Result |
|---|---|---|---|---|---|---|
| 3 | nums[0]=1 | -3 | 1 ≠ 3, no | -3 < -1, push | [3, -1, -3] | 3 |
| 4 | nums[1]=3 | 5 | 3 == 3, pop front | 5 > all, clear then push | [5] | 5 |
| 5 | nums[2]=-1 | 3 | -1 ≠ 5, no | 3 < 5, push | [5, 3] | 5 |
| 6 | nums[3]=-3 | 6 | -3 ≠ 5, no | 6 > 3, pop; 6 > 5, pop; push | [6] | 6 |
| 7 | nums[4]=5 | 7 | 5 ≠ 6, no | 7 > 6, pop; push | [7] | 7 |
Final output: [3, 3, 5, 5, 6, 7]
Why O(n)?
It might look like the inner while loop makes this O(nk), but each element is pushed into the deque at most once and popped at most once. Across all iterations, the total number of push and pop operations is bounded by 2n. So the amortized time per element is O(1), and the overall complexity is O(n).
Time: O(n)
Space: O(k) — the deque holds at most k elements
A Note on the Value-Based Approach
The solution above stores values in the deque, not indices. This works correctly because the removal check (maxNums.front() == nums[i-k]) only pops the front when the outgoing value matches. If there are duplicate values in the window, this is safe — we only remove one occurrence, and the deque’s decreasing order guarantees correctness.
An alternative approach stores indices in the deque instead of values. This makes the out-of-window check explicit (if deque.front() <= i – k, pop) and avoids any ambiguity with duplicates. Both approaches are O(n), but the index-based version is sometimes considered more robust.
Series Recap
Across all 8 problems, we’ve seen the sliding window pattern in three levels:
Level 1: Basic Fixed Window (Part 1)
Problems: LC 346, 643, 1343
The window slides, you maintain a sum, and the evaluation is a simple comparison. The template is mechanical — once you recognize “fixed-size subarray,” the code almost writes itself.
Level 2: Conditional Fixed Window (Part 2)
Problems: LC 1176, 1052, 1456, 1100
Same window mechanics, but the state you track gets more interesting: multiple counters, character sets, hash maps. The skill here is decomposing the problem to identify what the window should track vs. what should be computed globally.
Level 3: Monotonic Deque (Part 3)
Problem: LC 239
The window concept is the same, but maintaining the max efficiently requires a new data structure. The monotonic deque keeps candidates in sorted order and prunes elements that can never be the answer.
When to Use Sliding Window
Ask yourself these questions:
- Does the problem involve a contiguous subarray or substring?
- Is the window size fixed (or bounded)?
- Can you incrementally update the window state as elements enter and leave?
If all three are yes, sliding window is almost certainly the right approach. Start with the basic template, figure out what state to track, and you’re most of the way there.
Thanks for following along! If you found this series helpful, check out my other posts on data structures and algorithms for interview prep.