Sliding Window Maximum (Two Pointers)
Two pointers bound the window, a monotonic deque tracks the max
Two pointers l and r define the window: r advances one step at a time and l = r-k+1 trails k-1 behind, so l only enters valid range (>= 0) once the window has filled up. Recomputing the max across all k cells for every window is O(n*k) and wastes the overlap between adjacent windows. A deque of indices fixes that: before pushing r, pop every index at the back whose value is <= nums[r] — those are older AND smaller, so no window containing r can ever pick them. What survives is a front-to-back decreasing run, so the front is always the current window's maximum. The only other check is dropping the front once it falls behind l, since a value can still be the largest number seen without being inside the current window anymore.
Details
Animated on: nums = [1,3,-1,-3,5,3,6,7], k = 3 — report the maximum of every window of 3 consecutive numbers as it slides from left to right.
Problem:Sliding Window Maximum (Two Pointers)Hard
Two pointers bound the window, a monotonic deque tracks the max
step 1 / 10
nums=[1,3,-1,-3,5,3,6,7], k=3. Two pointers l and r bound the window; r sweeps right one step at a time while l = r-k+1 trails 2 behind. A deque of indices, kept strictly decreasing in value, means the front is always the max of whatever [l,r] currently covers.
- l=0· arr[0] = 1
- r=0· arr[0] = 1
1FUNCTION slidingWindowMax(nums, k)2 dq <- EMPTY LIST3 out <- EMPTY LIST4 FOR r <- 0 TO LENGTH(nums) - 15 l <- r - k + 16 WHILE dq NOT EMPTY AND nums[LAST(dq)] <= nums[r]7 REMOVE LAST FROM dq8 APPEND r TO dq9 IF FIRST(dq) < l10 REMOVE FIRST FROM dq11 IF l >= 012 APPEND nums[FIRST(dq)] TO out13 RETURN out
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- nums=[1,3,-1,-3,5,3,6,7], k=3. Two pointers l and r bound the window; r sweeps right one step at a time while l = r-k+1 trails 2 behind. A deque of indices, kept strictly decreasing in value, means the front is always the max of whatever [l,r] currently covers.
- Deque is empty, so nums[r]=nums[0]=1 becomes the first candidate. Deque [1]. l=-2 is still negative — the window hasn't reached width 3 yet, so no answer is emitted for r=0.
- nums[r]=nums[1]=3 arrived later than nums[0]=1 and is at least as large, so those earlier candidates can never win once r=1 is in range — they are popped from the back. Deque [3]. l=-1 is still negative — the window hasn't reached width 3 yet, so no answer is emitted for r=1.
- nums[r]=nums[2]=-1 is smaller than nums[1]=3 at the back, so nothing is popped — a smaller-but-newer value still matters once the larger ones ahead of it fall out of the window. Deque [3,-1] — window [0,2] reports front index 1 value 3. Answers so far: [3].
- nums[r]=nums[3]=-3 is smaller than nums[2]=-1 at the back, so nothing is popped — a smaller-but-newer value still matters once the larger ones ahead of it fall out of the window. Deque [3,-1,-3] — window [1,3] reports front index 1 value 3. Answers so far: [3,3].
- nums[r]=nums[4]=5 arrived later than nums[3]=-3 and nums[2]=-1 and nums[1]=3 and is at least as large, so those earlier candidates can never win once r=4 is in range — they are popped from the back. Deque [5] — window [2,4] reports front index 4 value 5. Answers so far: [3,3,5].
- nums[r]=nums[5]=3 is smaller than nums[4]=5 at the back, so nothing is popped — a smaller-but-newer value still matters once the larger ones ahead of it fall out of the window. Deque [5,3] — window [3,5] reports front index 4 value 5. Answers so far: [3,3,5,5].
- nums[r]=nums[6]=6 arrived later than nums[5]=3 and nums[4]=5 and is at least as large, so those earlier candidates can never win once r=6 is in range — they are popped from the back. Deque [6] — window [4,6] reports front index 6 value 6. Answers so far: [3,3,5,5,6].
- nums[r]=nums[7]=7 arrived later than nums[6]=6 and is at least as large, so those earlier candidates can never win once r=7 is in range — they are popped from the back. Deque [7] — window [5,7] reports front index 7 value 7. Answers so far: [3,3,5,5,6,7].
- l and r each move right exactly once per index and every index enters/leaves the deque at most once, so the whole sweep is O(n) despite answering 6 windows of width 3. Result: [3,3,5,5,6,7].
Now solve it yourself
Watching is the first half. The second is writing it without the animation.