Return the maximum of every window of size k in O(n) with a monotonic deque of indices, instead of O(n·k) rescans. A FAANG hard explained step by step.
The problem
Return the maximum of each contiguous window of size k as it slides from left to right over nums.
Examples
Example 1
Input
window_max([1, 3, -1, -3, 5, 3, 6, 7], 3)
Expected output
[3, 3, 5, 5, 6, 7]
Example 2
Input
window_max([1], 1)
Expected output
[1]
+ 3 hidden tests on Submit — decreasing, k = n, duplicates.
Edge cases to ask about
- k = 1
- k = len(nums)
- Duplicates
Hints
0/3How an interviewer scores this
0/9Your code runs in real CPython inside your browser — nothing is sent anywhere. The first run downloads the interpreter (about 6 MB, once). Your code is saved on this device as you type.
Complexity Lab
What does this cost as n grows?
Interviewers score the analysis as much as the code. Commit to an answer first — then check it, and measure your code against the optimal one at growing input sizes.
Pick both to reveal the answer.
Measure it
Runs the function on inputs of size 250 up to 16,000 and records the time and peak memory. Slow solutions stop early — a short curve is itself the answer.
From brute force to optimal
The progression an interviewer wants to hear, one step at a time.
| Approach | Time | Space | Idea |
|---|---|---|---|
| max() of every window | O(n·k) | O(k) | |
| Heap with lazy deletion | O(n log n) | O(n) | |
| bestMonotonic deque | O(n) | O(k) | Front is always the window's max; smaller values behind a newer bigger one can never win. |
Walkthrough of the optimal approach (try it yourself first)
Keep a deque of indices whose values decrease from front to back. When x arrives, pop smaller (or equal) values from the back — they will leave the window before x and can never beat it. Pop the front if it has slid out of the window. The front is then the current maximum.
Each index enters and leaves once, so the total work is O(n) despite the inner while.
Complexity: O(n) time, O(k) space. Every index is appended once and popped at most once from the deque.
Reveal the reference solution
from collections import deque def window_max(nums, k): dq = deque() # indices; their values are decreasing out = [] for i, x in enumerate(nums): while dq and nums[dq[-1]] <= x: dq.pop() dq.append(i) if dq[0] <= i - k: dq.popleft() if i >= k - 1: out.append(nums[dq[0]]) return out
The brute force, for comparison
def window_max(nums, k): return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]
Follow-ups interviewers ask
- Sliding window minimum.
- Shortest subarray with sum ≥ K (deque on prefix sums).
Frequently asked interview questions
Core interview concepts, complexities, and follow-ups scored by hiring teams.
What is the time complexity of Sliding Window Maximum (Deque) in Python?
The optimal solution runs in O(n) time and O(k) auxiliary space. Every index is appended once and popped at most once from the deque.
What is the brute-force approach, and how do you optimise it?
max() of every window: O(n·k) time, O(k) space. Heap with lazy deletion: O(n log n) time, O(n) space. Monotonic deque: O(n) time, O(k) space. Front is always the window's max; smaller values behind a newer bigger one can never win.
What follow-up questions do interviewers ask about Sliding Window Maximum (Deque)?
Sliding window minimum. Shortest subarray with sum ≥ K (deque on prefix sums).