Problem 11 · Two Pointers & Sliding Window

Sliding Window Maximum

HardClassic DSA & systems

01Problem

Given nums and window size k, return the maximum of each contiguous window of size k.

02Key insight

Maintain a deque of indices with strictly decreasing values: smaller elements behind a newer larger one can never be a future max. Each index is pushed and popped once.

03Solution

solution.pypython14 lines

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()  # indices, values decreasing
    result: list[int] = []
    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:
            result.append(nums[dq[0]])
    return result

Try it first.

TimeO(n)

SpaceO(k)

tests.py · 3 passing

tests.pypython3 lines

assert max_sliding_window([1,3,-1,-3,5,3,6,7], 3) == [3,3,5,5,6,7]
assert max_sliding_window([1], 1) == [1]
assert max_sliding_window([9,8,7,6], 2) == [9,8,7]

04Staff-level follow-up

Time-based windows over a metrics stream (e.g. max latency in last 60s)? Same monotonic deque keyed by timestamp, evicting by time instead of index; this is how streaming engines compute rolling max.