DevOps NetworkDevOpsNetwork
Join Free
Advanced

Sliding Window Maximum

hardHeaps (hard) Must-do

Problem statement

You have a series of CPU readings nums and a window size k. A window of k consecutive readings slides from the left end to the right end, one position at a time. Return a list with the maximum reading in each window position, from left to right.

With n readings there are n - k + 1 windows. k is always between 1 and n.

Examples

Example 1

Input: nums = [2,7,3,1,5,4,6], k = 3

Output: [7, 7, 5, 5, 6]

Explanation: The windows are [2,7,3], [7,3,1], [3,1,5], [1,5,4] and [5,4,6].

Example 2

Input: nums = [4,2,12,3], k = 4

Output: [12]

Explanation: The window covers the whole list, so there is one answer.

Hints

Approach

Monotonic deque. Keep a deque of indices whose values are strictly decreasing from front to back. For each new index i:

  1. Pop from the back while the value there is <= nums[i]. Those readings are older and no larger, so they can never be a maximum again.
  2. Append i to the back.
  3. If the front index has slid out of the window (<= i - k), pop it from the front.
  4. Once i >= k - 1, the front holds the index of the current window's maximum.

Every index enters and leaves the deque at most once, so the total work is linear.

ComplexityTime O(n)Space O(k)
Python
from collections import deque
def max_sliding_window(nums, k):
dq, out = deque(), [] # indices, values decreasing front to back
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
print(max_sliding_window([2, 7, 3, 1, 5, 4, 6], 3))
print(max_sliding_window([4, 2, 12, 3], 4))

Follow-up questions

  • Return the window minimum as well, in the same pass (a second deque with increasing values).
  • The readings arrive as a live stream and windows are defined by time (the last 60 seconds), not by count. What changes?

Frequently asked questions

Rolling aggregates over a time window are the bread and butter of monitoring: a max over the last five minutes, peak queue depth, or an alert rule like max_over_time. This problem asks for that aggregate at every step without rescanning the window, and the monotonic deque is the standard answer.

An older reading equal to the new one will leave the window first, and the new one covers it for every remaining window. Popping on <= keeps the deque strictly decreasing and smaller. Popping only on < is also correct, just slightly more work.

Yes. Each index is appended once and removed at most once, from either end. Across the whole run the inner loop does at most n pops in total, so the combined cost is linear (amortised O(1) per reading).