Sliding Window Maximum via collections.deque
Tracking peak metrics across a moving time window of size $K$ naively takes $O(N \times K)$ time. A monotonic double-ended queue (`collections.deque`) stores candidate indices in descending order. By dropping expired indices from the left and smaller elements from the right, the window maximum is always at `q[0]` in $O(N)$ time 🪟📊⚡.
from collections import deque
def window_max(nums, k):
q, res = deque(), []
for i, x in enumerate(nums):
while q and q[0] < i - k + 1: q.popleft()
while q and nums[q[-1]] < x: q.pop()
q.append(i)
if i >= k - 1: res.append(nums[q[0]])
return res
print("Peak Window:", window_max([1, 3, -1, -3, 5], 3))
# 22. Sliding Window Maximum via collections.deque Calculating peak network bandwidth, max stock prices, or high-water memory marks over sliding 1-minute or 1-hour windows is standard practice in stream telemetry. Recalculating `max(window)` at every tick destroys performance when $K$ is large 🛑. ```python # The Monotonic Deque Sliding Invariant: # Window Size K = 3 # Array: [1, 3, -1, -3, 5, 3, 6, 7] # # At index 1 (val 3): 3 > 1 -> Pop index 0! Deque = [1] (val 3) # At index 2 (val -1): -1 < 3 -> Append. Deque = [1, 2] (vals: 3, -1) -> Max is nums[1] = 3 # At index 3 (val -3): -3 < -1 -> Append. Deque = [1, 2, 3] -> Max is 3 # At index 4 (val 5): Index 1 expired! Popleft. # 5 > -3 and 5 > -1 -> Pop 3, Pop 2! Deque = [4] (val 5) -> Max is 5 ``` ### Why collections.deque is Mandatory - Python lists take $O(N)$ to pop from index 0. - `collections.deque` uses a doubly linked list of fixed-size blocks in C, guaranteeing **$O(1)$ pops from both ends**. - Every element enters and exits the deque at most once: **strictly $O(N)$ runtime** 🪟📊⚡. --- ### Interactive Pop-Quiz 🧠#### Why must indices rather than raw numerical values be stored in the deque? - [ ] Storing indices lets the algorithm determine whether an element has slipped past the left boundary of the sliding window (`q[0] < i - k + 1`) 🪟 - [ ] Because collections.deque cannot store negative integers - [ ] Because Python memory addresses require index pointers - [ ] To force the queue into multithreaded mode --- ### Practical Challenge 🎯 Implement `max_sliding_window(nums: list[int], k: int) -> list[int]` using `collections.deque`. Maintain indices of decreasing values, evict expired indices from the front, and record `nums[q[0]]` once the window reaches size `k`. Test with `nums = [1, 3, -1, -3, 5, 3, 6, 7]` and `k = 3`, assert `[3, 3, 5, 5, 6, 7]`, and print result. <details> <summary>Solution</summary> ```python from collections import deque def max_sliding_window(nums: list[int], k: int) -> list[int]: if not nums or k == 0: return [] q = deque() res = [] for i, n in enumerate(nums): while q and q[0] < i - k + 1: q.popleft() while q and nums[q[-1]] < n: q.pop() q.append(i) if i >= k - 1: res.append(nums[q[0]]) return res numbers = [1, 3, -1, -3, 5, 3, 6, 7] window_size = 3 result = max_sliding_window(numbers, window_size) assert result == [3, 3, 5, 5, 6, 7] print(f"Sliding window maximum verified: {result}") ``` </details>