SeniorSenior (6–10 yrs)CodingPythonAmazonGoogleMicrosoft

Sliding Window Maximum

Return the maximum value in every contiguous window of size k in the array.

Answers use simple, clear English.

Time: O(n)Space: O(k)

Quick interview answer

Use a monotonic decreasing deque of indices. Pop back while smaller than the new value; pop front when out of window; front is the max. O(n) time.

Detailed answer

Use a monotonic decreasing deque of indices. Pop back while smaller than the new value; pop front when out of window; front is the max. O(n) time. Heap per window is O(n log k) and acceptable but not optimal.

Full explanation

Heap per window is O(n log k) and acceptable but not optimal.

Real example & use case

Realtime monitoring showing peak CPU in each 5-minute sliding window.

Pros & cons

Pros: optimal O(n). Cons: deque index logic is error-prone under time pressure.

Code example

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    out: list[int] = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Practice code · python (view only · no execution)

from collections import deque

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    out: list[int] = []
    for i, x in enumerate(nums):
        while dq and dq[0] <= i - k:
            dq.popleft()
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

#deque#sliding-window