Sliding Window Maximum (LeetCode 239)
Take the integer array nums and look at it through a frame exactly k elements wide. The frame starts over the first k elements and moves right by one element at a time, until it covers the last k.
For every position of the frame, write down the largest value inside it. Return these maxima as a list, from the leftmost position of the frame to the rightmost: len(nums) - k + 1 values in all.
Worked Examples
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]nums = [1], k = 1[1]⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Core Insight
A value that arrives later and is at least as large makes every older, smaller-or-equal value useless: the newer one stays in the window at least as long. Dropping those from the back leaves indices whose values strictly decrease, so the front is always the window's maximum. The window can only ever be oversized by one index, so left advances with a plain if, and the front leaves exactly when dq[0] < left, tested only after left has already moved.
Real-World Scenario & Production Applications
Monitoring dashboards that plot the peak latency or the highest price of the last few minutes, updated every tick, and signal processing that follows the loudest sample of a moving block of audio.
Subproblems & Recurrence Decomposition3 Phases
Every older value <= nums[right] can never be a window's maximum again, because nums[right] is at least as large and stays longer. Pop them from the back, then push right: the values in dq strictly decrease from front to back.
while dq and nums[dq[-1]] <= nums[right]:
dq.pop()
dq.append(right)Step-by-Step Execution Trace Table
right | nums[right] | Back: pop while nums[dq[-1]] <= nums[right] | dq after dq.append(right) | left after the boundary check | Front: dq[0] < left? | res.append(nums[dq[0]]) |
|---|---|---|---|---|---|---|
| 0 | 1 | — | [0] (values 1) | 0 | no | — (not size k yet) |
| 1 | 3 | pop 0 (1 <= 3) | [1] (values 3) | 0 | no | — (not size k yet) |
| 2 | -1 | — | [1, 2] (values 3, -1) | 0 | no | 3 |
| 3 | -3 | — | [1, 2, 3] (values 3, -1, -3) | 1 | no | 3 |
| 4 | 5 | pop 3 (-3 <= 5), 2 (-1 <= 5), 1 (3 <= 5) | [4] (values 5) | 2 | no | 5 |
| 5 | 3 | — | [4, 5] (values 5, 3) | 3 | no | 5 |
| 6 | 6 | pop 5 (3 <= 6), 4 (5 <= 6) | [6] (values 6) | 4 | no | 6 |
| 7 | 7 | pop 6 (6 <= 7) | [7] (values 7) | 5 | no | 7 |
The back-eviction loop happens to clear every stale index before the front check runs on this example, so the front check never fires here; see the card's first gotcha (nums = [9, 8, 7, 6, 5, 4], k = 2) for a trace where it does.
| 1 | dq = deque() |
| 2 | res = [] # indices, values strictly decreasing |
| 3 | left = 0 |
| 4 | for right in range(len(nums)): |
| 5 | while dq and nums[dq[-1]] <= nums[right]: |
| 6 | dq.pop() |
| 7 | dq.append(right) |
| 8 | if right - left + 1 > k: |
| 9 | left += 1 |
| 10 | if dq and dq[0] < left: |
| 11 | dq.popleft() |
| 12 | if right - left + 1 == k: |
| 13 | res.append(nums[dq[0]]) |
| 14 | return res |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Re-scanning all k values of the window at every step is the obvious approach, and also the slow one. A heap would give the maximum faster, but it can't cheaply drop the value that just left the window. A monotonic deque keeps only the values that can still be a window's maximum, as indices whose values strictly decrease from front to back, so the answer is always at the front.
📐 What a Monotonic Deque Is
A monotonic deque is a double-ended queue of array indices. A double-ended queue can add and remove items at both ends in O(1) time; Python's collections.deque is one. Three rules hold after every step:
- Index order. The indices in
dqincrease from front to back. They are not always next to each other, because some indices were removed. The front is the oldest index, and the back is the newest. - Value order. The values at those indices move in one direction only, with no two equal. For a maximum, they strictly decrease from front to back, so
nums[dq[0]]is the largest. For a minimum, they strictly increase, sonums[dq[0]]is the smallest. - Only candidates stay. Every index in
dqcan still be the answer for the current window or a later one. An index leaves in one of two ways:- From the back, when a newer index arrives whose value is at least as large (for a maximum) or at most as large (for a minimum). The newer index stays in every later window that the older index is in, so the older index can never be the answer again.
- From the front, when the problem says the front index can no longer be used. In Sliding Window Maximum (LC 239), that happens once the window's own
leftpointer passes it:dq[0] < left, tested only afterlefthas already advanced.
Each index enters dq once and leaves it at most once, so one pass over the array costs O(N).
🔁 The Same Deque Beyond the Window Maximum
The three rules stay the same. Three choices change from problem to problem.
| What changes | Sliding Window Maximum (LC 239) | Window minimum | Jump Game VI (LC 1696) |
|---|---|---|---|
| The values the indices point to | nums[right] | nums[i] | score[i], the best total when standing on index i |
| Value order, front to back | strictly decreasing | strictly increasing | strictly decreasing |
| Back pop test | nums[dq[-1]] <= nums[right] | nums[dq[-1]] >= nums[i] | score[dq[-1]] <= score[i] |
| When the front leaves | dq[0] < left, after left advances | dq[0] <= i - k | dq[0] < i - k |
The front test depends on how the problem defines its window. Sliding Window Maximum (LC 239) tracks the window's own left edge in an explicit left pointer: once the window holds more than k indices, left moves forward one step, and only then is the front tested against it, because testing it against left's old value misses the index that just fell behind. In Jump Game VI (LC 1696), the indices you can jump from are i - k to i - 1, so index i - k can still be used, and only indices below it leave. Constrained Subsequence Sum (LC 1425) uses the same deque as Jump Game VI (LC 1696). Shortest Subarray with Sum at Least K (LC 862) uses the same three rules on prefix sums, with its own test for when the front leaves.
🏆 The Analogy: A Leaderboard That Removes Everyone Who Can No Longer Win
Imagine a live leaderboard of "candidates for tallest person in the room." Every time a new person walks in, you don't just add them: you first remove everyone already on the leaderboard who is not taller than the newcomer, because they will leave the room first and can never be the tallest while the newcomer is still there. The leaderboard therefore stays sorted tallest-to-shortest from front to back, and the front is always, instantly, the tallest person in the room. When someone's time is up (they slide out of the window), you only need to check whether they are the person at the front.
🔑 The Key Idea in the Code
The deque stores indices so the front check can tell when the leader has left: once the window holds more than k indices, left moves forward one step, and the test dq[0] < left must run after that move, against left's new value, or the index that just fell behind stays at the front for one window too long. Each index is pushed once and popped at most once across the whole array, which keeps the total work at O(N) instead of O(N·k).
Popping the front on
dq[0] < i - kWriting the front cutoff as
k - iinstead ofi - kStoring values in
dqinstead of indicesAppending to
resbefore the first window is fullKeeping the
<=pop test for a window minimum
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement moves a window of fixed width k one step at a time and asks for the largest value in every window. Every step adds one value and drops one, and each step needs the current maximum: rescanning costs k per step and a heap can't cheaply drop the value that left. A maximum over a window that slides is the Monotonic Deque.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision at each right: pop the back while nums[dq[-1]] <= nums[right], push right, advance left with if right - left + 1 > k: left += 1, pop the front with if dq[0] < left: dq.popleft(), and read nums[dq[0]] once right - left + 1 == k.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
leftmust advance before the front is tested: the test is against the window's new edge (gotcha 1 has the failing input).dq.append(right): push the index, not the value (gotcha 4).if right - left + 1 > k, not>= k: shrinking one step early collapses the window below sizekforever (gotcha 2).nums[dq[-1]] <= nums[right]: flip to>=only for a window minimum (gotcha 5).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use a Monotonic Deque. I keep a deque of indices whose values strictly decrease from front to back, so the front is always the largest value still in the window, plus an explicit left pointer for the window's own left edge. For each index right, I first pop from the back every index whose value is not larger than nums of right: the newcomer is at least as big and stays in the window longer, so those values can never be a maximum again. I push right. The window can only ever be oversized by one index, since exactly one enters per step, so I advance left with a plain if once the window exceeds size k. Only then do I test the front against left: a value that already fell behind the window's new edge gets popped. Once the window holds exactly k elements, I append the front's value to the answer. The trap is that order: left must move before the front is tested, or an old maximum survives one window too long. Every index is pushed once and popped at most once, so it's
O(N)time and O(K) space for the deque, output not counted."
Complexity & Mathematical Proof
O(N)
Look at the code: for right in range(len(nums)) runs N times. Inside it, dq.append(right) is one push, if right - left + 1 > k: left += 1 and if dq and dq[0] < left: dq.popleft() are two checks and at most one pop, and if right - left + 1 == k with res.append(nums[dq[0]]) is one check and one append. The inner while dq and nums[dq[-1]] <= nums[right] can run many times in one step, but each dq.pop() removes an index that was appended earlier, and every index is appended exactly once, so over the whole run the while pops at most N times in total. That makes at most N appends, N pops (front and back together) and N failed while checks: O(N).
O(K)
Look at the allocations: dq only holds indices inside the window nums[left .. right], so it never has more than K entries. res holds the N - K + 1 answers, which is the output and is counted separately. There is no recursion.
Derivation Progression
for right in range(len(nums)): N passes, each with one append, one boundary check, one front check and one window check
Everything outside the inner while costs a constant amount per index.
total dq.pop() + dq.popleft() <= total dq.append(right) = N
An index can only be popped after it was appended, and each index is appended once, so the inner while pops at most N times across all passes together, not N per pass.
N + N + N = O(N)
Appends, pops and the one failing while check per pass add up to a constant times N.
Variable Definitions
len(nums), the number of values
k, the window size (1 <= K <= N)
Memory Architecture & Bounds
O(1): no recursion
O(K): dq holds only indices inside the current window
O(N - K + 1): res, one maximum per window (output, not counted)
Boundary Best / Worst Cases
: strictly decreasing input, nothing is popped from the back and the front leaves once per step
: strictly increasing input, each new value pops the one before it
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "a frame exactly k elements wide", "write down the largest value inside it". Every step adds one value and drops one, and every step needs the current maximum: the maximum of a window that slides is the Monotonic Deque, not a rescan and not a heap.
, , values in . Rescanning every window is , up to about comparisons when . A heap gives but cannot cheaply drop the value that just left, so it needs lazy deletion. The deque does at most pushes and pops and holds at most indices, so it also works on a stream where only the last values are kept.
On a time-based window (the last 5 minutes rather than the last k samples), several samples can expire at once, so the single front check becomes a while loop over expired timestamps. With samples arriving out of order, the deque's increasing-position order breaks, so late samples must be buffered or dropped before they reach it.
Core Algorithmic State Invariants
- Only the Front Can Be Too Old
dq holds indices in increasing order, so the oldest index still stored is always at the front, and the window nums[i - k + 1 .. i] loses exactly one index per step. That is why a single if suffices at the front, while the back needs a while: many older values can be dominated by one newcomer.
Sliding Window Maximum (LeetCode 239)
Take the integer array nums and look at it through a frame exactly k elements wide. The frame starts over the first k elements and moves right by one element at a time, until it covers the last k.
For every position of the frame, write down the largest value inside it. Return these maxima as a list, from the leftmost position of the frame to the rightmost: len(nums) - k + 1 values in all.
Worked Examples
nums = [1,3,-1,-3,5,3,6,7], k = 3[3,3,5,5,6,7]nums = [1], k = 1[1]⚖️Formal Constraints & Bounds
1 <= nums.length <= 105-104 <= nums[i] <= 1041 <= k <= nums.length
Core Insight
A value that arrives later and is at least as large makes every older, smaller-or-equal value useless: the newer one stays in the window at least as long. Dropping those from the back leaves indices whose values strictly decrease, so the front is always the window's maximum. The window can only ever be oversized by one index, so left advances with a plain if, and the front leaves exactly when dq[0] < left, tested only after left has already moved.
Real-World Scenario & Production Applications
Monitoring dashboards that plot the peak latency or the highest price of the last few minutes, updated every tick, and signal processing that follows the loudest sample of a moving block of audio.
Subproblems & Recurrence Decomposition3 Phases
Every older value <= nums[right] can never be a window's maximum again, because nums[right] is at least as large and stays longer. Pop them from the back, then push right: the values in dq strictly decrease from front to back.
while dq and nums[dq[-1]] <= nums[right]:
dq.pop()
dq.append(right)Step-by-Step Execution Trace Table
right | nums[right] | Back: pop while nums[dq[-1]] <= nums[right] | dq after dq.append(right) | left after the boundary check | Front: dq[0] < left? | res.append(nums[dq[0]]) |
|---|---|---|---|---|---|---|
| 0 | 1 | — | [0] (values 1) | 0 | no | — (not size k yet) |
| 1 | 3 | pop 0 (1 <= 3) | [1] (values 3) | 0 | no | — (not size k yet) |
| 2 | -1 | — | [1, 2] (values 3, -1) | 0 | no | 3 |
| 3 | -3 | — | [1, 2, 3] (values 3, -1, -3) | 1 | no | 3 |
| 4 | 5 | pop 3 (-3 <= 5), 2 (-1 <= 5), 1 (3 <= 5) | [4] (values 5) | 2 | no | 5 |
| 5 | 3 | — | [4, 5] (values 5, 3) | 3 | no | 5 |
| 6 | 6 | pop 5 (3 <= 6), 4 (5 <= 6) | [6] (values 6) | 4 | no | 6 |
| 7 | 7 | pop 6 (6 <= 7) | [7] (values 7) | 5 | no | 7 |
The back-eviction loop happens to clear every stale index before the front check runs on this example, so the front check never fires here; see the card's first gotcha (nums = [9, 8, 7, 6, 5, 4], k = 2) for a trace where it does.
| 1 | dq = deque() |
| 2 | res = [] # indices, values strictly decreasing |
| 3 | left = 0 |
| 4 | for right in range(len(nums)): |
| 5 | while dq and nums[dq[-1]] <= nums[right]: |
| 6 | dq.pop() |
| 7 | dq.append(right) |
| 8 | if right - left + 1 > k: |
| 9 | left += 1 |
| 10 | if dq and dq[0] < left: |
| 11 | dq.popleft() |
| 12 | if right - left + 1 == k: |
| 13 | res.append(nums[dq[0]]) |
| 14 | return res |
Conceptual Narrative
🧭 Conceptual Foundation & Pattern Intuition
Re-scanning all k values of the window at every step is the obvious approach, and also the slow one. A heap would give the maximum faster, but it can't cheaply drop the value that just left the window. A monotonic deque keeps only the values that can still be a window's maximum, as indices whose values strictly decrease from front to back, so the answer is always at the front.
📐 What a Monotonic Deque Is
A monotonic deque is a double-ended queue of array indices. A double-ended queue can add and remove items at both ends in O(1) time; Python's collections.deque is one. Three rules hold after every step:
- Index order. The indices in
dqincrease from front to back. They are not always next to each other, because some indices were removed. The front is the oldest index, and the back is the newest. - Value order. The values at those indices move in one direction only, with no two equal. For a maximum, they strictly decrease from front to back, so
nums[dq[0]]is the largest. For a minimum, they strictly increase, sonums[dq[0]]is the smallest. - Only candidates stay. Every index in
dqcan still be the answer for the current window or a later one. An index leaves in one of two ways:- From the back, when a newer index arrives whose value is at least as large (for a maximum) or at most as large (for a minimum). The newer index stays in every later window that the older index is in, so the older index can never be the answer again.
- From the front, when the problem says the front index can no longer be used. In Sliding Window Maximum (LC 239), that happens once the window's own
leftpointer passes it:dq[0] < left, tested only afterlefthas already advanced.
Each index enters dq once and leaves it at most once, so one pass over the array costs O(N).
🔁 The Same Deque Beyond the Window Maximum
The three rules stay the same. Three choices change from problem to problem.
| What changes | Sliding Window Maximum (LC 239) | Window minimum | Jump Game VI (LC 1696) |
|---|---|---|---|
| The values the indices point to | nums[right] | nums[i] | score[i], the best total when standing on index i |
| Value order, front to back | strictly decreasing | strictly increasing | strictly decreasing |
| Back pop test | nums[dq[-1]] <= nums[right] | nums[dq[-1]] >= nums[i] | score[dq[-1]] <= score[i] |
| When the front leaves | dq[0] < left, after left advances | dq[0] <= i - k | dq[0] < i - k |
The front test depends on how the problem defines its window. Sliding Window Maximum (LC 239) tracks the window's own left edge in an explicit left pointer: once the window holds more than k indices, left moves forward one step, and only then is the front tested against it, because testing it against left's old value misses the index that just fell behind. In Jump Game VI (LC 1696), the indices you can jump from are i - k to i - 1, so index i - k can still be used, and only indices below it leave. Constrained Subsequence Sum (LC 1425) uses the same deque as Jump Game VI (LC 1696). Shortest Subarray with Sum at Least K (LC 862) uses the same three rules on prefix sums, with its own test for when the front leaves.
🏆 The Analogy: A Leaderboard That Removes Everyone Who Can No Longer Win
Imagine a live leaderboard of "candidates for tallest person in the room." Every time a new person walks in, you don't just add them: you first remove everyone already on the leaderboard who is not taller than the newcomer, because they will leave the room first and can never be the tallest while the newcomer is still there. The leaderboard therefore stays sorted tallest-to-shortest from front to back, and the front is always, instantly, the tallest person in the room. When someone's time is up (they slide out of the window), you only need to check whether they are the person at the front.
🔑 The Key Idea in the Code
The deque stores indices so the front check can tell when the leader has left: once the window holds more than k indices, left moves forward one step, and the test dq[0] < left must run after that move, against left's new value, or the index that just fell behind stays at the front for one window too long. Each index is pushed once and popped at most once across the whole array, which keeps the total work at O(N) instead of O(N·k).
Popping the front on
dq[0] < i - kWriting the front cutoff as
k - iinstead ofi - kStoring values in
dqinstead of indicesAppending to
resbefore the first window is fullKeeping the
<=pop test for a window minimum
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
The statement moves a window of fixed width k one step at a time and asks for the largest value in every window. Every step adds one value and drops one, and each step needs the current maximum: rescanning costs k per step and a heap can't cheaply drop the value that left. A maximum over a window that slides is the Monotonic Deque.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Decision at each right: pop the back while nums[dq[-1]] <= nums[right], push right, advance left with if right - left + 1 > k: left += 1, pop the front with if dq[0] < left: dq.popleft(), and read nums[dq[0]] once right - left + 1 == k.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
leftmust advance before the front is tested: the test is against the window's new edge (gotcha 1 has the failing input).dq.append(right): push the index, not the value (gotcha 4).if right - left + 1 > k, not>= k: shrinking one step early collapses the window below sizekforever (gotcha 2).nums[dq[-1]] <= nums[right]: flip to>=only for a window minimum (gotcha 5).
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I'll use a Monotonic Deque. I keep a deque of indices whose values strictly decrease from front to back, so the front is always the largest value still in the window, plus an explicit left pointer for the window's own left edge. For each index right, I first pop from the back every index whose value is not larger than nums of right: the newcomer is at least as big and stays in the window longer, so those values can never be a maximum again. I push right. The window can only ever be oversized by one index, since exactly one enters per step, so I advance left with a plain if once the window exceeds size k. Only then do I test the front against left: a value that already fell behind the window's new edge gets popped. Once the window holds exactly k elements, I append the front's value to the answer. The trap is that order: left must move before the front is tested, or an old maximum survives one window too long. Every index is pushed once and popped at most once, so it's
O(N)time and O(K) space for the deque, output not counted."
Complexity & Mathematical Proof
O(N)
Look at the code: for right in range(len(nums)) runs N times. Inside it, dq.append(right) is one push, if right - left + 1 > k: left += 1 and if dq and dq[0] < left: dq.popleft() are two checks and at most one pop, and if right - left + 1 == k with res.append(nums[dq[0]]) is one check and one append. The inner while dq and nums[dq[-1]] <= nums[right] can run many times in one step, but each dq.pop() removes an index that was appended earlier, and every index is appended exactly once, so over the whole run the while pops at most N times in total. That makes at most N appends, N pops (front and back together) and N failed while checks: O(N).
O(K)
Look at the allocations: dq only holds indices inside the window nums[left .. right], so it never has more than K entries. res holds the N - K + 1 answers, which is the output and is counted separately. There is no recursion.
Derivation Progression
for right in range(len(nums)): N passes, each with one append, one boundary check, one front check and one window check
Everything outside the inner while costs a constant amount per index.
total dq.pop() + dq.popleft() <= total dq.append(right) = N
An index can only be popped after it was appended, and each index is appended once, so the inner while pops at most N times across all passes together, not N per pass.
N + N + N = O(N)
Appends, pops and the one failing while check per pass add up to a constant times N.
Variable Definitions
len(nums), the number of values
k, the window size (1 <= K <= N)
Memory Architecture & Bounds
O(1): no recursion
O(K): dq holds only indices inside the current window
O(N - K + 1): res, one maximum per window (output, not counted)
Boundary Best / Worst Cases
: strictly decreasing input, nothing is popped from the back and the front leaves once per step
: strictly increasing input, each new value pops the one before it
Pointer Invariant Transition Progression
Senior SWE Deconstruction & Hardware Caveats
Triggers: "a frame exactly k elements wide", "write down the largest value inside it". Every step adds one value and drops one, and every step needs the current maximum: the maximum of a window that slides is the Monotonic Deque, not a rescan and not a heap.
, , values in . Rescanning every window is , up to about comparisons when . A heap gives but cannot cheaply drop the value that just left, so it needs lazy deletion. The deque does at most pushes and pops and holds at most indices, so it also works on a stream where only the last values are kept.
On a time-based window (the last 5 minutes rather than the last k samples), several samples can expire at once, so the single front check becomes a while loop over expired timestamps. With samples arriving out of order, the deque's increasing-position order breaks, so late samples must be buffered or dropped before they reach it.
Core Algorithmic State Invariants
- Only the Front Can Be Too Old
dq holds indices in increasing order, so the oldest index still stored is always at the front, and the window nums[i - k + 1 .. i] loses exactly one index per step. That is why a single if suffices at the front, while the back needs a while: many older values can be dominated by one newcomer.