A monotonic stack that can also forget. Pop dominated candidates from the back, pop expired ones from the front, and the best candidate in the window is always at the front.
Two earlier patterns meet here. The sliding window moves a range across an array, but it cannot tell you the window’s maximum without rescanning. The monotonic stack throws away values that can never matter again, but it only ever grows from one end. Put the stack in a deque and you can also drop indices that slide out of the window. Every index enters once and leaves once, so the whole pass is O(n).
best[i] = value + max(best[i-k..i-1]). Template B.n up to 105 with a window of size k. O(n × k) is too slow. O(n) is the target.Reading the figure. Cell colors match the fate of each index. Violet means stale: the index slid out of the window. Red means dominated: a newer, larger value arrived, so it can never be the max. Amber is the new value and green is the answer. Notice that the dominated values leave from the back, newest first.
Why indices, not values. The front check is “has this left the window?”, and only an index can answer that. Same rule as on the monotonic stack page.
Why O(n). Each index is appended once. It can be popped at most once, from one end or the other. So the total work across all the inner while loops is at most n pops, even though one step may pop many.
<= the new value.>= the new value.from collections import deque
def sliding_window_min(nums: list[int], k: int) -> list[int]:
"""Minimum of every window of size k, left to right.
Args:
nums: The values.
k: Window size, 1 <= k <= len(nums).
Returns:
One minimum per window, len(nums) - k + 1 values.
Example:
>>> sliding_window_min([4, 2, 12, 3, 8, 1], 3)
[2, 2, 3, 1]
"""
window: deque[int] = deque() # indices. nums[...] increases front to back.
out: list[int] = []
# index is the right edge of the window. The window is index - k + 1 .. index.
# Invariant at the top of each pass: window holds in-range, undominated indices.
for index, value in enumerate(nums):
# Stale: index - k is the first position left of the window. Drop it.
while window and window[0] <= index - k:
window.popleft()
# Dominated: an older value >= the new one can never be the minimum again.
while window and nums[window[-1]] >= value: # [-1]: the back of the deque
window.pop()
window.append(index)
# k - 1: the first index where a full window of k values exists.
if index >= k - 1:
out.append(nums[window[0]]) # [0]: the front holds the window minimum
return out
Flip both comparisons for the maximum: pop the back while nums[window[-1]] <= value. Everything else stays the same. Problem 1 is that flip.
Reading the figure. Each row is one pass of the loop. In the array, amber is the new value and blue is the rest of the window. Red text names values popped from the back as dominated. Violet text names a value dropped from the front as stale. The green deque cell is the front, which is the minimum written to out.
from collections import deque
def min_cost_jumps(costs: list[int], k: int) -> int:
"""Cheapest walk from the first stone to the last, jumping 1 to k stones.
You pay costs[i] for every stone you land on, including the first.
Args:
costs: Cost of each stone, at least one stone.
k: Longest jump allowed, k >= 1.
Returns:
The minimum total cost to stand on the last stone.
Example:
>>> min_cost_jumps([1, 100, 1, 1, 100, 1], 2)
4
"""
# best[i]: cheapest total to stand on stone i. 0 is a placeholder until filled.
best = [0] * len(costs)
window: deque[int] = deque() # indices. best[...] increases front to back.
# Invariant at the top of pass i: window holds indices i - k .. i - 1 that
# are not dominated, so best[window[0]] is the cheapest stone that can reach i.
for i, cost in enumerate(costs):
# Stale: a stone before i - k is more than k stones back.
while window and window[0] < i - k:
window.popleft()
# Recurrence: land on i from the cheapest reachable stone.
# Stone 0 has nothing before it, so it adds 0.
best[i] = cost + (best[window[0]] if window else 0) # [0]: the front
# Dominated: an older stone that costs at least as much is never better.
while window and best[window[-1]] >= best[i]: # [-1]: the back
window.pop()
window.append(i)
return best[-1] # [-1]: the last stone
The recurrence best[i] = cost[i] + min(best[i-k..i-1]) is O(n × k) if you scan. The deque turns the scan into reading window[0]. Any DP whose transition is “best of the last k states” gets this speed-up. Jump Game VI is this template with max in place of min.
Reading the figure. Each column is one stone. The front row is window[0], the cheapest stone in reach. Violet notes show a stone dropped from the front for being more than k back. Green stones form the cheapest walk, and the green cell is the answer, best[-1] = 4.
k ending at i, the first index is i - k + 1. So drop the front while it is <= i - k, or equally < i - k + 1.i >= k - 1.< where <= is safe. Both give right answers for max and min. Popping on ties keeps the deque shorter. In Problem 4 with values stored instead of indices, ties must be kept. Indices avoid the question.Given an array nums and a window size k, return the maximum of each window of k consecutive values as the window slides from left to right.
from collections import deque
def max_sliding_window(nums: list[int], k: int) -> list[int]:
"""Maximum of every window of size k, left to right.
Args:
nums: The values.
k: Window size, 1 <= k <= len(nums).
Returns:
One maximum per window, len(nums) - k + 1 values.
Example:
>>> max_sliding_window([1, 3, -1, -3, 5, 3, 6, 7], 3)
[3, 3, 5, 5, 6, 7]
>>> max_sliding_window([9], 1)
[9]
"""
window: deque[int] = deque() # indices. nums[...] decreases front to back.
result: list[int] = []
# right is the right edge. The window covers right - k + 1 .. right.
# Invariant at the top of each pass: window holds in-range, undominated indices.
for right, value in enumerate(nums):
# Stale: right - k is one left of the window, so drop it and anything older.
while window and window[0] <= right - k:
window.popleft()
# Dominated: an older value <= the new one can never be the max again.
while window and nums[window[-1]] <= value: # [-1]: the back
window.pop()
window.append(right)
# k - 1: the first right edge with a full window of k values.
if right >= k - 1:
result.append(nums[window[0]]) # [0]: the front is the window max
return result
nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3. The deque is shown as values.
1: deque [1]. Window not full.3: pops 1. Deque [3]. Not full.-1: deque [3, -1]. Emit 3.-3: deque [3, -1, -3]. Emit 3.5: 3 is stale, then 5 pops -3 and -1. Deque [5]. Emit 5.3: deque [5, 3]. Emit 5. Then 6 pops both, emit 6. Then 7 pops 6, emit 7.Reading the figure. Each row adds one value. Amber marks it in the array, blue marks the rest of its window. Red text lists values popped from the back because the new value is at least as big. At i=4 the 3 is popped from the front in violet, because index 1 left the window. The green cell is the front, the max of that window.
k = 1: every value is its own window, the output equals the input.k == len(nums): one window, the output is [max(nums)].k and the front check does all the work.<= keeps only the newest copy, which lives longest. Correct and shorter.Given an integer array nums, which may contain negatives, and an integer k, return the length of the shortest non-empty contiguous subarray whose sum is at least k. Return -1 if none exists.
nums[i:j] is prefix[j] - prefix[i]. For each j we want the largest i with prefix[i] <= prefix[j] - k.prefix[j] - prefix[front] >= k, record the length and drop the front. A later j would only give a longer subarray from that start.prefix[back] >= prefix[j], drop the back. Index j is later and no larger, so it beats back as a start for every future end.from collections import deque
def shortest_subarray(nums: list[int], k: int) -> int:
"""Length of the shortest subarray with sum >= k, or -1.
Args:
nums: Integers, may be negative.
k: The target, k >= 1.
Returns:
The shortest qualifying length, or -1 if none exists.
Example:
>>> shortest_subarray([2, -1, 2], 3)
3
>>> shortest_subarray([1, 2], 4)
-1
>>> shortest_subarray([84, -37, 32, 40, 95], 167)
3
"""
# prefix[j] is the sum of nums[0:j]. prefix[0] = 0 is the empty prefix.
prefix = [0]
for value in nums:
prefix.append(prefix[-1] + value) # [-1]: the running total so far
# len(nums) + 1 is longer than any real subarray, so it marks "none yet".
best = len(nums) + 1
starts: deque[int] = deque() # indices into prefix, prefix[...] increasing
# end is a prefix index. nums[start:end] sums to prefix[end] - prefix[start].
# Invariant at the top of each pass: starts holds useful start indices < end.
for end, total in enumerate(prefix):
# Front: the oldest start works. No later end can give it a shorter answer.
while starts and total - prefix[starts[0]] >= k: # [0]: the front
best = min(best, end - starts.popleft())
# Back: end is later and no larger, so it is a better start from now on.
while starts and prefix[starts[-1]] >= total: # [-1]: the back
starts.pop()
starts.append(end)
# Still the sentinel len(nums) + 1 means nothing qualified, so -1.
return best if best <= len(nums) else -1
nums = [2, -1, 2], k = 3, so prefix = [0, 2, 1, 3]:
end = 0, total 0: deque [0].end = 1, total 2: 2 - 0 < 3. Deque [0, 1].end = 2, total 1: 1 - 0 < 3. Back prefix 2 ≥ 1, pop index 1. Deque [0, 2].end = 3, total 3: 3 - 0 >= 3, length 3 - 0 = 3, pop index 0. 3 - 1 < 3, stop. Deque [2, 3].Reading the figure. On the left, each circle is prefix[index], plotted by height. The red circle is index 1. Index 2 comes later with a smaller prefix, so index 1 can never be the better start. The green dashed line joins the start and end of the answer. On the right, the deque holds start indices, front on the left.
>= k: length 1.-1.Given an integer array nums and an integer k, return the maximum sum of a non-empty subsequence such that any two consecutive chosen elements are at most k positions apart.
best[i] is the largest sum of a valid subsequence that ends at i.best[i] = nums[i] + max(0, best[j]) over i - k <= j < i. The 0 means “start fresh at i” when every earlier option is negative.k DP values, so Template B with max makes it O(1).max(best), since the best subsequence can end anywhere.from collections import deque
def constrained_subset_sum(nums: list[int], k: int) -> int:
"""Max sum of a non-empty subsequence with chosen indices at most k apart.
Args:
nums: Integers, at least one, may be negative.
k: Largest allowed gap between consecutive chosen indices, k >= 1.
Returns:
The maximum achievable sum.
Example:
>>> constrained_subset_sum([10, 2, -10, 5, 20], 2)
37
>>> constrained_subset_sum([-1, -2, -3], 1)
-1
>>> constrained_subset_sum([10, -2, -10, -5, 20], 2)
23
"""
# best[i]: largest sum of a valid subsequence ending at i. [:]: a copy,
# so each slot starts as "take nums[i] alone".
best = nums[:]
window: deque[int] = deque() # indices. best[...] decreases front to back.
# Invariant at the top of pass i: window holds undominated indices in
# i - k .. i - 1, so best[window[0]] is the best predecessor for i.
for i, value in enumerate(nums):
# Stale: an index before i - k is too far back to precede i.
while window and window[0] < i - k:
window.popleft()
if window:
# max(0, ...): a negative predecessor only hurts, so start fresh.
best[i] = value + max(0, best[window[0]]) # [0]: the front is the max
# Dominated: an older index with a sum no larger is never the better pick.
while window and best[window[-1]] <= best[i]: # [-1]: the back
window.pop()
window.append(i)
return max(best) # the best subsequence may end anywhere
nums = [10, 2, -10, 5, 20], k = 2:
i = 0: best[0] = 10. Deque [0].i = 1: front 10, best[1] = 2 + 10 = 12. 12 pops index 0. Deque [1].i = 2: front 12, best[2] = -10 + 12 = 2. Deque [1, 2].i = 3: index 1 is still in range. best[3] = 5 + 12 = 17. Pops 2 and 1. Deque [3].i = 4: best[4] = 20 + 17 = 37. max(best) is 37, from 10, 2, 5, 20.Reading the figure. Each column is one index. The front row shows which earlier state best[i] builds on. Green cells in the top row are the chosen subsequence. The grey -10 is skipped. Notice that i3 reads i1, two steps back, which is still inside k = 2.
max(0, ...) handles it.k >= len(nums): any subsequence is allowed, so the answer is the sum of the positives, or the largest value if none are positive.best[-1] and there is no max(0, ...). Same deque.Given an integer array nums and an integer limit, return the length of the longest contiguous subarray in which the absolute difference between any two elements is at most limit.
max - min <= limit. So we need the window’s max and min at all times.highs has decreasing values, so its front is the max. lows has increasing values, so its front is the min.left moves past a front index, that front is stale and goes.from collections import deque
def longest_subarray(nums: list[int], limit: int) -> int:
"""Longest subarray whose max minus min is at most limit.
Args:
nums: Integers, at least one.
limit: Largest allowed difference, limit >= 0.
Returns:
The length of the longest qualifying subarray.
Example:
>>> longest_subarray([8, 2, 4, 7], 4)
2
>>> longest_subarray([10, 1, 2, 4, 7, 2], 5)
4
>>> longest_subarray([4, 2, 2, 2, 4, 4, 2, 2], 0)
3
"""
highs: deque[int] = deque() # indices. Values decrease, front is the max.
lows: deque[int] = deque() # indices. Values increase, front is the min.
left = 0 # 0: the window starts at the first index
best = 0 # 0: no window seen yet
# right is the new right edge. Invariant at the end of each pass: the window
# left .. right is valid, and both deques hold only indices in it.
for right, value in enumerate(nums):
# Dominated in highs: older and no bigger, never the max again.
while highs and nums[highs[-1]] <= value: # [-1]: the back
highs.pop()
highs.append(right)
# Dominated in lows: older and no smaller, never the min again.
while lows and nums[lows[-1]] >= value: # [-1]: the back
lows.pop()
lows.append(right)
# Shrink while invalid. [0] is each front: the window max and min.
while nums[highs[0]] - nums[lows[0]] > limit:
left += 1 # + 1: drop one index from the left edge
if highs[0] < left: # [0]: the max fell out of the window
highs.popleft()
if lows[0] < left: # [0]: the min fell out of the window
lows.popleft()
# + 1: right - left counts gaps. Add one to count the elements.
best = max(best, right - left + 1)
return best
nums = [8, 2, 4, 7], limit = 4. Deques shown as values.
right = 0 (8): highs [8], lows [8]. Length 1.right = 1 (2): highs [8, 2], lows [2]. 8 - 2 > 4, so left = 1 and 8 leaves highs. Length 1.right = 2 (4): highs [4], lows [2, 4]. 4 - 2 <= 4. Length 2.right = 3 (7): highs [7], lows [2, 4, 7]. 7 - 2 > 4, so left = 2 and 2 leaves lows. 7 - 4 <= 4. Length 2.Reading the figure. Each row adds nums[right], shown in amber, and the blue cells are the rest of the window after any shrink. Deques read front to back, left to right. A violet cell is a front that went stale when left moved past it. Values popped from the back as dominated are not drawn. The green length is the best seen.
1. The deques are never empty inside the shrink loop, because right is in both and a single element always satisfies the limit.limit = 0: the longest run of equal values.SortedList or two heaps also work at O(n log n). Name them, then explain why the deques are linear.The deque here is a tool inside an algorithm. Pattern 23, Design: Hash Map plus Linked List, turns the same “cheap at both ends” idea into a data structure you build yourself, the shape behind the LRU cache.