What you will learn
- Why the obvious approaches to sliding window maximum are too slow.
- The monotonic deque: which elements to keep and why.
- A full dry run, plus Python and Java solutions.
The problem
Given an array nums and a window size k, return the maximum of every window of k consecutive elements (LeetCode 239). For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the answer is [3, 3, 5, 5, 6, 7].
Approaches:
| Approach | Time | Problem |
|---|---|---|
max() of every window | O(n·k) | Too slow when n and k are both 10⁵ |
| Max-heap with lazy deletion | O(n log n) | Works, but heavier and more code |
| Monotonic deque | O(n) | Each index is pushed and popped at most once |
The key insight
When a new value x enters the window, any older, smaller-or-equal value can never be a maximum again: x is at least as big and will stay in the window longer. So throw those values away.
What remains, read from front to back, is a decreasing sequence of candidates. The front is the current maximum. The only other cleanup: if the front index has slid out of the window, drop it.
The deque stores indices, not values, so we can tell when an element has left the window.
Dry run
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3 (deque shown as values):
| i | x | Pop from back | Deque after | Front expired? | Output |
|---|---|---|---|---|---|
| 0 | 1 | none | [1] | no | none |
| 1 | 3 | 1 | [3] | no | none |
| 2 | -1 | none | [3, -1] | no | 3 |
| 3 | -3 | none | [3, -1, -3] | no | 3 |
| 4 | 5 | -3, -1, 3 | [5] | no | 5 |
| 5 | 3 | none | [5, 3] | no | 5 |
| 6 | 6 | 3, 5 | [6] | no | 6 |
| 7 | 7 | 6 | [7] | no | 7 |
Python
"""Sliding window maximum in O(n) with a monotonic deque (LeetCode 239)."""
import random
from collections import deque
def max_sliding_window(nums, k):
dq = deque() # indices; their values are strictly decreasing from front to back
out = []
for i, x in enumerate(nums):
while dq and nums[dq[-1]] <= x:
dq.pop() # smaller values can never be a max while x is in the window
dq.append(i)
if dq[0] <= i - k:
dq.popleft() # front index slid out of the window
if i >= k - 1:
out.append(nums[dq[0]])
return out
def brute_force(nums, k):
return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]
if __name__ == "__main__":
print(max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3))
random.seed(7)
for _ in range(2000):
nums = [random.randint(-20, 20) for _ in range(random.randint(1, 40))]
k = random.randint(1, len(nums))
assert max_sliding_window(nums, k) == brute_force(nums, k)
print("2000 random tests match brute force")
Output:
[3, 3, 5, 5, 6, 7]
2000 random tests match brute force
Random testing against a brute force is a habit worth copying: it catches off-by-one errors in the expiry check (dq[0] <= i - k) quickly.
Java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class SlidingWindowMax {
public static int[] maxSlidingWindow(int[] nums, int k) {
int[] out = new int[nums.length - k + 1];
Deque<Integer> dq = new ArrayDeque<>(); // indices, values decreasing front to back
for (int i = 0; i < nums.length; i++) {
while (!dq.isEmpty() && nums[dq.peekLast()] <= nums[i]) dq.pollLast();
dq.offerLast(i);
if (dq.peekFirst() <= i - k) dq.pollFirst();
if (i >= k - 1) out[i - k + 1] = nums[dq.peekFirst()];
}
return out;
}
public static void main(String[] args) {
System.out.println(Arrays.toString(maxSlidingWindow(new int[]{1, 3, -1, -3, 5, 3, 6, 7}, 3)));
}
}
Output:
[3, 3, 5, 5, 6, 7]
Why it’s O(n)
Every index is appended once and removed at most once (from the back when a bigger value arrives, or from the front when it expires). That’s at most 2n deque operations in total, even though there’s a while inside the loop. Extra space is O(k).
Related problems
- Sliding window minimum: flip the comparison so the deque is increasing.
- Shortest subarray with sum at least K (LeetCode 862): a monotonic deque over prefix sums.
- Constrained subsequence sum (LeetCode 1425): DP where each state needs the max of the previous k states.
- Jump game VI (LeetCode 1696): same DP-plus-window-max idea.
This pattern sits with monotonic stacks on the cheat sheet: monotonic stack / deque problems. The next lessons cover prefix sums and the stack version of the idea in monotonic stack.
Key takeaways
- Keep a deque of indices whose values are decreasing; the front is the window maximum.
- Pop smaller-or-equal values from the back before pushing; pop the front when it leaves the window.
- Store indices, not values, so you can detect expiry.
- O(n) time because each index enters and leaves the deque once.
Exercises
- Modify the code to return window minimums.
- Return both max and min for every window in one pass with two deques.
- Solve “longest subarray where max − min ≤ limit” (LeetCode 1438) with two deques and a variable window.
Quiz
- Why can a smaller, older value be discarded when a bigger value arrives?
- Why does the deque hold indices instead of values?
- What is the time complexity, and why isn’t the inner while loop O(k) per step overall?
Show answers
- The new value is larger and will stay in the window at least as long, so the older value can never be the maximum of any future window.
- To know when the front element has slid out of the window (
index <= i - k). - O(n): each index is pushed once and popped at most once, so the total work of all inner loops is bounded by n.