Sliding Window Maximum

A running sum can be repaired by adding and subtracting. A running maximum cannot: when the maximum leaves the window, you have no idea what the next largest value is without looking again. This problem is about keeping just enough information to answer that question in O(1). The tool is a double-ended queue kept in decreasing order.

The problem

Given an array of integers and a window size k, slide the window from the left end to the right end one step at a time, and return a list of the largest value in each window.

• nums = [2, 7, 3, 1, 5, 2, 6, 2], k = 3 → [7, 7, 5, 5, 6, 6]. The windows are [2,7,3], [7,3,1], [3,1,5], [1,5,2], [5,2,6] and [2,6,2].
• nums = [4], k = 1 → [4].

Constraints: 1 ≤ k ≤ n ≤ 10⁵, values between −10⁴ and 10⁴.

Clarifying questions

• Is k at most n? Yes, so there are always n − k + 1 windows.
• Can values repeat or be negative? Yes to both.
• Return values or positions? Values.

Approach 1: take the max of every window

def max_sliding_window_brute(nums: list[int], k: int) -> list[int]:    """Recompute each window's maximum: O(n * k)."""    return [max(nums[i:i + k]) for i in range(len(nums) - k + 1)]

Time: O(n·k). With n = 10⁵ and k = 5 × 10⁴, that is about 2.5 × 10⁹ comparisons. Space: O(k) for each slice, plus the output.

Approach 2: a max-heap with lazy removal

Push (−value, index) into a heap as each element enters. The top is the largest value, but it might be an element that has already left the window. So before reading the top, pop entries whose index is too old.

1import heapq234def max_sliding_window_heap(nums: list[int], k: int) -> list[int]:5    """Max-heap of (-value, index); drop expired tops before reading. O(n log n)."""6    heap: list[tuple[int, int]] = []7    result: list[int] = []8    for end, value in enumerate(nums):9        heapq.heappush(heap, (-value, end))10        while heap[0][1] <= end - k:       # top has slid out of the window11            heapq.heappop(heap)12        if end >= k - 1:13            result.append(-heap[0][0])14    return result

Time: O(n log n). Old entries are removed only when they reach the top, so the heap can hold up to n entries (on an increasing array, nothing is ever removed), and each push and pop costs O(log n). Space: O(n). That is good enough for n = 10⁵, but there is a linear answer.

The key insight

Suppose a new value enters and it is larger than some older value still in the window. That older value can never again be the maximum of any window. Every future window that contains the older value also contains the newer one, because the newer one arrived later and so leaves later. And the newer one is bigger.

So the older, smaller values can be thrown away for good. What is left, from oldest to newest, is a list of values that decrease: each one is smaller than everything older than it that is still kept. The oldest kept value is the largest, so it is the window's maximum. Keep indices rather than values, so you can tell when the front has slid out of the window.

This structure is a monotonic deque: a double-ended queue whose contents stay in sorted order. New elements go on the back after popping smaller ones off the back; expired elements come off the front.

Approach 3: monotonic deque

1from collections import deque234def max_sliding_window(nums: list[int], k: int) -> list[int]:5    """Deque of indices whose values strictly decrease from front to back. O(n)."""6    candidates: deque[int] = deque()7    result: list[int] = []8    for end, value in enumerate(nums):9        while candidates and nums[candidates[-1]] <= value:10            candidates.pop()                 # smaller and older: can never win again11        candidates.append(end)12        if candidates[0] <= end - k:13            candidates.popleft()             # the front has slid out of the window14        if end >= k - 1:15            result.append(nums[candidates[0]])16    return result

At most one index expires per step, because the window moves by one, so an if is enough for the front.

Dry run on [2, 7, 3, 1, 5, 2, 6, 2], k = 3 (the deque is shown as values, front first):

The result is [7, 7, 5, 5, 6, 6]. At end = 4, the 7 at index 1 has left the window (which now covers indices 2 to 4), so it comes off the front.

Time: O(n). Each index is appended once and removed at most once, from either end, so all the pops together cost O(n), the same amortised argument as the window's start pointer. Space: O(k): the deque only holds indices from the current window.

Edge cases

• k = 1. Every element is its own window. The deque holds one index at a time; the output equals the input.
• k = n. One window; the output is [max(nums)].
• Repeated values, [5, 5, 5]. The <= pops the older 5 when the newer one arrives, which keeps the deque short. Using < also gives correct output, but keeps equal values and can let the deque hold up to k entries.
• A strictly decreasing array. Nothing is ever popped from the back; every value leaves by expiring from the front.

Follow-ups

• "Window minimum instead." Flip the comparison: pop from the back while the back's value is >= the new one, so values increase from front to back.
• "Longest subarray where max − min is at most a limit." A variable window with two deques, one for the maximum and one for the minimum; shrink while max − min is too large.
• "Shortest subarray with sum at least K, negatives allowed." Prefix sums plus a monotonic deque of prefix indices; the plain sliding window fails there because of the negatives.