Sliding Window Maximum with a Deque
22 min · Intermediate
Need help? Ask a tutor on WhatsApp (opens in a new tab)A sum is easy to slide, but a maximum is not: when the biggest item leaves, you need the next one. A deque of candidates solves it in one pass.
A queue you can use at both ends
Deque (say "deck") is a double-ended queue from the collections module. You can append and pop at both ends in O(1) time. With maxlen set, it keeps only the newest items.
The largest item of every window is hard to slide: when the maximum leaves, you need the next one. A deque lets you add and remove at both ends quickly.
from collections import deque
line = deque([1, 2, 3])line.append(4)line.appendleft(0)print(line.pop(), line.popleft(), list(line))Example 1 · Brute force: max of each slice
nums = [1, 3, -1, -3, 5, 3, 6, 7]k = 3print([max(nums[i:i + k]) for i in range(len(nums) - k + 1)])[3, 3, 5, 5, 6, 7]
What this code does
- Each window is sliced and scanned for its maximum.
- The cost is O(n * k). It is the right first answer to say in an interview.
Example 2 · A deque with maxlen is a ready-made window
from collections import deque
recent = deque(maxlen=3)for sale in [4, 2, 7, 1, 3]: recent.append(sale) print(list(recent), sum(recent))[4] 4 [4, 2] 6 [4, 2, 7] 13 [2, 7, 1] 10 [7, 1, 3] 11
What this code does
- When a fourth item is appended, the oldest one drops out by itself.
- Summing the deque costs O(k) each time, so use the running-total method for big windows.
Each of these four operations takes O(1) time. A list is slow at the front: list.pop(0) shifts every other item, which is O(n).
Keep only the candidates for the maximum
Monotonic deque is a deque whose items always go in one order, here from largest to smallest. Before each new item is added, the weaker items at the back are removed.
When a bigger item arrives, every smaller item before it can never be the maximum again, because the bigger one stays in the window longer. Remove them from the back.
from collections import deque
cands = deque()for value in [1, 3, 2, 5]: while cands and cands[-1] <= value: cands.pop() cands.append(value) print(value, list(cands))Example 3 · Watch the candidates (indexes) change
from collections import deque
nums = [4, 2, 1, 3, 0]k = 3dq = deque()for i, value in enumerate(nums): while dq and nums[dq[-1]] <= value: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() print(i, [nums[j] for j in dq])0 [4] 1 [4, 2] 2 [4, 2, 1] 3 [3] 4 [3, 0]
What this code does
- The printed values always go from large to small.
- At index 3 the value 3 removes the smaller candidates 1 and 2 from the back.
- The 4 at index 0 has left the window, so it is dropped from the front. Only 3 remains.
The deque always goes from big to small, so the front is the maximum.
Store indexes and drop expired ones
Store indexes, not values. An index tells you when an item has left the window: index i - k is just outside. Only the front can be that old, so check the front once per step.
from collections import deque
def window_max(nums, k): dq, out = deque(), [] for i, value in enumerate(nums): while dq and nums[dq[-1]] <= value: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: out.append(nums[dq[0]]) return outExample 4 · Optimal: sliding window maximum
from collections import deque
def window_max(nums, k): dq, out = deque(), [] for i, value in enumerate(nums): while dq and nums[dq[-1]] <= value: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: out.append(nums[dq[0]]) return out
print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))print(window_max([9], 1))print(window_max([4, 3, 2, 1], 2))print(window_max([1, 2, 3, 4], 4))[3, 3, 5, 5, 6, 7] [9] [4, 3, 2] [4]
What this code does
- The result has n - k + 1 values, one for each full window.
- With k = 1 every item is its own maximum.
- With k equal to the length there is just one window.
The answer for a full window is nums[dq[0]], the item at the front. Windows start to be full when i >= k - 1.
Cost, and the minimum
Each index is added once and removed at most once, so the loop does O(n) work. The deque never holds more than k indexes, so the extra space is O(k). For a minimum, flip the comparison.
from collections import deque
def window_min(nums, k): dq, out = deque(), [] for i, value in enumerate(nums): while dq and nums[dq[-1]] >= value: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: out.append(nums[dq[0]]) return outExample 5 · The same idea for the minimum
from collections import deque
def window_min(nums, k): dq, out = deque(), [] for i, value in enumerate(nums): while dq and nums[dq[-1]] >= value: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: out.append(nums[dq[0]]) return out
print(window_min([1, 3, -1, -3, 5, 3, 6, 7], 3))[-1, -3, -3, -3, 3, 3]
What this code does
- Only the comparison changed.
- The deque holds candidates for the smallest value instead.
Example 6 · Another way: a heap with lazy removal
import heapq
def window_max_heap(nums, k): heap, out = [], [] for i, value in enumerate(nums): heapq.heappush(heap, (-value, i)) while heap[0][1] <= i - k: heapq.heappop(heap) if i >= k - 1: out.append(-heap[0][0]) return out
print(window_max_heap([1, 3, -1, -3, 5, 3, 6, 7], 3))[3, 3, 5, 5, 6, 7]
What this code does
- heapq is a min-heap, so values are stored negated. The top is the maximum.
- Expired items are removed only when they reach the top.
- This is O(n log n), a little slower than the deque.
Only one symbol changed, <= became >=. The deque now goes from smallest to largest.
Next step
Check your understanding
11 quick questions