Sliding Window Maximum
Monotonic deque — the front is always the answer
The obvious loop re-reads all k cells for every window, which is O(n·k) and repeats work the previous window already did. A deque of indices fixes that with one rule: before pushing i, pop every index at the back whose value is <= nums[i]. Those are older AND smaller, so no future window can ever pick them over i. What is left is a front-to-back decreasing run, and the front is the window's maximum for free. One more check per step — drop the front if it has slid out of range — keeps the deque honest about which window it is describing.
Details
Animated on: nums = [5,3,4,1,2,6], k = 3 — report the maximum of every window of 3 consecutive numbers.
Problem:Sliding Window MaximumHard
Pattern:Monotonic Queue
Monotonic deque — the front is always the answer
step 1 / 10
nums=[5,3,4,1,2,6], k=3. Re-scanning all 3 cells per window would be O(n·k). Instead keep a deque of INDICES whose values fall from front to back — then the front is always the current window's maximum, and every element is pushed and popped at most once.
1FUNCTION maxSlidingWindow(nums, k):2 dq <- empty deque of indices3 out <- empty list4 FOR i <- 0 TO LENGTH(nums) - 1:5 IF dq NOT EMPTY AND FRONT(dq) <= i - k:6 REMOVE FRONT(dq)7 WHILE dq NOT EMPTY AND nums[BACK(dq)] <= nums[i]:8 REMOVE BACK(dq)9 APPEND i TO dq10 IF i >= k - 1:11 APPEND nums[FRONT(dq)] TO out12 RETURN out
← / → step · space play · Home restart
Every step in words
Show all 10 steps
- nums=[5,3,4,1,2,6], k=3. Re-scanning all 3 cells per window would be O(n·k). Instead keep a deque of INDICES whose values fall from front to back — then the front is always the current window's maximum, and every element is pushed and popped at most once.
- The deque is empty, so nums[0]=5 simply becomes the first candidate. Deque [5]. Only 1 of 3 cells is in view, so no answer is emitted yet.
- nums[1]=3 is smaller than 5 at the back, so nothing is popped — a smaller-but-newer value still matters, because it becomes the answer once the bigger ones ahead of it expire. Deque [5,3]. Only 2 of 3 cells are in view, so no answer is emitted yet.
- nums[2]=4 is at least as big as 3 sitting behind it, and it arrived LATER — that value can never be the max of any window that still contains index 2, so it is dead weight and gets popped. Deque [5,4], so the front — index 0, value 5 — is the max of window [0..2]. Answers so far: [5].
- The window has moved to [1..3], so index 0 (value 5) is behind it now. It was the front, so the answer it was holding expires — drop it and index 2 inherits the front. Deque is now [4].
- nums[3]=1 is smaller than 4 at the back, so nothing is popped — a smaller-but-newer value still matters, because it becomes the answer once the bigger ones ahead of it expire. Deque [4,1], so the front — index 2, value 4 — is the max of window [1..3]. Answers so far: [5,4].
- nums[4]=2 is at least as big as 1 sitting behind it, and it arrived LATER — that value can never be the max of any window that still contains index 4, so it is dead weight and gets popped. Deque [4,2], so the front — index 2, value 4 — is the max of window [2..4]. Answers so far: [5,4,4].
- The window has moved to [3..5], so index 2 (value 4) is behind it now. It was the front, so the answer it was holding expires — drop it and index 4 inherits the front. Deque is now [2].
- nums[5]=6 is at least as big as 2 sitting behind it, and it arrived LATER — that value can never be the max of any window that still contains index 5, so it is dead weight and gets popped. Deque [6], so the front — index 5, value 6 — is the max of window [3..5]. Answers so far: [5,4,4,6].
- The 4 shaded cells are where each window ended, in order: [5,4,4,6]. Every index entered the deque once and left at most once, so the whole pass is O(n) despite there being 4 windows of 3 to answer.
Now solve it yourself
Watching is the first half. The second is writing it without the animation.