Sliding Window Maximum (LeetCode 239)

The problem

You get an integer array nums and a window size k. A window of k consecutive elements slides from the left end to the right end, one step at a time. Return a list of the maximum value in each window position.

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

The windows are [1,3,-1], [3,-1,-3], [-1,-3,5], [-3,5,3], [5,3,6] and [3,6,7], with maxima 3, 3, 5, 5, 6 and 7.

How to think about it

Start with brute force. For each of the n − k + 1 windows, scan its k elements for the max: O(n·k). A heap of the window improves this to O(n log n), with lazy removal of elements that have left.

Why a running value doesn’t work. For a sum you can add the incoming element and subtract the outgoing one. A maximum can’t be “subtracted”: when the current max leaves the window, you need to know the next biggest, and the one after that.

The key insight: some elements can never be the max again. If a new element x arrives and an older element in the window is smaller than or equal to x, that older one is useless: it leaves the window before x does, and x is at least as big for its whole remaining life. So throw it away. If you do this every time, the elements left over are in decreasing order from front to back. The front is the biggest, so it’s the window’s max.

Keep indices, not values, so you can tell when the front has slid out of the window (its index is ≤ i − k). Use a deque, because you pop from the back (dominated elements) and from the front (expired elements).

Which pattern is this? A fixed-size sliding window backed by a monotonic deque. The tell is “max (or min) of every window”.

Approach

1. Keep a deque dq of indices whose values are decreasing.
2. For each index i with value x, pop from the back while nums[dq[-1]] <= x, then append i.
3. If the front index has left the window (dq[0] <= i - k), pop it from the front.
4. Once the first full window is formed (i >= k - 1), append nums[dq[0]] to the result.
5. Return the result.

Solution

from collections import deque

def max_sliding_window(nums, k):
    dq = deque(); res = []                          # indices, values decreasing
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x: dq.pop()    # dominated: never the max again
        dq.append(i)
        if dq[0] <= i - k: dq.popleft()             # front slid out of the window
        if i >= k - 1: res.append(nums[dq[0]])      # front is the window max
    return res
# max_sliding_window([1,3,-1,-3,5,3,6,7], 3) -> [3,3,5,5,6,7]

Dry run

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

(At i = 0 the deque is just [0]; at i = 1 the 3 pops it.) The result is [3, 3, 5, 5, 6, 7].

Complexity

• Time: O(n). Each index is appended once and popped at most once, from either end.
• Space: O(k). The deque only holds indices from the current window.

Edge cases and pitfalls

• k = 1: every element is its own max; the output equals the input.
• k = n: one window, one output, the overall max.
• Strictly decreasing input keeps the deque full, and the expiry check is what removes old fronts.
• Storing values instead of indices loses the ability to tell when the front expires, especially with duplicates.
• < vs <= when popping. Both are correct; <= keeps the deque shorter by dropping equal, older values.

Related problems

• Daily Temperatures (LeetCode 739): the same “pop what the new element dominates” idea, as a monotonic stack.
• Maximum Average Subarray I (LeetCode 643): a fixed window where a running sum is enough.
• Kth Largest Element in a Stream (LeetCode 703): the heap-based way to keep track of large values as data arrives.