Sliding Window Maximum

Brute force — scan every window

Move the window one position at a time. At each start, inspect all k values and record the largest. This is the clean baseline because it follows the task word for word.

def max_sliding_window(nums: list[int], k: int) -> list[int]:
    result: list[int] = []
 
    for left in range(len(nums) - k + 1):
        best = nums[left]
        for index in range(left + 1, left + k):
            if nums[index] > best:
                best = nums[index]
        result.append(best)
 
    return result

Neighboring windows share k - 1 positions, yet this approach compares those values all over again. Time O(n·k), space O(1) beyond the returned array.

Monotonic deque — keep only live contenders

A monotonic deque is a double-ended queue whose stored indices have values in a consistent order. Here, values decrease from front to back, so the front always points to the current maximum.

Before adding index right, do two cleanups:

1. Remove the front index if it sits left of the current window.
2. Remove back indices whose values are no greater than nums[right]. The new value outlives them and beats them, so none can become a maximum again.

from collections import deque
 
 
def max_sliding_window(nums: list[int], k: int) -> list[int]:
    candidates: deque[int] = deque()
    result: list[int] = []
 
    for right, value in enumerate(nums):
        while candidates and candidates[0] <= right - k:
            candidates.popleft()
 
        while candidates and nums[candidates[-1]] <= value:
            candidates.pop()
 
        candidates.append(right)
        if right >= k - 1:
            result.append(nums[candidates[0]])
 
    return result

The deque holds every candidate that could still become a maximum. Its front is best now; everything behind it is smaller but may survive longer. Each index enters once and leaves once, whether from the front or back.

Time O(n), space O(k) — the queue never holds indices outside one window.

This pattern works because deletion is backed by proof: an expired index is unavailable, and an index beaten by a newer value can never win a later window.