078. Sliding Window Maximum

Why this mechanism works

A later value at least as large as an earlier candidate dominates it: the later value is better or equal and expires later. Keep only undominated indices in a deque with decreasing values. The front is the current maximum, while front expiration and back domination perform different jobs.

State and boundaries

candidates has increasing indices and strictly decreasing values. Every retained index belongs to the active window.

Protocol

1. Expire indices at or before right-k.
2. Remove back candidates no larger than the incoming value.
3. Append the incoming index.
4. Once k values have arrived, emit the front value.

Visualization

window [1,3,-1] -> deque values [3,-1]
new -3: [3,-1,-3]
new 5 dominates the back until deque [5]

Python implementation

from collections import deque

def window_maximum(nums, k):
    if k < 1 or k > len(nums):
        return []
    candidates = deque()
    output = []
    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 + 1 >= k:
            output.append(nums[candidates[0]])
    return output

Worked execution

Recorded state changes after statements; L numbers refer to the solution file. Long traces are explicitly condensed.

L4 window_maximum: if k < 1 or k > len(nums):
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3

L6 window_maximum: candidates = deque()
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([])

L7 window_maximum: output = []
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([]); output=[]

L8 window_maximum: for right, value in enumerate(nums):
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([]); output=[]; right=0; value=1

L13 window_maximum: candidates.append(right)
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([0]); output=[]; right=0; value=1

L8 window_maximum: for right, value in enumerate(nums):
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([0]); output=[]; right=1; value=3

L12 window_maximum: candidates.pop()
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([]); output=[]; right=1; value=3

L13 window_maximum: candidates.append(right)
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([1]); output=[]; right=1; value=3

... 20 intermediate state changes omitted ...

L8 window_maximum: for right, value in enumerate(nums):
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([6]); output=[3, 3, 5, 5, 6]; right=7; value=7

L12 window_maximum: candidates.pop()
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([]); output=[3, 3, 5, 5, 6]; right=7; value=7

L13 window_maximum: candidates.append(right)
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([7]); output=[3, 3, 5, 5, 6]; right=7; value=7

L15 window_maximum: output.append(nums[candidates[0]])
nums=[1, 3, -1, -3, 5, 3, 6, 7]; k=3; candidates=deque([7]); output=[3, 3, 5, 5, 6, 7]; right=7; value=7

L4 window_maximum: if k < 1 or k > len(nums):
nums=[2, 2, 2]; k=2

L6 window_maximum: candidates = deque()
nums=[2, 2, 2]; k=2; candidates=deque([])

L7 window_maximum: output = []
nums=[2, 2, 2]; k=2; candidates=deque([]); output=[]

L8 window_maximum: for right, value in enumerate(nums):
nums=[2, 2, 2]; k=2; candidates=deque([]); output=[]; right=0; value=2

L13 window_maximum: candidates.append(right)
nums=[2, 2, 2]; k=2; candidates=deque([0]); output=[]; right=0; value=2

L8 window_maximum: for right, value in enumerate(nums):
nums=[2, 2, 2]; k=2; candidates=deque([0]); output=[]; right=1; value=2

L12 window_maximum: candidates.pop()
nums=[2, 2, 2]; k=2; candidates=deque([]); output=[]; right=1; value=2

L13 window_maximum: candidates.append(right)
nums=[2, 2, 2]; k=2; candidates=deque([1]); output=[]; right=1; value=2

... 1 intermediate state changes omitted ...

L8 window_maximum: for right, value in enumerate(nums):
nums=[2, 2, 2]; k=2; candidates=deque([1]); output=[2]; right=2; value=2

L12 window_maximum: candidates.pop()
nums=[2, 2, 2]; k=2; candidates=deque([]); output=[2]; right=2; value=2

L13 window_maximum: candidates.append(right)
nums=[2, 2, 2]; k=2; candidates=deque([2]); output=[2]; right=2; value=2

L15 window_maximum: output.append(nums[candidates[0]])
nums=[2, 2, 2]; k=2; candidates=deque([2]); output=[2, 2]; right=2; value=2

Why the solution is correct

Removing an expired index is mandatory. Removing a dominated candidate is safe because its later replacement remains available whenever the older one would be relevant. The largest retained value stays at the front and represents the active window maximum.

Time and space

O(n) time and O(k) auxiliary deque space, plus output.

Common mistakes

Storing values alone makes expiration ambiguous with duplicates. A heap without removing stale entries can report an out-of-window maximum.

Reasoning card

Transfer exercise

Maintain both minimum and maximum deques to find the longest window whose range is at most a limit.