Sliding Window Maximum: The Monotonic Deque That Turns O(n·k) Into O(n)
Solve Sliding Window Maximum in O(n) with a monotonic deque — the intuition, JavaScript code, a full walkthrough, complexity table, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Sliding Window Maximum (LeetCode 239) is rated Hard, but not because the code is long — the optimal solution fits in fifteen lines. It's Hard because it demands a data structure most people have never needed before: the monotonic deque, a queue that deliberately throws information away and is faster precisely because of it.
The unlock is one observation: once a bigger number enters the window, every smaller number that arrived earlier is dead weight. It can never be the maximum of any future window. Delete it and never look back. That single idea collapses an O(n·k) problem into O(n), and it powers a whole family of harder problems — shortest subarray with sum at least K, jump game variants, constrained DP optimizations.
The problem
Given an integer array nums and a window size k, a window of k consecutive elements slides from the left edge of the array to the right, one position at a time. Return an array containing the maximum of each window.
Input: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Output: [3, 3, 5, 5, 6, 7]
Window [1, 3, -1] → max 3
Window [3, -1, -3] → max 3
Window [-1, -3, 5] → max 5
Window [-3, 5, 3] → max 5
Window [5, 3, 6] → max 6
Window [3, 6, 7] → max 7An array of length n produces exactly n - k + 1 windows. The constraints go up to 10⁵ elements, which quietly rules out anything slower than roughly O(n log n).
The brute force baseline
Scan every window and take its max directly:
function maxSlidingWindow(nums, k) {
const res = [];
for (let i = 0; i + k <= nums.length; i++) {
let max = nums[i];
for (let j = i + 1; j < i + k; j++) {
if (nums[j] > max) max = nums[j];
}
res.push(max);
}
return res;
}This is O(n·k): about n windows, each rescanned in O(k). With n = 10⁵ and k = 5·10⁴, that's billions of comparisons — a guaranteed time limit exceeded.
The waste is obvious once you see it. Consecutive windows share k - 1 elements. When the window slides one step, the brute force forgets everything it learned and re-derives the max of k - 1 numbers it already examined. The whole game is remembering the useful part of what you've seen.
The key insight: smaller and older means never the max
What exactly is worth remembering? Not the full window — only the elements that could still become a maximum.
Suppose the window contains ... 3, -1 ... and a 5 arrives. The 3 and the -1 are now both smaller than 5 and older than 5 — they will leave the window before 5 does. There is no future window where either of them beats 5. They're not just unlikely candidates; they're mathematically impossible ones. Discard them.
Do this consistently and the surviving candidates form a decreasing sequence: the deque. New elements enter at the back, bulldozing every smaller value on their way in. The front therefore always holds the current window's maximum — answering "what's the max?" becomes an O(1) peek. This is the sliding window + monotonic deque pattern (you'll also hear "monotonic queue").
Two maintenance rules keep it honest:
- Back eviction (on arrival): before pushing
arr[j], pop every tail value strictly smaller than it. - Front eviction (on departure): when the element leaving the window is the deque's front, shift it off — its reign is over.
The optimal solution
This is the exact algorithm the interactive visualizer steps through — same structure, same variable names:
var maxSlidingWindow = function (arr, k) {
let res = [];
let q = []; // deque of values, decreasing front → back
let i = 0, j = 0; // i = window start, j = window end
while (j < arr.length) {
// Back eviction: arr[j] bulldozes smaller tails
while (q.length && arr[j] > q[q.length - 1]) {
q.pop();
}
q.push(arr[j]);
if (j >= k - 1) {
res.push(q[0]); // front is the window max
if (arr[i] === q[0]) q.shift(); // front eviction if it's leaving
++i;
}
++j;
}
return res;
};Three details carry all the correctness:
- The pop condition is strictly
>, not>=. Equal values stay in the deque as duplicates. That's what makes the front-eviction checkarr[i] === q[0]safe: if two 5s are in the window, the deque holds both, and shifting one when the older 5 exits still leaves the other on duty. j >= k - 1gates output. No maximum is recorded until the window has grown to a fullkelements; before that, the loop only builds up the deque.ionly advances after recording. Each loop iteration past the warm-up produces exactly one answer and slides the window exactly one step.
Walkthrough: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
One row per j iteration. "Back pops" happen before the push; "front evict" happens after recording, when arr[i] matches q[0].
| j | arr[j] | Back pops | q after push | res | Front evict? |
|---|---|---|---|---|---|
| 0 | 1 | — | [1] | [] | window not full |
| 1 | 3 | 1 | [3] | [] | window not full |
| 2 | -1 | — | [3, -1] | [3] | no — arr[0]=1 ≠ 3 |
| 3 | -3 | — | [3, -1, -3] | [3, 3] | yes — arr[1]=3 = q[0] → q=[-1, -3] |
| 4 | 5 | -3, -1 | [5] | [3, 3, 5] | no — arr[2]=-1 ≠ 5 |
| 5 | 3 | — | [5, 3] | [3, 3, 5, 5] | no — arr[3]=-3 ≠ 5 |
| 6 | 6 | 3, 5 | [6] | [3, 3, 5, 5, 6] | no — arr[4]=5 ≠ 6 |
| 7 | 7 | 6 | [7] | [3, 3, 5, 5, 6, 7] | no — arr[5]=3 ≠ 7 |
Two rows deserve a second look. At j = 3, the outgoing 3 is the deque front, so it gets shifted — and the max correctly drops to -1 for the next window's benefit. At j = 4, the arriving 5 bulldozes the entire deque (-3, then -1) in two pops: everything smaller and older dies at once. Notice the deque never holds more than three values, and every value enters it exactly once.
Complexity
| Approach | Time | Space | Why |
|---|---|---|---|
| Brute force | O(n·k) | O(1) | rescans k elements for each of ~n windows |
| Max-heap | O(n log n) | O(n) | log-time inserts; stale entries lazily discarded |
| Monotonic deque | O(n) | O(k) | each element is pushed once and popped at most once |
The O(n) claim looks suspicious next to that nested while loop, but it's an amortized argument: the inner loop's total work across the entire run is bounded by the number of pops, and you can't pop an element more times than it was pushed. n pushes → at most n pops → O(n) overall. The deque never exceeds k entries, since everything in it lives inside the current window.
Common mistakes
- Popping with
>=instead of>. Collapsing duplicates seems harmless until two equal maxes share a window. With one copy stored, the older one leaving the window shifts the front — and the still-valid twin's max vanishes. Strict>keeps duplicates and keepsarr[i] === q[0]eviction correct. - Forgetting front eviction entirely. Without the
arr[i] === q[0]shift, a huge early value haunts the deque forever and gets reported as the max of windows it no longer belongs to. A descending array like[9, 8, 7, 6, 5]exposes this instantly. - Recording before the window is full. Drop the
j >= k - 1guard and you emit maxes for partial windows, producingk - 1extra bogus entries at the front ofres. - Maintaining the whole window in the deque. The deque holds candidates, not contents. If your deque always has
kelements, you skipped the back-eviction step and you're just doing brute force with extra ceremony. - Treating the deque as sorted storage to binary-search. Its order falls out of eviction, not sorting — the max is always at the front, so there is never anything to search.
Where this pattern shows up next
Sliding Window Maximum is the capstone of the two-pointers-and-window family — same track, escalating machinery:
- Two Sum — where the "remember the useful part of what you've seen" instinct first appears, with a hash map instead of a deque.
- Two Sum II - Input Array Is Sorted — the cleanest introduction to two pointers converging over an array.
- Is Subsequence — two pointers advancing independently through two sequences.
- Find the Index of the First Occurrence in a String — a sliding window over strings, matching instead of maximizing.
The best way to make the deque click is to watch it work: step through it interactively and watch new elements bulldoze smaller tails while the crown sits on the front of the queue.
FAQ
Why does the deque store values instead of indices?
Either works; this implementation stores values and tracks the window start with a separate pointer i. Because the pop condition is strictly greater-than, duplicates survive in the deque, so evicting the front when arr[i] === q[0] removes exactly one copy — the oldest — which is precisely the one leaving the window. The index-storing variant instead checks whether the front index has fallen out of range (front <= j - k); it's the better choice when you need positions as well as values, but for this problem the value version is equivalent and slightly simpler to read.
What is the time complexity of Sliding Window Maximum with a monotonic deque?
O(n) time and O(k) space. The nested loop is deceptive: each array element is pushed onto the deque exactly once and popped at most once over the whole run, so total deque operations are bounded by 2n. The deque itself can never hold more than k values, since every entry belongs to the current window.
Can I solve Sliding Window Maximum with a max-heap instead?
Yes, in O(n log n): push (value, index) pairs into a max-heap, and before reading the top of the heap, discard entries whose index has slid out of the window (lazy deletion). It passes, but it's both asymptotically and practically slower than the deque, and the lazy-deletion bookkeeping is easier to get wrong in an interview. The deque is the expected answer.
Why must the deque be kept in decreasing order?
Decreasing order is exactly the set of elements that could still become a window maximum. Any element smaller than something newer is permanently dominated — the newer, bigger element will outlive it in the window — so it's evicted on arrival. What remains is decreasing by construction, which puts the current maximum at the front for O(1) access and means the next-best candidate is already waiting right behind it when the front expires.
Is Array.prototype.shift() a problem for performance here?
Not meaningfully. shift() on a JavaScript array is O(m) in the array's length, but the deque never exceeds k elements and the front is shifted at most once per window, so the worst case stays well within limits for n up to 10⁵. In languages with a real double-ended queue (Python's collections.deque, C++'s std::deque), both ends are true O(1); in JavaScript you could use a head-pointer instead of shift() if you wanted to be strict about constants.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.