Sliding Window Maximum

Sliding Window Maximum asks for the largest value in every window of size k as it slides across the array. The naive answer is easy but slow; the clever one introduces a tool you will reuse everywhere: the monotonic deque.

The slow way first

For each of the n - k + 1 windows, scan all k elements and take the max. That is O(n·k) — for a large window and a large array it crawls.

The wasteful part: when the window slides by one, we re-scan k - 1 elements we already looked at. We throw away work every single step. The question to ask: as the window moves, which elements could ever be the max again?

The idea: keep a decreasing deque of indices

Keep a double-ended queue of indices whose values are strictly decreasing front-to-back. Two rules maintain it as a new index hi arrives:

• Pop the back while the value there is <= the incoming value. Those elements are smaller and newer is bigger, so they can never be the max while the new one is around.
• Pop the front if its index has slid out of the window (front <= hi - k).

After that, the front of the deque is always the maximum of the current window.

The deque never holds more than k indices, and each index is pushed and popped at most once, which is what makes the whole pass O(n).

Walk through it

Step through the animation. hi scans right; lo trails k - 1 behind to show the window. Watch the deque strip: when 3 arrives it pops the smaller 1; when 5 arrives it clears everything smaller; when 7 arrives it pops 6. The front index always names the current window max, which we append to the output once the window is full.

Pseudocode

make an empty deque (holds indices, values decreasing front-to-back)
for each index hi in nums:
    if front index has left the window (front <= hi - k):
        pop it from the front
    while back value <= nums[hi]:
        pop it from the back        # it can never be the max again
    push hi onto the back
    if the window is full (hi >= k - 1):
        record nums[front] as this window's max

The Python solution

from collections import deque
 
def max_sliding_window(nums, k):
    dq = deque()          # holds indices, values decreasing
    out = []
    for hi in range(len(nums)):
        # drop indices that left the window
        while dq and dq[0] <= hi - k:
            dq.popleft()
        # drop smaller values from the back
        while dq and nums[dq[-1]] <= nums[hi]:
            dq.pop()
        dq.append(hi)
        if hi >= k - 1:
            out.append(nums[dq[0]])
    return out

• dq stores indices, not values, so we can tell when the front has slid out of the window.
• The values at those indices stay strictly decreasing from front to back, so the front is always the biggest.
• Lines 8-9 drop a stale front whose index has left the window.
• Lines 11-12 are the monotonic part: pop every back index whose value is <= the new one.
• Once hi >= k - 1 the window is full, so line 15 records nums[dq[0]] — the front — as that window's max.

Complexity

Even though there are two nested while loops, each index can only be pushed once and popped once across the whole run, so the total work is O(n). The deque holds at most k indices, giving O(k) extra space.

When this pattern shows up

Practice