What is the pricing and subscription model for Hi👋SpeedAlgo?

The entire core curriculum of 13 patterns and 225 practice problems is 100% free to access with no credit card required. New accounts get 40 free coins once, the daily claim adds +20 coins once a day, and inviting a friend earns you +25 coins when they complete their first practice step. These are the only ways to earn coins. Each AI coach question costs 1-5 coins, priced by the server according to its size. AI coaching is free with your own Google Gemini, OpenAI or OpenRouter API key (BYOK). Coins also unlock extras for 24 hours: a Recall hint level (1 coin), a Solve solution reveal (2), a LeetCode problem card's solutions (1) and a pattern's extra canonical problems (1). Nothing on the site is sold for money: coins can only be earned, never bought.

What is the refund and cancellation policy?

Hi👋SpeedAlgo sells nothing for money: there are no subscriptions, renewals or charges, so there is nothing to cancel or refund. Nothing on the site is sold for money: coins can only be earned, never bought.

Who creates and maintains the curriculum?

Hi👋SpeedAlgo is developed and maintained by Hi👋WebEnterprise (https://hiwebenterprise.com), an engineering organization focused on developer education, deliberate practice methodologies, and cognitive ergonomics for technical interviews.

How does Hi👋SpeedAlgo prepare candidates for senior and staff SWE interviews?

Rather than rote LeetCode grinding, Hi👋SpeedAlgo uses deliberate practice for each pattern: learn the loop invariant, Big-O proof and edge cases from a side-by-side template and a step-by-step debugger, rebuild the template from memory, then solve a new problem on your own against a graded test suite.

Theory Context•Two Pointers & Sliding Window

Builds on Fixed Window and Next Greater Element, which you haven’t finished yet.

P2HardBuilt on Fixed Window~4 min speedrun

Monotonic Deque (Sliding Window Maximum)

Built on

Fixed WindowThe window state is a deque of candidate indices whose values only decrease, so the window maximum is always at the front.

Grows into

Dual Monotonic Deque

The problem

Sliding Window Maximum (LC 239)(opens leetcode.com)

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.

Example 1

Input:nums = [1,3,-1,-3,5,3,6,7], k = 3

Output:[3,3,5,5,6,7]

The six windows and their maxima: [1,3,-1] -> 3, [3,-1,-3] -> 3, [-1,-3,5] -> 5, [-3,5,3] -> 5, [5,3,6] -> 6, [3,6,7] -> 7.

Monotonic Deque

sliding window ➔ deque of indices with decreasing values, an explicit left pointer ➔ front is the window maximum

Spot it when: Every position of a window that slides one step at a time needs the largest (or smallest) value inside it: the window's maximum, or the best of the last k entries of a DP table.

Monotonic Deque

Python

1	from collections import deque
2	from typing import List
3
4	def max_sliding_window(nums: List[int], k: int) -> List[int]:
5	"""Sliding Window Maximum: a deque of indices whose values only decrease; its front is the window's maximum.
6	Time: O(N) \| Space: O(K)
7	"""
8	# dq holds indices still inside the window, with their values strictly decreasing from front to back.
9	dq: deque[int] = deque()
10	res: List[int] = []
11	left = 0
12
13	for right in range(len(nums)):
14	# Phase 1: Push & Maintain Monotonicity:
15	# An older value no larger than nums[right] can never be the maximum again, so drop it from the back.
16	while dq and nums[dq[-1]] <= nums[right]:
17	dq.pop()
18	dq.append(right)
19
20	# Phase 2 & 3: Contract the Boundary, Then Evict the Stale Front:
21	# Exactly one index enters per step, so the window is oversized by at most one; left must move first,
22	# since the front is tested against the window's new edge, and left only grows by one at a time.
23	if right - left + 1 > k:
24	left += 1
25	if dq and dq[0] < left:
26	dq.popleft()
27
28	# Phase 4: Harvest the Answer:
29	# Once the window holds exactly k elements, the front of dq is its maximum.
30	if right - left + 1 == k:
31	res.append(nums[dq[0]])
32
33	return res

Invariant: dq holds the indices still inside the window, in increasing order, and their values strictly decrease from front to back, so nums[dq[0]] is the window's maximum; left is the window's own left edge, so the window is always nums[left..right].

A value that arrives later and is at least as large makes every older, smaller-or-equal value useless: the newer one stays in every window the older one is in, and in more after it. So before dq.append(right), pop from the back every index whose value is <= nums[right]. What remains in dq are the indices that can still be some window's maximum, oldest first, with values that strictly decrease. Exactly one index enters the window per step, so it can only ever be oversized by one: if right - left + 1 > k: left += 1 restores it, and because left only ever grows by one per step, at most one front index can have fallen behind it, so evicting the front is also an if, not a while: if dq and dq[0] < left: dq.popleft(). The order of those two lines is itself the trap -- left must move first, or the front is tested against the window's old edge and a value that has already left stays one window too long. Once the window holds exactly k elements, res.append(nums[dq[0]]) reads its maximum without scanning it.

See it run

Sliding Window Maximum: max_sliding_window([7, 3, 5, 1, 2], 3)

left 0right -dq []res []

The top row is nums. The bottom row shows the values of the indices that dq holds, each under its own column, so they read from oldest to newest.

left the first index of the window
right the index that was just read
left, right left and right are at the same index
front dq[0], the index of the window maximum
in dq an index kept in dq behind the front

dq and res are empty, and left is 0. The loop reads one index right at a time.

nums

dq (values)

1 / 15

Gotchas1 of 5

The trap
Gotcha 1: Evicting the stale front before advancing left
Mistake
```
if dq and dq[0] < left:
    dq.popleft()
if right - left + 1 > k:
    left += 1
```
Fix
```
if right - left + 1 > k:
    left += 1
if dq and dq[0] < left:
    dq.popleft()
```
What happens: left must move before the front is tested, because the test is against the window's new edge. Swap the order, and the front is checked against left's stale, one-step-old value: an index that has just left the window still passes the check, stays at the front for one extra step, and reports a value that should already be gone. It is evicted the step after, but by then a stale maximum has already been recorded.
Example: nums = [9, 8, 7, 6, 5, 4], k = 2
Mistake: returns [9, 9, 8, 7, 6]Fix: returns [9, 8, 7, 6, 5]
Gotcha 2: Advancing left on right - left + 1 >= k instead of > k
Mistake
```
if right - left + 1 >= k:
    left += 1
```
Fix
```
if right - left + 1 > k:
    left += 1
```
What happens: >= shrinks the window as soon as it reaches size k, one step before it is allowed to. The window can then never hold k elements at the moment Phase 4 checks for it, so the harvest condition right - left + 1 == k never fires.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns []Fix: returns [7, 5, 5]
Gotcha 3: Evicting the front on dq[0] <= left instead of dq[0] < left
Mistake
```
if dq and dq[0] <= left:
    dq.popleft()
```
Fix
```
if dq and dq[0] < left:
    dq.popleft()
```
What happens: The window is nums[left..right], so index left itself is still inside it. With <=, a front sitting exactly at left is evicted anyway, even while it is still a valid candidate, which can throw away the true maximum before it is ever read.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns [5, 5, 2]Fix: returns [7, 5, 5]
Gotcha 4: Storing values in dq instead of indices
What happens: The front must leave dq when its index falls behind left. A stored value does not say where it came from. With repeated values, a value cannot say which copy left the window. An index answers both questions.
Gotcha 5: Keeping the <= pop test for a window minimum
Mistake
```
while dq and nums[dq[-1]] <= nums[right]:
```
Fix
```
while dq and nums[dq[-1]] >= nums[right]:
```
What happens: The <= test keeps the values in dq decreasing, so the front is the maximum. For a window minimum, keep the values increasing instead. Pop while nums[dq[-1]] >= nums[right]. A window whose validity depends on both the maximum and the minimum at once runs one deque of each kind side by side instead of picking just one -- see the Dual Monotonic Deque tool, built on this card.

Not this one if…

You need the k-th largest of everything seen so far and no value ever leaves, as in Kth Largest Element in a Stream (LC 703), not the largest value of a window that drops its oldest item at every step. See Top-K Heap
Each item needs the first larger value after it, as in Daily Temperatures (LC 739): the answer belongs to the item that is popped, and nothing leaves because it got too old. See Next Greater Element

Deep Dive

Why an older, smaller value can be thrown away

The Fixed Window card keeps one number for the window, such as a sum, and updates it in O(1). A maximum cannot be updated that way. When the maximum leaves the window, the next maximum is somewhere inside, and a scan to find it costs O(K) at every step.

The deque dq solves this by keeping only the indices that can still become the maximum. Suppose nums[a] <= nums[b] and a < b. Every window that holds a and b has a maximum of at least nums[b]. The window that holds b also stays valid longer, because b leaves later than a. So a can never be the maximum again, and it can be dropped now.

That is the rule in Phase 1: while dq and nums[dq[-1]] <= nums[right]: dq.pop(). After it, the values of dq strictly decrease from front to back. The front is the largest value that is still in the window. This is the same stack as in the Next Greater Element card, with one difference: the old end of the deque can also expire, so it is a deque and not a stack.

Tracing [7, 3, 5, 1, 2] with k = 3

At right = 0 and right = 1, nothing is popped. dq holds the indices [0, 1], with values 7 and 3. The window has fewer than 3 values, so res stays empty.

At right = 2, nums[2] = 5 is larger than 3, so index 1 is popped from the back. dq is [0, 2], with values 7 and 5. The window has 3 values, so res.append(nums[dq[0]]) adds 7.

At right = 3, nums[3] = 1 is appended, and dq is [0, 2, 3]. The window now has 4 values, so left moves to 1. The front index 0 is below left, so it leaves. The front is now index 2, and res gets 5.

At right = 4, nums[4] = 2 pops index 3 (value 1). left moves to 2. The front, index 2, is not below left, so it stays. res gets 5 again, and the result is [7, 5, 5]. For nums = [1, 3, -1, -3, 5, 3, 6, 7] and k = 3, the same code gives [3, 3, 5, 5, 6, 7], the answer of Sliding Window Maximum (LC 239).

Why the order of the two window lines matters

One index enters the window at each step, so the window can be larger than k by at most one. So left moves by one, and at most one index can fall behind it. That is why both lines are an if, not a while.

The order is the trap. left += 1 must run first, and then dq[0] < left is tested against the new edge. If the front is tested first, it is compared with the old left. At right = 3 in the trace, the front index 0 is not below the old left = 0. It stays for one more step, and res gets 7 for the window [3, 5, 1], which does not hold 7.

The test is dq[0] < left and not dq[0] <= left. The window is nums[left..right], so index left is still inside it. With <=, the front at left leaves too early, and the true maximum is lost.

Store indices in dq, not values. A value cannot tell the code whether it came from a position before left, and it cannot tell two equal values apart.

The cost, and where the deque is used

Each index is appended once and popped at most once, either from the back by Phase 1 or from the front by the eviction. So the whole run is O(N) time, even though Phase 1 has a while loop. After the eviction, dq holds only indices inside the window, so it never has more than k entries and the space is O(K).

For a window minimum, keep the values increasing and pop while nums[dq[-1]] >= nums[right]. A window that needs the maximum and the minimum together uses two deques, as in the Dual Monotonic Deque card.

The deque also gives the best earlier value for a DP step. Jump Game VI (LC 1696) and Constrained Subsequence Sum (LC 1425) need the largest dp value among the last k positions. Shortest Subarray with Sum at Least K (LC 862) keeps a deque of prefix sums. The window is not fixed there, but the pop-from-the-back rule is the same.

60-Second Pitch

"I need the maximum of every window of k values in O(N). A heap needs lazy deletion and costs O(N log N), so I use a deque of indices. When a new value arrives, every older value that is not larger can never be a maximum again, so I pop it from the back. The values in the deque strictly decrease, and the front is the maximum of the window. Then I move left forward if the window is too big, and I drop the front if its index is below left. I move left first, so the front is tested against the new edge. When the window holds k values, I record nums[dq[0]]. Each index enters and leaves the deque once, so the time is O(N). The deque holds at most k indices, so the space is O(K)."

Common Questions

What is the time and space complexity?: The time is O(N). Each index is appended once and popped at most once, so the while loop in Phase 1 does O(N) pops in total. The space is O(K), because dq holds only indices inside the window. The result list is extra O(N - K + 1) space.
Why does the deque store indices and not values?: The front must leave when its index falls behind left. A value cannot say which position it came from. With repeated values, a value cannot say which copy left the window. An index answers both questions, and nums[index] gives the value.
Why pop on <= and not on <?: Both give the correct maxima. With <, an older equal value stays in dq. It is never needed, because the newer equal value stays in the window longer. For nums = [5, 5, 5, 5] and k = 3, < can hold 3 indices and <= holds 1. The card uses <= so the values strictly decrease, as the invariant says.
How would you do it with a heap, and why is the deque better?: Push (-nums[right], right) on a max-heap, and pop the top while its index is below left. Each push and pop costs O(log N), so the total is O(N log N). The heap also keeps expired entries inside it until they reach the top. The deque is O(N) and holds at most k entries.
How do you get the window minimum, or both together?: For the minimum, keep the values increasing: pop while nums[dq[-1]] >= nums[right]. For both, run max_dq and min_dq side by side and check each front for expiry. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LC 1438) is the standard problem for this.

SWE Reasoning

Spot it

Each position of a sliding window needs the maximum or the minimum of the values inside it.
The window slides by one step, so one value enters and one value leaves.
A heap works, but it needs lazy deletion of the values that left, which makes it O(N log N).
A DP value depends on the best of the last k earlier values (Jump Game VI (LC 1696)).

The invariant, step by step

dq is empty and left = 0. dq will hold indices inside nums[left..right], in increasing order.
At each right, while dq and nums[dq[-1]] <= nums[right] pops every older value that is not larger. Such a value can never be the maximum again.
dq.append(right) adds the new index. The values in dq strictly decrease from front to back.
If the window holds more than k values, left += 1 makes it hold k. This line runs first.
if dq and dq[0] < left removes the front when its index has left the window. At most one index can have left.
When the window holds exactly k values, nums[dq[0]] is the largest value in it, and res.append records it.

Traps

Testing the front before moving left. The front is compared with the old edge, so a value that has left the window stays for one more step and is recorded as a maximum.
Shrinking on right - left + 1 >= k. The window never holds k values when the harvest line runs, so res stays empty.
Evicting on dq[0] <= left. Index left is still inside the window, and its value may be the true maximum.
Storing values instead of indices. The code cannot tell when the front has left the window.
Using <= for a minimum. A window minimum needs >=, so the values in dq increase.

Practice

Canonical LeetCode:Sliding Window Maximum (LC 239)Shortest Subarray with Sum at Least K (LC 862)Jump Game VI (LC 1696)Constrained Subsequence Sum (LC 1425)

Most courses evict the front by comparing its index straight to i - k, with no separate pointer for the window's own left edge. This course keeps an explicit left, so the same front test, dq[0] < left, also works once a window's edge can move by more than one step a turn, as in the Dual Monotonic Deque.

The classic loop

Old Way

Python

1	from collections import deque
2
3	def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
4	dq = deque()
5	res = []
6
7	for i in range(len(nums)):
8	if dq and dq[0] <= i - k:
9	dq.popleft()
10	while dq and nums[dq[-1]] <= nums[i]:
11	dq.pop()
12	dq.append(i)
13	if i >= k - 1:
14	res.append(nums[dq[0]])
15
16	return res

From the classic loop to our template

Old Way line	In our template	Why
if dq and dq[0] <= i - k: dq.popleft()	if right - left + 1 > k: left += 1 if dq and dq[0] < left: dq.popleft()	`i - k` is the window's left edge computed on the spot, true only because `k` never changes mid-run; storing that edge in `left` and testing `dq[0] < left` keeps working even when the edge can jump by more than one index in a single step, as the Dual Monotonic Deque's shrink loop needs.
while dq and nums[dq[-1]] <= nums[i]: dq.pop()	while dq and nums[dq[-1]] <= nums[right]: dq.pop()	The same rule, under the name this course gives the loop variable once a window has its own `left` and `right` edges.
if i >= k - 1: res.append(nums[dq[0]])	if right - left + 1 == k: res.append(nums[dq[0]])	`i >= k - 1` and `right - left + 1 == k` agree exactly while `left` stays `0` the whole run, which is always true here; the window-size form is the one that keeps working once `left` is free to move.

When the classic form is fine

Use dq[0] <= i - k when the window size k never changes and no related card in the same course needs an explicit left -- Sliding Window Maximum alone never needs one, and the index math is one line shorter. Keep an explicit left when the same deque shape is reused for a window whose edge can move by more than one step at a time, so every Monotonic Deque card in this course reads the same way.

Gotchas of the classic loop

Gotchas1 of 2

The trap
Gotcha 1: Writing the front cutoff as k - i instead of i - k
Mistake
```
if dq and dq[0] <= k - i:
```
Fix
```
if dq and dq[0] <= i - k:
```
What happens: The window at step i is nums[i - k + 1 .. i]. Its first index is i - k + 1, so every index at or below i - k is outside it. The cutoff i - k grows by 1 at each step, because the window moves right. At i = 0 the cutoff is -k, a negative number, so no index is at or below it and nothing leaves. The cutoff k - i does the opposite: it starts at k and gets smaller as i grows. With k = 3, at i = 2 the cutoff is 3 - 2 = 1, so index 1 (value 3) leaves, although the window nums[0 .. 2] still holds it.
Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Mistake: returns [-1, -1, 5, 5, 6, 7]Fix: returns [3, 3, 5, 5, 6, 7]
Gotcha 2: Popping the front on dq[0] < i - k
Mistake
```
if dq and dq[0] < i - k:
```
Fix
```
if dq and dq[0] <= i - k:
```
What happens: The window at step i is nums[i - k + 1 .. i]. So index i - k has just left the window. With <, index i - k stays at the front for one more step. Its value is then reported for a window that no longer holds it.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns [7, 7, 5]Fix: returns [7, 5, 5]

Theory Context•Two Pointers & Sliding Window

Builds on Fixed Window and Next Greater Element, which you haven’t finished yet.

P2HardBuilt on Fixed Window~4 min speedrun

Monotonic Deque (Sliding Window Maximum)

Built on

Fixed WindowThe window state is a deque of candidate indices whose values only decrease, so the window maximum is always at the front.

Grows into

Dual Monotonic Deque

The problem

Sliding Window Maximum (LC 239)(opens leetcode.com)

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.

Example 1

Input:nums = [1,3,-1,-3,5,3,6,7], k = 3

Output:[3,3,5,5,6,7]

The six windows and their maxima: [1,3,-1] -> 3, [3,-1,-3] -> 3, [-1,-3,5] -> 5, [-3,5,3] -> 5, [5,3,6] -> 6, [3,6,7] -> 7.

Monotonic Deque

sliding window ➔ deque of indices with decreasing values, an explicit left pointer ➔ front is the window maximum

Spot it when: Every position of a window that slides one step at a time needs the largest (or smallest) value inside it: the window's maximum, or the best of the last k entries of a DP table.

Monotonic Deque

Python

1	from collections import deque
2	from typing import List
3
4	def max_sliding_window(nums: List[int], k: int) -> List[int]:
5	"""Sliding Window Maximum: a deque of indices whose values only decrease; its front is the window's maximum.
6	Time: O(N) \| Space: O(K)
7	"""
8	# dq holds indices still inside the window, with their values strictly decreasing from front to back.
9	dq: deque[int] = deque()
10	res: List[int] = []
11	left = 0
12
13	for right in range(len(nums)):
14	# Phase 1: Push & Maintain Monotonicity:
15	# An older value no larger than nums[right] can never be the maximum again, so drop it from the back.
16	while dq and nums[dq[-1]] <= nums[right]:
17	dq.pop()
18	dq.append(right)
19
20	# Phase 2 & 3: Contract the Boundary, Then Evict the Stale Front:
21	# Exactly one index enters per step, so the window is oversized by at most one; left must move first,
22	# since the front is tested against the window's new edge, and left only grows by one at a time.
23	if right - left + 1 > k:
24	left += 1
25	if dq and dq[0] < left:
26	dq.popleft()
27
28	# Phase 4: Harvest the Answer:
29	# Once the window holds exactly k elements, the front of dq is its maximum.
30	if right - left + 1 == k:
31	res.append(nums[dq[0]])
32
33	return res

See it run

Sliding Window Maximum: max_sliding_window([7, 3, 5, 1, 2], 3)

left 0right -dq []res []

The top row is nums. The bottom row shows the values of the indices that dq holds, each under its own column, so they read from oldest to newest.

left the first index of the window
right the index that was just read
left, right left and right are at the same index
front dq[0], the index of the window maximum
in dq an index kept in dq behind the front

dq and res are empty, and left is 0. The loop reads one index right at a time.

nums

dq (values)

1 / 15

Gotchas1 of 5

The trap
Gotcha 1: Evicting the stale front before advancing left
Mistake
```
if dq and dq[0] < left:
    dq.popleft()
if right - left + 1 > k:
    left += 1
```
Fix
```
if right - left + 1 > k:
    left += 1
if dq and dq[0] < left:
    dq.popleft()
```
What happens: left must move before the front is tested, because the test is against the window's new edge. Swap the order, and the front is checked against left's stale, one-step-old value: an index that has just left the window still passes the check, stays at the front for one extra step, and reports a value that should already be gone. It is evicted the step after, but by then a stale maximum has already been recorded.
Example: nums = [9, 8, 7, 6, 5, 4], k = 2
Mistake: returns [9, 9, 8, 7, 6]Fix: returns [9, 8, 7, 6, 5]
Gotcha 2: Advancing left on right - left + 1 >= k instead of > k
Mistake
```
if right - left + 1 >= k:
    left += 1
```
Fix
```
if right - left + 1 > k:
    left += 1
```
What happens: >= shrinks the window as soon as it reaches size k, one step before it is allowed to. The window can then never hold k elements at the moment Phase 4 checks for it, so the harvest condition right - left + 1 == k never fires.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns []Fix: returns [7, 5, 5]
Gotcha 3: Evicting the front on dq[0] <= left instead of dq[0] < left
Mistake
```
if dq and dq[0] <= left:
    dq.popleft()
```
Fix
```
if dq and dq[0] < left:
    dq.popleft()
```
What happens: The window is nums[left..right], so index left itself is still inside it. With <=, a front sitting exactly at left is evicted anyway, even while it is still a valid candidate, which can throw away the true maximum before it is ever read.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns [5, 5, 2]Fix: returns [7, 5, 5]
Gotcha 4: Storing values in dq instead of indices
What happens: The front must leave dq when its index falls behind left. A stored value does not say where it came from. With repeated values, a value cannot say which copy left the window. An index answers both questions.
Gotcha 5: Keeping the <= pop test for a window minimum
Mistake
```
while dq and nums[dq[-1]] <= nums[right]:
```
Fix
```
while dq and nums[dq[-1]] >= nums[right]:
```
What happens: The <= test keeps the values in dq decreasing, so the front is the maximum. For a window minimum, keep the values increasing instead. Pop while nums[dq[-1]] >= nums[right]. A window whose validity depends on both the maximum and the minimum at once runs one deque of each kind side by side instead of picking just one -- see the Dual Monotonic Deque tool, built on this card.

Not this one if…

You need the k-th largest of everything seen so far and no value ever leaves, as in Kth Largest Element in a Stream (LC 703), not the largest value of a window that drops its oldest item at every step. See Top-K Heap
Each item needs the first larger value after it, as in Daily Temperatures (LC 739): the answer belongs to the item that is popped, and nothing leaves because it got too old. See Next Greater Element

Deep Dive

Why an older, smaller value can be thrown away

Tracing [7, 3, 5, 1, 2] with k = 3

At right = 0 and right = 1, nothing is popped. dq holds the indices [0, 1], with values 7 and 3. The window has fewer than 3 values, so res stays empty.

At right = 2, nums[2] = 5 is larger than 3, so index 1 is popped from the back. dq is [0, 2], with values 7 and 5. The window has 3 values, so res.append(nums[dq[0]]) adds 7.

Why the order of the two window lines matters

Store indices in dq, not values. A value cannot tell the code whether it came from a position before left, and it cannot tell two equal values apart.

The cost, and where the deque is used

60-Second Pitch

Common Questions

What is the time and space complexity?: The time is O(N). Each index is appended once and popped at most once, so the while loop in Phase 1 does O(N) pops in total. The space is O(K), because dq holds only indices inside the window. The result list is extra O(N - K + 1) space.
Why does the deque store indices and not values?: The front must leave when its index falls behind left. A value cannot say which position it came from. With repeated values, a value cannot say which copy left the window. An index answers both questions, and nums[index] gives the value.
Why pop on <= and not on <?: Both give the correct maxima. With <, an older equal value stays in dq. It is never needed, because the newer equal value stays in the window longer. For nums = [5, 5, 5, 5] and k = 3, < can hold 3 indices and <= holds 1. The card uses <= so the values strictly decrease, as the invariant says.
How would you do it with a heap, and why is the deque better?: Push (-nums[right], right) on a max-heap, and pop the top while its index is below left. Each push and pop costs O(log N), so the total is O(N log N). The heap also keeps expired entries inside it until they reach the top. The deque is O(N) and holds at most k entries.
How do you get the window minimum, or both together?: For the minimum, keep the values increasing: pop while nums[dq[-1]] >= nums[right]. For both, run max_dq and min_dq side by side and check each front for expiry. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LC 1438) is the standard problem for this.

SWE Reasoning

Spot it

Each position of a sliding window needs the maximum or the minimum of the values inside it.
The window slides by one step, so one value enters and one value leaves.
A heap works, but it needs lazy deletion of the values that left, which makes it O(N log N).
A DP value depends on the best of the last k earlier values (Jump Game VI (LC 1696)).

The invariant, step by step

dq is empty and left = 0. dq will hold indices inside nums[left..right], in increasing order.
At each right, while dq and nums[dq[-1]] <= nums[right] pops every older value that is not larger. Such a value can never be the maximum again.
dq.append(right) adds the new index. The values in dq strictly decrease from front to back.
If the window holds more than k values, left += 1 makes it hold k. This line runs first.
if dq and dq[0] < left removes the front when its index has left the window. At most one index can have left.
When the window holds exactly k values, nums[dq[0]] is the largest value in it, and res.append records it.

Traps

Testing the front before moving left. The front is compared with the old edge, so a value that has left the window stays for one more step and is recorded as a maximum.
Shrinking on right - left + 1 >= k. The window never holds k values when the harvest line runs, so res stays empty.
Evicting on dq[0] <= left. Index left is still inside the window, and its value may be the true maximum.
Storing values instead of indices. The code cannot tell when the front has left the window.
Using <= for a minimum. A window minimum needs >=, so the values in dq increase.

Practice

Canonical LeetCode:Sliding Window Maximum (LC 239)Shortest Subarray with Sum at Least K (LC 862)Jump Game VI (LC 1696)Constrained Subsequence Sum (LC 1425)

The classic loop

Old Way

Python

1	from collections import deque
2
3	def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
4	dq = deque()
5	res = []
6
7	for i in range(len(nums)):
8	if dq and dq[0] <= i - k:
9	dq.popleft()
10	while dq and nums[dq[-1]] <= nums[i]:
11	dq.pop()
12	dq.append(i)
13	if i >= k - 1:
14	res.append(nums[dq[0]])
15
16	return res

From the classic loop to our template

Old Way line	In our template	Why
if dq and dq[0] <= i - k: dq.popleft()	if right - left + 1 > k: left += 1 if dq and dq[0] < left: dq.popleft()	`i - k` is the window's left edge computed on the spot, true only because `k` never changes mid-run; storing that edge in `left` and testing `dq[0] < left` keeps working even when the edge can jump by more than one index in a single step, as the Dual Monotonic Deque's shrink loop needs.
while dq and nums[dq[-1]] <= nums[i]: dq.pop()	while dq and nums[dq[-1]] <= nums[right]: dq.pop()	The same rule, under the name this course gives the loop variable once a window has its own `left` and `right` edges.
if i >= k - 1: res.append(nums[dq[0]])	if right - left + 1 == k: res.append(nums[dq[0]])	`i >= k - 1` and `right - left + 1 == k` agree exactly while `left` stays `0` the whole run, which is always true here; the window-size form is the one that keeps working once `left` is free to move.

When the classic form is fine

Gotchas of the classic loop

Gotchas1 of 2

The trap
Gotcha 1: Writing the front cutoff as k - i instead of i - k
Mistake
```
if dq and dq[0] <= k - i:
```
Fix
```
if dq and dq[0] <= i - k:
```
What happens: The window at step i is nums[i - k + 1 .. i]. Its first index is i - k + 1, so every index at or below i - k is outside it. The cutoff i - k grows by 1 at each step, because the window moves right. At i = 0 the cutoff is -k, a negative number, so no index is at or below it and nothing leaves. The cutoff k - i does the opposite: it starts at k and gets smaller as i grows. With k = 3, at i = 2 the cutoff is 3 - 2 = 1, so index 1 (value 3) leaves, although the window nums[0 .. 2] still holds it.
Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Mistake: returns [-1, -1, 5, 5, 6, 7]Fix: returns [3, 3, 5, 5, 6, 7]
Gotcha 2: Popping the front on dq[0] < i - k
Mistake
```
if dq and dq[0] < i - k:
```
Fix
```
if dq and dq[0] <= i - k:
```
What happens: The window at step i is nums[i - k + 1 .. i]. So index i - k has just left the window. With <, index i - k stays at the front for one more step. Its value is then reported for a window that no longer holds it.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns [7, 7, 5]Fix: returns [7, 5, 5]

Theory Context•Two Pointers & Sliding Window

Builds on Fixed Window and Next Greater Element, which you haven’t finished yet.

P2HardBuilt on Fixed Window~4 min speedrun

Monotonic Deque (Sliding Window Maximum)

Built on

Fixed WindowThe window state is a deque of candidate indices whose values only decrease, so the window maximum is always at the front.

Grows into

Dual Monotonic Deque

The problem

Sliding Window Maximum (LC 239)(opens leetcode.com)

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.

Example 1

Input:nums = [1,3,-1,-3,5,3,6,7], k = 3

Output:[3,3,5,5,6,7]

The six windows and their maxima: [1,3,-1] -> 3, [3,-1,-3] -> 3, [-1,-3,5] -> 5, [-3,5,3] -> 5, [5,3,6] -> 6, [3,6,7] -> 7.

Monotonic Deque

sliding window ➔ deque of indices with decreasing values, an explicit left pointer ➔ front is the window maximum

Spot it when: Every position of a window that slides one step at a time needs the largest (or smallest) value inside it: the window's maximum, or the best of the last k entries of a DP table.

Monotonic Deque

Python

1	from collections import deque
2	from typing import List
3
4	def max_sliding_window(nums: List[int], k: int) -> List[int]:
5	"""Sliding Window Maximum: a deque of indices whose values only decrease; its front is the window's maximum.
6	Time: O(N) \| Space: O(K)
7	"""
8	# dq holds indices still inside the window, with their values strictly decreasing from front to back.
9	dq: deque[int] = deque()
10	res: List[int] = []
11	left = 0
12
13	for right in range(len(nums)):
14	# Phase 1: Push & Maintain Monotonicity:
15	# An older value no larger than nums[right] can never be the maximum again, so drop it from the back.
16	while dq and nums[dq[-1]] <= nums[right]:
17	dq.pop()
18	dq.append(right)
19
20	# Phase 2 & 3: Contract the Boundary, Then Evict the Stale Front:
21	# Exactly one index enters per step, so the window is oversized by at most one; left must move first,
22	# since the front is tested against the window's new edge, and left only grows by one at a time.
23	if right - left + 1 > k:
24	left += 1
25	if dq and dq[0] < left:
26	dq.popleft()
27
28	# Phase 4: Harvest the Answer:
29	# Once the window holds exactly k elements, the front of dq is its maximum.
30	if right - left + 1 == k:
31	res.append(nums[dq[0]])
32
33	return res

See it run

Sliding Window Maximum: max_sliding_window([7, 3, 5, 1, 2], 3)

left 0right -dq []res []

The top row is nums. The bottom row shows the values of the indices that dq holds, each under its own column, so they read from oldest to newest.

left the first index of the window
right the index that was just read
left, right left and right are at the same index
front dq[0], the index of the window maximum
in dq an index kept in dq behind the front

dq and res are empty, and left is 0. The loop reads one index right at a time.

nums

dq (values)

1 / 15

Gotchas1 of 5

The trap
Gotcha 1: Evicting the stale front before advancing left
Mistake
```
if dq and dq[0] < left:
    dq.popleft()
if right - left + 1 > k:
    left += 1
```
Fix
```
if right - left + 1 > k:
    left += 1
if dq and dq[0] < left:
    dq.popleft()
```
What happens: left must move before the front is tested, because the test is against the window's new edge. Swap the order, and the front is checked against left's stale, one-step-old value: an index that has just left the window still passes the check, stays at the front for one extra step, and reports a value that should already be gone. It is evicted the step after, but by then a stale maximum has already been recorded.
Example: nums = [9, 8, 7, 6, 5, 4], k = 2
Mistake: returns [9, 9, 8, 7, 6]Fix: returns [9, 8, 7, 6, 5]
Gotcha 2: Advancing left on right - left + 1 >= k instead of > k
Mistake
```
if right - left + 1 >= k:
    left += 1
```
Fix
```
if right - left + 1 > k:
    left += 1
```
What happens: >= shrinks the window as soon as it reaches size k, one step before it is allowed to. The window can then never hold k elements at the moment Phase 4 checks for it, so the harvest condition right - left + 1 == k never fires.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns []Fix: returns [7, 5, 5]
Gotcha 3: Evicting the front on dq[0] <= left instead of dq[0] < left
Mistake
```
if dq and dq[0] <= left:
    dq.popleft()
```
Fix
```
if dq and dq[0] < left:
    dq.popleft()
```
What happens: The window is nums[left..right], so index left itself is still inside it. With <=, a front sitting exactly at left is evicted anyway, even while it is still a valid candidate, which can throw away the true maximum before it is ever read.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns [5, 5, 2]Fix: returns [7, 5, 5]
Gotcha 4: Storing values in dq instead of indices
What happens: The front must leave dq when its index falls behind left. A stored value does not say where it came from. With repeated values, a value cannot say which copy left the window. An index answers both questions.
Gotcha 5: Keeping the <= pop test for a window minimum
Mistake
```
while dq and nums[dq[-1]] <= nums[right]:
```
Fix
```
while dq and nums[dq[-1]] >= nums[right]:
```
What happens: The <= test keeps the values in dq decreasing, so the front is the maximum. For a window minimum, keep the values increasing instead. Pop while nums[dq[-1]] >= nums[right]. A window whose validity depends on both the maximum and the minimum at once runs one deque of each kind side by side instead of picking just one -- see the Dual Monotonic Deque tool, built on this card.

Not this one if…

You need the k-th largest of everything seen so far and no value ever leaves, as in Kth Largest Element in a Stream (LC 703), not the largest value of a window that drops its oldest item at every step. See Top-K Heap
Each item needs the first larger value after it, as in Daily Temperatures (LC 739): the answer belongs to the item that is popped, and nothing leaves because it got too old. See Next Greater Element

Deep Dive

Why an older, smaller value can be thrown away

Tracing [7, 3, 5, 1, 2] with k = 3

At right = 0 and right = 1, nothing is popped. dq holds the indices [0, 1], with values 7 and 3. The window has fewer than 3 values, so res stays empty.

At right = 2, nums[2] = 5 is larger than 3, so index 1 is popped from the back. dq is [0, 2], with values 7 and 5. The window has 3 values, so res.append(nums[dq[0]]) adds 7.

Why the order of the two window lines matters

Store indices in dq, not values. A value cannot tell the code whether it came from a position before left, and it cannot tell two equal values apart.

The cost, and where the deque is used

60-Second Pitch

Common Questions

What is the time and space complexity?: The time is O(N). Each index is appended once and popped at most once, so the while loop in Phase 1 does O(N) pops in total. The space is O(K), because dq holds only indices inside the window. The result list is extra O(N - K + 1) space.
Why does the deque store indices and not values?: The front must leave when its index falls behind left. A value cannot say which position it came from. With repeated values, a value cannot say which copy left the window. An index answers both questions, and nums[index] gives the value.
Why pop on <= and not on <?: Both give the correct maxima. With <, an older equal value stays in dq. It is never needed, because the newer equal value stays in the window longer. For nums = [5, 5, 5, 5] and k = 3, < can hold 3 indices and <= holds 1. The card uses <= so the values strictly decrease, as the invariant says.
How would you do it with a heap, and why is the deque better?: Push (-nums[right], right) on a max-heap, and pop the top while its index is below left. Each push and pop costs O(log N), so the total is O(N log N). The heap also keeps expired entries inside it until they reach the top. The deque is O(N) and holds at most k entries.
How do you get the window minimum, or both together?: For the minimum, keep the values increasing: pop while nums[dq[-1]] >= nums[right]. For both, run max_dq and min_dq side by side and check each front for expiry. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LC 1438) is the standard problem for this.

SWE Reasoning

Spot it

Each position of a sliding window needs the maximum or the minimum of the values inside it.
The window slides by one step, so one value enters and one value leaves.
A heap works, but it needs lazy deletion of the values that left, which makes it O(N log N).
A DP value depends on the best of the last k earlier values (Jump Game VI (LC 1696)).

The invariant, step by step

dq is empty and left = 0. dq will hold indices inside nums[left..right], in increasing order.
At each right, while dq and nums[dq[-1]] <= nums[right] pops every older value that is not larger. Such a value can never be the maximum again.
dq.append(right) adds the new index. The values in dq strictly decrease from front to back.
If the window holds more than k values, left += 1 makes it hold k. This line runs first.
if dq and dq[0] < left removes the front when its index has left the window. At most one index can have left.
When the window holds exactly k values, nums[dq[0]] is the largest value in it, and res.append records it.

Traps

Testing the front before moving left. The front is compared with the old edge, so a value that has left the window stays for one more step and is recorded as a maximum.
Shrinking on right - left + 1 >= k. The window never holds k values when the harvest line runs, so res stays empty.
Evicting on dq[0] <= left. Index left is still inside the window, and its value may be the true maximum.
Storing values instead of indices. The code cannot tell when the front has left the window.
Using <= for a minimum. A window minimum needs >=, so the values in dq increase.

Practice

Canonical LeetCode:Sliding Window Maximum (LC 239)Shortest Subarray with Sum at Least K (LC 862)Jump Game VI (LC 1696)Constrained Subsequence Sum (LC 1425)

The classic loop

Old Way

Python

1	from collections import deque
2
3	def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
4	dq = deque()
5	res = []
6
7	for i in range(len(nums)):
8	if dq and dq[0] <= i - k:
9	dq.popleft()
10	while dq and nums[dq[-1]] <= nums[i]:
11	dq.pop()
12	dq.append(i)
13	if i >= k - 1:
14	res.append(nums[dq[0]])
15
16	return res

From the classic loop to our template

Old Way line	In our template	Why
if dq and dq[0] <= i - k: dq.popleft()	if right - left + 1 > k: left += 1 if dq and dq[0] < left: dq.popleft()	`i - k` is the window's left edge computed on the spot, true only because `k` never changes mid-run; storing that edge in `left` and testing `dq[0] < left` keeps working even when the edge can jump by more than one index in a single step, as the Dual Monotonic Deque's shrink loop needs.
while dq and nums[dq[-1]] <= nums[i]: dq.pop()	while dq and nums[dq[-1]] <= nums[right]: dq.pop()	The same rule, under the name this course gives the loop variable once a window has its own `left` and `right` edges.
if i >= k - 1: res.append(nums[dq[0]])	if right - left + 1 == k: res.append(nums[dq[0]])	`i >= k - 1` and `right - left + 1 == k` agree exactly while `left` stays `0` the whole run, which is always true here; the window-size form is the one that keeps working once `left` is free to move.

When the classic form is fine

Gotchas of the classic loop

Gotchas1 of 2

The trap
Gotcha 1: Writing the front cutoff as k - i instead of i - k
Mistake
```
if dq and dq[0] <= k - i:
```
Fix
```
if dq and dq[0] <= i - k:
```
What happens: The window at step i is nums[i - k + 1 .. i]. Its first index is i - k + 1, so every index at or below i - k is outside it. The cutoff i - k grows by 1 at each step, because the window moves right. At i = 0 the cutoff is -k, a negative number, so no index is at or below it and nothing leaves. The cutoff k - i does the opposite: it starts at k and gets smaller as i grows. With k = 3, at i = 2 the cutoff is 3 - 2 = 1, so index 1 (value 3) leaves, although the window nums[0 .. 2] still holds it.
Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Mistake: returns [-1, -1, 5, 5, 6, 7]Fix: returns [3, 3, 5, 5, 6, 7]
Gotcha 2: Popping the front on dq[0] < i - k
Mistake
```
if dq and dq[0] < i - k:
```
Fix
```
if dq and dq[0] <= i - k:
```
What happens: The window at step i is nums[i - k + 1 .. i]. So index i - k has just left the window. With <, index i - k stays at the front for one more step. Its value is then reported for a window that no longer holds it.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns [7, 7, 5]Fix: returns [7, 5, 5]

Theory Context•Two Pointers & Sliding Window

Builds on Fixed Window and Next Greater Element, which you haven’t finished yet.

P2HardBuilt on Fixed Window~4 min speedrun

Monotonic Deque (Sliding Window Maximum)

Built on

Fixed WindowThe window state is a deque of candidate indices whose values only decrease, so the window maximum is always at the front.

Grows into

Dual Monotonic Deque

The problem

Sliding Window Maximum (LC 239)(opens leetcode.com)

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.

Example 1

Input:nums = [1,3,-1,-3,5,3,6,7], k = 3

Output:[3,3,5,5,6,7]

The six windows and their maxima: [1,3,-1] -> 3, [3,-1,-3] -> 3, [-1,-3,5] -> 5, [-3,5,3] -> 5, [5,3,6] -> 6, [3,6,7] -> 7.

Monotonic Deque

sliding window ➔ deque of indices with decreasing values, an explicit left pointer ➔ front is the window maximum

Spot it when: Every position of a window that slides one step at a time needs the largest (or smallest) value inside it: the window's maximum, or the best of the last k entries of a DP table.

Monotonic Deque

Python

1	from collections import deque
2	from typing import List
3
4	def max_sliding_window(nums: List[int], k: int) -> List[int]:
5	"""Sliding Window Maximum: a deque of indices whose values only decrease; its front is the window's maximum.
6	Time: O(N) \| Space: O(K)
7	"""
8	# dq holds indices still inside the window, with their values strictly decreasing from front to back.
9	dq: deque[int] = deque()
10	res: List[int] = []
11	left = 0
12
13	for right in range(len(nums)):
14	# Phase 1: Push & Maintain Monotonicity:
15	# An older value no larger than nums[right] can never be the maximum again, so drop it from the back.
16	while dq and nums[dq[-1]] <= nums[right]:
17	dq.pop()
18	dq.append(right)
19
20	# Phase 2 & 3: Contract the Boundary, Then Evict the Stale Front:
21	# Exactly one index enters per step, so the window is oversized by at most one; left must move first,
22	# since the front is tested against the window's new edge, and left only grows by one at a time.
23	if right - left + 1 > k:
24	left += 1
25	if dq and dq[0] < left:
26	dq.popleft()
27
28	# Phase 4: Harvest the Answer:
29	# Once the window holds exactly k elements, the front of dq is its maximum.
30	if right - left + 1 == k:
31	res.append(nums[dq[0]])
32
33	return res

See it run

Sliding Window Maximum: max_sliding_window([7, 3, 5, 1, 2], 3)

left 0right -dq []res []

The top row is nums. The bottom row shows the values of the indices that dq holds, each under its own column, so they read from oldest to newest.

left the first index of the window
right the index that was just read
left, right left and right are at the same index
front dq[0], the index of the window maximum
in dq an index kept in dq behind the front

dq and res are empty, and left is 0. The loop reads one index right at a time.

nums

dq (values)

1 / 15

Gotchas1 of 5

The trap
Gotcha 1: Evicting the stale front before advancing left
Mistake
```
if dq and dq[0] < left:
    dq.popleft()
if right - left + 1 > k:
    left += 1
```
Fix
```
if right - left + 1 > k:
    left += 1
if dq and dq[0] < left:
    dq.popleft()
```
What happens: left must move before the front is tested, because the test is against the window's new edge. Swap the order, and the front is checked against left's stale, one-step-old value: an index that has just left the window still passes the check, stays at the front for one extra step, and reports a value that should already be gone. It is evicted the step after, but by then a stale maximum has already been recorded.
Example: nums = [9, 8, 7, 6, 5, 4], k = 2
Mistake: returns [9, 9, 8, 7, 6]Fix: returns [9, 8, 7, 6, 5]
Gotcha 2: Advancing left on right - left + 1 >= k instead of > k
Mistake
```
if right - left + 1 >= k:
    left += 1
```
Fix
```
if right - left + 1 > k:
    left += 1
```
What happens: >= shrinks the window as soon as it reaches size k, one step before it is allowed to. The window can then never hold k elements at the moment Phase 4 checks for it, so the harvest condition right - left + 1 == k never fires.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns []Fix: returns [7, 5, 5]
Gotcha 3: Evicting the front on dq[0] <= left instead of dq[0] < left
Mistake
```
if dq and dq[0] <= left:
    dq.popleft()
```
Fix
```
if dq and dq[0] < left:
    dq.popleft()
```
What happens: The window is nums[left..right], so index left itself is still inside it. With <=, a front sitting exactly at left is evicted anyway, even while it is still a valid candidate, which can throw away the true maximum before it is ever read.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns [5, 5, 2]Fix: returns [7, 5, 5]
Gotcha 4: Storing values in dq instead of indices
What happens: The front must leave dq when its index falls behind left. A stored value does not say where it came from. With repeated values, a value cannot say which copy left the window. An index answers both questions.
Gotcha 5: Keeping the <= pop test for a window minimum
Mistake
```
while dq and nums[dq[-1]] <= nums[right]:
```
Fix
```
while dq and nums[dq[-1]] >= nums[right]:
```
What happens: The <= test keeps the values in dq decreasing, so the front is the maximum. For a window minimum, keep the values increasing instead. Pop while nums[dq[-1]] >= nums[right]. A window whose validity depends on both the maximum and the minimum at once runs one deque of each kind side by side instead of picking just one -- see the Dual Monotonic Deque tool, built on this card.

Not this one if…

You need the k-th largest of everything seen so far and no value ever leaves, as in Kth Largest Element in a Stream (LC 703), not the largest value of a window that drops its oldest item at every step. See Top-K Heap
Each item needs the first larger value after it, as in Daily Temperatures (LC 739): the answer belongs to the item that is popped, and nothing leaves because it got too old. See Next Greater Element

Deep Dive

Why an older, smaller value can be thrown away

Tracing [7, 3, 5, 1, 2] with k = 3

At right = 0 and right = 1, nothing is popped. dq holds the indices [0, 1], with values 7 and 3. The window has fewer than 3 values, so res stays empty.

At right = 2, nums[2] = 5 is larger than 3, so index 1 is popped from the back. dq is [0, 2], with values 7 and 5. The window has 3 values, so res.append(nums[dq[0]]) adds 7.

Why the order of the two window lines matters

Store indices in dq, not values. A value cannot tell the code whether it came from a position before left, and it cannot tell two equal values apart.

The cost, and where the deque is used

60-Second Pitch

Common Questions

What is the time and space complexity?: The time is O(N). Each index is appended once and popped at most once, so the while loop in Phase 1 does O(N) pops in total. The space is O(K), because dq holds only indices inside the window. The result list is extra O(N - K + 1) space.
Why does the deque store indices and not values?: The front must leave when its index falls behind left. A value cannot say which position it came from. With repeated values, a value cannot say which copy left the window. An index answers both questions, and nums[index] gives the value.
Why pop on <= and not on <?: Both give the correct maxima. With <, an older equal value stays in dq. It is never needed, because the newer equal value stays in the window longer. For nums = [5, 5, 5, 5] and k = 3, < can hold 3 indices and <= holds 1. The card uses <= so the values strictly decrease, as the invariant says.
How would you do it with a heap, and why is the deque better?: Push (-nums[right], right) on a max-heap, and pop the top while its index is below left. Each push and pop costs O(log N), so the total is O(N log N). The heap also keeps expired entries inside it until they reach the top. The deque is O(N) and holds at most k entries.
How do you get the window minimum, or both together?: For the minimum, keep the values increasing: pop while nums[dq[-1]] >= nums[right]. For both, run max_dq and min_dq side by side and check each front for expiry. Longest Continuous Subarray With Absolute Diff Less Than or Equal to Limit (LC 1438) is the standard problem for this.

SWE Reasoning

Spot it

Each position of a sliding window needs the maximum or the minimum of the values inside it.
The window slides by one step, so one value enters and one value leaves.
A heap works, but it needs lazy deletion of the values that left, which makes it O(N log N).
A DP value depends on the best of the last k earlier values (Jump Game VI (LC 1696)).

The invariant, step by step

dq is empty and left = 0. dq will hold indices inside nums[left..right], in increasing order.
At each right, while dq and nums[dq[-1]] <= nums[right] pops every older value that is not larger. Such a value can never be the maximum again.
dq.append(right) adds the new index. The values in dq strictly decrease from front to back.
If the window holds more than k values, left += 1 makes it hold k. This line runs first.
if dq and dq[0] < left removes the front when its index has left the window. At most one index can have left.
When the window holds exactly k values, nums[dq[0]] is the largest value in it, and res.append records it.

Traps

Testing the front before moving left. The front is compared with the old edge, so a value that has left the window stays for one more step and is recorded as a maximum.
Shrinking on right - left + 1 >= k. The window never holds k values when the harvest line runs, so res stays empty.
Evicting on dq[0] <= left. Index left is still inside the window, and its value may be the true maximum.
Storing values instead of indices. The code cannot tell when the front has left the window.
Using <= for a minimum. A window minimum needs >=, so the values in dq increase.

Practice

Canonical LeetCode:Sliding Window Maximum (LC 239)Shortest Subarray with Sum at Least K (LC 862)Jump Game VI (LC 1696)Constrained Subsequence Sum (LC 1425)

The classic loop

Old Way

Python

1	from collections import deque
2
3	def maxSlidingWindow(nums: list[int], k: int) -> list[int]:
4	dq = deque()
5	res = []
6
7	for i in range(len(nums)):
8	if dq and dq[0] <= i - k:
9	dq.popleft()
10	while dq and nums[dq[-1]] <= nums[i]:
11	dq.pop()
12	dq.append(i)
13	if i >= k - 1:
14	res.append(nums[dq[0]])
15
16	return res

From the classic loop to our template

Old Way line	In our template	Why
if dq and dq[0] <= i - k: dq.popleft()	if right - left + 1 > k: left += 1 if dq and dq[0] < left: dq.popleft()	`i - k` is the window's left edge computed on the spot, true only because `k` never changes mid-run; storing that edge in `left` and testing `dq[0] < left` keeps working even when the edge can jump by more than one index in a single step, as the Dual Monotonic Deque's shrink loop needs.
while dq and nums[dq[-1]] <= nums[i]: dq.pop()	while dq and nums[dq[-1]] <= nums[right]: dq.pop()	The same rule, under the name this course gives the loop variable once a window has its own `left` and `right` edges.
if i >= k - 1: res.append(nums[dq[0]])	if right - left + 1 == k: res.append(nums[dq[0]])	`i >= k - 1` and `right - left + 1 == k` agree exactly while `left` stays `0` the whole run, which is always true here; the window-size form is the one that keeps working once `left` is free to move.

When the classic form is fine

Gotchas of the classic loop

Gotchas1 of 2

The trap
Gotcha 1: Writing the front cutoff as k - i instead of i - k
Mistake
```
if dq and dq[0] <= k - i:
```
Fix
```
if dq and dq[0] <= i - k:
```
What happens: The window at step i is nums[i - k + 1 .. i]. Its first index is i - k + 1, so every index at or below i - k is outside it. The cutoff i - k grows by 1 at each step, because the window moves right. At i = 0 the cutoff is -k, a negative number, so no index is at or below it and nothing leaves. The cutoff k - i does the opposite: it starts at k and gets smaller as i grows. With k = 3, at i = 2 the cutoff is 3 - 2 = 1, so index 1 (value 3) leaves, although the window nums[0 .. 2] still holds it.
Example: nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3
Mistake: returns [-1, -1, 5, 5, 6, 7]Fix: returns [3, 3, 5, 5, 6, 7]
Gotcha 2: Popping the front on dq[0] < i - k
Mistake
```
if dq and dq[0] < i - k:
```
Fix
```
if dq and dq[0] <= i - k:
```
What happens: The window at step i is nums[i - k + 1 .. i]. So index i - k has just left the window. With <, index i - k stays at the front for one more step. Its value is then reported for a window that no longer holds it.
Example: nums = [7, 3, 5, 1, 2], k = 3
Mistake: returns [7, 7, 5]Fix: returns [7, 5, 5]