NEW
SLIDING WINDOW
MEDIUM
Sliding Window Maximum
Given an array nums and a window size k, return the maximum of every contiguous window as it slides from left to right.
EXAMPLE
nums = [1,3,-1,-3,5,3,6,7]
k = 3
→ [3,3,5,5,6,7]
HINTS
each costs 2 min
?
What must stay true about the window's contents?
🔒
Which structure removes the max in O(1)?
🔒
Full approach walkthrough
solution.py
tests.py
python 3.12
1from collections import deque
2
3def max_sliding_window(nums, k):
4 dq, out = deque(), []
5
6 for i, n in enumerate(nums):
7 # drop indices outside the window
8 if dq and dq[0] <= i - k:
9 dq.popleft()
10
11 # keep the deque decreasing
12 while dq and nums[dq[-1]] < n:
13 dq.pop()
14
15 dq.append(i)
16 if i >= k - 1:
17 out.append(nums[dq[0]])
18
19 return out
TESTSCOMPLEXITYSCRATCHPAD
18 passed2 failed
✓basic window, k = 30.4ms
✓strictly decreasing input0.6ms
✗k == len(nums)index error, line 17
Run tests
Submit & schedule review