Sliding Window Maximum

Interview Prep

HardSliding Windowarraysmonotonic-deque

The problem

Given an array nums and a window size k, return an array of length n − k + 1 where entry i is the maximum of nums[i..i+k−1].

Why the obvious approaches fall short

A naive scan recomputes the max for every window in O(k), giving O(n · k) total — too slow for the standard interview constraints. A max-heap with lazy deletion gets to O(n log n), but there's an O(n) solution using a deque that's worth memorising because the same pattern solves a whole family of problems. 

def max_window_brute(nums: list[int], k: int) -> list[int]:
    return [max(nums[i:i+k]) for i in range(len(nums) - k + 1)]
# O(n * k) — TLE for large inputs.

Pattern: the monotonic deque

Keep a deque of indices, maintained so the corresponding values are strictly decreasing from front to back. When a new element enters: pop from the back everyone smaller than or equal to it (they can't be the maximum of any future window that also contains the new element). When the front of the deque falls outside the current window, drop it. The maximum of the current window is always at nums[dq[0]].

Every index is pushed once and popped once, so the amortized cost per step is O(1). Total: O(n).

Optimal solution

from collections import deque

def max_window(nums: list[int], k: int) -> list[int]:
    """O(n). Monotonic deque of indices, values decreasing front-to-back."""
    dq = deque()       # indices, nums[dq] strictly decreasing
    out = []
    for i, x in enumerate(nums):
        # 1) Drop indices outside the window
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2) Maintain decreasing property: anyone smaller than x can never be the max again
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        # 3) Once the first full window is reached, the front is the answer
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Trace

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0, x=1:   dq=[0]                window not full
i=1, x=3:   pop 0 (1<=3); dq=[1]   not full
i=2, x=-1:  dq=[1, 2]              out=[3]
i=3, x=-3:  pop none; dq=[1,2,3]   out=[3, 3]
i=4, x=5:   dq[0]=1 == 4-3, pop front; dq=[2,3]
             pop 3 (-3<=5), pop 2 (-1<=5); dq=[4]   out=[3, 3, 5]
i=5, x=3:   dq=[4, 5]              out=[3, 3, 5, 5]
i=6, x=6:   pop 5 (3<=6), pop 4 (5<=6); dq=[6]   out=[3, 3, 5, 5, 6]
i=7, x=7:   pop 6 (6<=7); dq=[7]   out=[3, 3, 5, 5, 6, 7]

result = [3, 3, 5, 5, 6, 7]

Heap variant (also acceptable)

import heapq

def max_window_heap(nums, k):
    """O(n log n). Heap of (-value, index)."""
    heap, out = [], []
    for i, x in enumerate(nums):
        heapq.heappush(heap, (-x, i))
        # Lazy deletion of out-of-window entries from the top
        while heap[0][1] <= i - k:
            heapq.heappop(heap)
        if i >= k - 1:
            out.append(-heap[0][0])
    return out

Complexity

Variations worth knowing