Sliding Window Maximum

You'll build a monotonic deque. It's the stack from Daily Temperatures, plus a way for old values to leave. A deque ("deck") is a list you can add to and remove from at both ends quickly. Read Daily Temperatures first. Related chapter: monotonic deque.

1. The problem

You get a list of integers nums and a window size k. Slide a window of k neighboring numbers across the list, one position at a time. Return the largest number in each window. Assume 1 <= k <= len(nums). Numbers can be negative or repeated. Don't change the input. This is Sliding Window Maximum (LC 239).

There are len(nums) − k + 1 windows. The hard part is what happens when the current largest number leaves the window.

2. A correct baseline

Take the maximum of each window directly.

def baseline(nums, k):
    return [max(nums[start:start + k]) for start in range(len(nums) - k + 1)]

assert baseline([4, 2, 3, 1, 5], 3) == [4, 3, 5]
assert baseline([2, 2, 1], 2) == [2, 2]
assert baseline([-3, -1], 1) == [-3, -1]

Each window costs k steps, so this takes O((n − k + 1) · k) time. With n = 100,000 and k = 50,000, that's about 2.5 billion comparisons.

The bottleneck. Neighboring windows share k − 1 numbers, and the brute force looks at all of them again. The obvious fix is to remember the largest so far, but that breaks when it leaves. In [5, 1, 2] with k = 2, the first maximum is 5. When 5 leaves, remembering "5" doesn't tell you whether 1 or 2 is next. We need backups. The question is which ones.

3. The observation

Take the window [4, 2, 3]. Can the 2 ever be the largest? The 3 came after it, so the 3 stays in every window the 2 is in. And 3 is bigger. So the 2 can never win: drop it for good.

In general, take an older index i and a newer index j with nums[i] <= nums[j]. Any future window holding i also holds j, because i leaves first. So i is never needed again.

After dropping every such index, the ones left have strictly decreasing values, oldest to newest. That gives us everything we need:

• The largest is the oldest one left. Values fall toward the new end, so the front holds the largest.
• A new number removes from the back. It beats every value less than or equal to it, and those all sit at the new end.
• Old indexes leave from the front. The window moves forward, so indexes leave oldest first.

In Daily Temperatures, values only left from the new end, so a stack was enough. Here they also leave from the old end, so we need a deque. Store indexes, because a value alone doesn't say when it leaves the window. This works because the window only moves forward, so whatever leaves, leaves from the old end.

4. The solution and a trace

from collections import deque

class Solution:
    def maxSlidingWindow(self, nums: list[int], k: int) -> list[int]:
        """Return window maxima; requires 1 <= k <= len(nums)."""
        candidates = deque()  # Indexes in the window; their values strictly decrease.
        answer = []
        for right, number in enumerate(nums):
            left = right - k + 1
            while candidates and candidates[0] < left:
                candidates.popleft()
            while candidates and nums[candidates[-1]] <= number:
                candidates.pop()
            candidates.append(right)
            if right >= k - 1:
                answer.append(nums[candidates[0]])
        return answer

solve = Solution().maxSlidingWindow
assert solve([4, 2, 3, 1, 5], 3) == [4, 3, 5]
assert solve([2, 2, 1], 2) == [2, 2]
assert solve([-3, -1], 1) == [-3, -1]
assert solve([5, 1, 2], 2) == [5, 2]

Trace [4, 2, 3, 1, 5] with k = 3:

At right = 3, the 4 leaves, and the backup 3 is already waiting at the front. Remembering only the largest number couldn't give us that backup.

5. Why it works

What stays true. After step right, the deque holds exactly the window's indexes whose value is bigger than everything after them in the window. They're in index order, so their values strictly decrease.

The front is the largest. Let m be the last index in the window that holds the window's largest value. Everything after it is smaller, so m is in the deque. Nothing in the deque is larger, and values fall from front to back, so m is at the front.

Each step keeps it true. When right arrives, any index at the back with a value at most nums[right] no longer qualifies, and the loop removes exactly those. The rest are bigger than nums[right], so they still qualify, and so does right itself. An index that falls out of the window is removed from the front, where the oldest index sits.

6. Cost, edge cases, and failure

Cost. Each index is added once and removed at most once, from one end or the other. So the total is O(n) time despite the nested loops: it grows in step with the list. The deque holds at most k indexes, so O(k) extra space plus the output. Python's deque.popleft() takes O(1) time. A list's pop(0) shifts every element, which would bring back O(nk) time.

Edge cases. k = 1 returns the input's values. k = len(nums) returns one maximum. With repeated values, <= drops the older copy, which leaves the window sooner. < would also be correct, just with a longer deque.

Where it fails. The test for leaving is < left, because index left is still in the window. Off by one, and you throw away a maximum that's still in the window:

class ExpireEarly:  # deliberately wrong: drops index left while it is still in the window
    def maxSlidingWindow(self, nums, k):
        candidates, answer = deque(), []
        for right, number in enumerate(nums):
            left = right - k + 1
            while candidates and candidates[0] <= left:
                candidates.popleft()
            while candidates and nums[candidates[-1]] <= number:
                candidates.pop()
            candidates.append(right)
            if right >= k - 1:
                answer.append(nums[candidates[0]])
        return answer

assert ExpireEarly().maxSlidingWindow([4, 2, 3, 1, 5], 3) == [3, 3, 5]  # wrong: the first window's maximum is 4
assert solve([4, 2, 3, 1, 5], 3) == [4, 3, 5]

The technique itself fails when smaller values still matter. For the window's median, an older, smaller value still affects where the middle is, so you can't drop it. That problem needs two heaps instead.

import random

rng = random.Random(239)
for _ in range(2000):
    nums = [rng.randint(-4, 4) for _ in range(rng.randint(1, 12))]
    k = rng.randint(1, len(nums))
    assert solve(nums, k) == baseline(nums, k), (nums, k)