You are given a list of numbers nums and a window size k. A window of k numbers starts at the left end and slides right, one step at a time, until it reaches the right end. For every position of the window, report the biggest number inside it.
Each slide adds one number on the right and removes one on the left. Adding is easy: compare the new number with the current biggest. Removing is the hard part. If the number leaving was the biggest, what is the new biggest? You would have to look through the whole window again.
So the real question is: how do you keep track of the maximum when numbers keep leaving from the other end?
Here is the observation that unlocks an O(n) answer.
If a smaller number arrived before a bigger number, the smaller one can never be the window's maximum again.
Why? The bigger number arrived later, so it will stay in the window for at least as long as the smaller one. Every future window that still contains the smaller number also contains the bigger one. So the smaller number is useless from now on, and we can forget it.
Think of students walking into a classroom while older students leave from the other door, and you want to know the tallest student in the room. A very tall student walks in. Every shorter student who arrived earlier will leave before this one does. So none of them can ever be the tallest in the room again. We stop keeping track of them.
If we keep throwing away useless numbers like this, the ones left over are always in decreasing order from oldest to newest. The oldest one, at the front, is the biggest. That is the window's maximum.
The structure that holds them is a deque, pronounced "deck", short for "double-ended queue". It is a list that lets you add and remove at both ends in constant time. We use the back to add new numbers and throw away smaller ones. We use the front to read the maximum, and to remove it once it slides out of the window. A deque whose contents always go in one direction like this is called a monotonic deque. "Monotonic" means "always moving one way", here always decreasing.
We store positions, not the numbers themselves. A position tells us when an entry has slid out of the window. A number alone cannot.
The deque keeps only the values that could still become the maximum.
from collections import dequeclass Solution: def maxSlidingWindow(self, nums: List[int], k: int) -> List[int]: dq = deque() # (1) result = [] for i in range(len(nums)): # (2) if dq and dq[0] <= i - k: # (3) dq.popleft() while dq and nums[dq[-1]] < nums[i]: # (4) dq.pop() dq.append(i) # (5) if i >= k - 1: # (6) result.append(nums[dq[0]]) return result
ts
function maxSlidingWindow(nums: number[], k: number): number[] { const dq: number[] = []; // (1) let head = 0; // front of the deque const result: number[] = []; for (let i = 0; i < nums.length; i++) { // (2) if (head < dq.length && dq[head] <= i - k) head++; // (3) while (dq.length > head && nums[dq[dq.length - 1]] < nums[i]) { // (4) dq.pop(); } dq.push(i); // (5) if (i >= k - 1) result.push(nums[dq[head]]); // (6) } return result;}
(1) The deque. It holds positions in the list. The numbers at those positions always decrease from front to back.
In Python, collections.deque removes from the front in constant time. A plain Python list with pop(0) does not. It shifts every other item down by one, which costs up to k steps, and that would turn this into the slow solution again.
JavaScript arrays have the same problem with shift(). So the TypeScript version never really removes from the front. It keeps a number head that marks where the front is, and moves head forward instead. Everything before head is treated as gone.
(2) Visit each position i in turn. Position i is the right edge of the current window. The window covers positions i - k + 1 to i.
(3) Drop the front if it has slid out. The front position is outside the window when it is i - k or smaller. Only one position leaves per step, so one check is enough. This is an if, not a while.
(4) Throw away smaller numbers from the back. While the number at the back is smaller than the new number, it can never be the maximum again, so we remove it. When this loop ends, everything left is at least as big as nums[i], so adding i keeps the order decreasing.
We use <, not <=. With <=, an equal number would also be thrown away. The answer would still be right, but keeping equal numbers is simpler to reason about and costs nothing.
(5) Add the new position at the back. It might become the maximum later, after the bigger numbers in front of it slide out.
(6) Report the maximum once the first full window exists. The first window covers positions 0 to k - 1. So from i = k - 1 onward, every step completes a window, and the front of the deque is its maximum.
Take nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3. The deque is shown as the numbers at its positions, front first.
i
nums[i]
Front slid out?
Thrown from back
Deque after
Output
0
1
—
—
[1]
(window not full)
1
3
—
1
[3]
(window not full)
2
−1
—
—
[3, −1]
3
3
−3
no
—
[3, −1, −3]
3
4
5
yes, the 3 at position 1
−3, −1
[5]
5
5
3
—
—
[5, 3]
5
6
6
—
3, 5
[6]
6
7
7
—
6
[7]
7
The answer is [3, 3, 5, 5, 6, 7]. ✓
Look at row 4. The 3 at the front was at position 1, and the window now covers positions 2 to 4, so it slid out. Then the new 5 threw away both −3 and −1, because they arrived earlier and are smaller.
Time. Again there is a while loop inside a for loop, and again it is not O(n^2). Count the total work over the whole run.
Each position is added to the deque exactly once, in line (5). That is n additions in total.
Each position is removed at most once, either from the back in line (4) or from the front in line (3). A position that has been removed is never added again. So there are at most n removals in total.
So the deque does at most 2n operations over the entire run, each in constant time. Everything else is constant work per step. The total is O(n).
Space. The deque only holds positions inside the current window, so at most k of them. The extra memory is O(k), not counting the answer list.
k = 1. Every window is one number, so the answer is the list itself. The code handles it: each new number throws out the previous one or the front slides out.
Numbers only go down, like [5, 4, 3, 2, 1]. Nothing is ever thrown from the back. The deque grows to k entries, and the front slides out each step.
Numbers only go up, like [1, 2, 3, 4, 5]. Each new number throws out everything. The deque never holds more than one entry.
Repeated numbers, like [2, 2, 2]. Because line (4) uses <, equal numbers stay. The front slides out on time, and the next equal number takes over.
A heap is a structure that always keeps its biggest (or smallest) item at the top. You can push every number with its position into a heap that keeps the biggest on top. Before reading the top, throw away any top entry whose position has slid out of the window.
That is O(n \log k) time, because each push or pop on a heap costs O(\log k). Old entries may linger deep inside the heap until they reach the top, so the memory can grow to O(n). It is easier to write and a perfectly good first answer. The deque is the one that reaches O(n).
Sliding window minimum. Flip the comparison in line (4) to >. The deque then keeps increasing numbers, and the front is the smallest.
Jump Game VI. At each position you may jump up to k steps back, and you want the best total score. The best score at a position needs the biggest score among the last k positions. A monotonic deque gives that in constant time per step, turning an O(n \cdot k) solution into O(n).
Shortest Subarray with Sum at Least K. With negative numbers, a plain window breaks. The answer combines running totals with a monotonic deque.
The general lesson: when you need the biggest or smallest value over a range that slides forward, a monotonic deque gives it in constant time per step. That is why this problem is worth the effort. It is a building block for harder problems.
"Why is this O(n) when there is a loop inside a loop?" Each position enters the deque once and leaves at most once, so the total deque work is at most 2n.
"Why store positions instead of numbers?" You need to know when an entry has slid out of the window, and only the position tells you that.
"Why < and not <= when throwing away?" Either works. With <, equal numbers are kept, which is simpler to reason about.
"Could you use a heap?" Yes, O(n \log k), removing stale entries when they reach the top. Say that, then say why the deque is faster.
"What if you needed the minimum instead?" Flip the comparison. Answering that instantly shows you understood the structure, not just this problem.
One thing to volunteer: say the throw-away rule as a sentence. "A smaller number that arrived earlier can never be the maximum again, because the bigger, later number outlasts it." Everything in the code follows from that.
Next:4.7 Linked Lists, Stacks and Queues. It covers the structures behind this deque, and the stack that the next group of problems is built on.