DSA Sliding Window Maximum

The problem

Sliding window maximum asks for the largest value inside every window of a fixed size k. A window is a contiguous run of k values. The window slides one step at a time from the left end of the list to the right end.

The answer holds one maximum per window, in window order. The cases below are the ones this article solves.

cases = [
    ([1, 3, -1, -3, 5, 3, 6, 7], 3, [3, 3, 5, 5, 6, 7]),
    ([1, 3, -1, -3, 5, 3], 3, [3, 3, 5, 5]),
    ([5, 4, 3, 2, 1], 2, [5, 4, 3, 2]),
    ([2, 2, 2], 2, [2, 2]),
    ([4, 1, 3, 5, 2], 5, [5]),
]
for nums, k, expected in cases:
    print("nums", nums, "k:", k, "maxima:", expected)

The third case falls steadily, so every window answers its own first value. The fourth case repeats one value, and both windows still answer it.

Intuition: look at each window and pick the biggest

The first idea reads each window on its own and picks the largest value inside it. The windows of the second case are printed below with their maxima. The answers are plainly right.

nums = [1, 3, -1, -3, 5, 3]
k = 3
for i in range(len(nums) - k + 1):
    window = nums[i:i + k]
    print("window", window, "maximum:", max(window))

The trap is repetition. Neighbouring windows share k minus 1 values, yet the plain reading compares them all again. The shared work is paid in full at every step.

Brute force: rescan every window

The brute force is the intuition written as a function. Each window is scanned from its first value to its last. A counter records the comparisons inside the scans.

def naive_maxima(nums, k):
    checks = 0
    result = []
    for i in range(len(nums) - k + 1):
        best = nums[i]
        for j in range(i + 1, i + k):
            checks += 1
            if nums[j] > best:
                best = nums[j]
        result.append(best)
    return result, checks

for nums, k in [([1, 3, -1, -3, 5, 3, 6, 7], 3), ([1, 3, -1, -3, 5, 3], 3), ([5, 4, 3, 2, 1], 2)]:
    maxima, checks = naive_maxima(nums, k)
    print("nums", nums, "k:", k, "maxima:", maxima, "checks:", checks)

The check count is the window count times k minus 1. A list of a thousand values with a window of a hundred pays about ninety thousand checks. The next section removes that factor.

The optimal solution: a monotonic queue of candidates

A monotonic queue is a double-ended queue that keeps candidate indices in decreasing value order, and its front always holds the current window's maximum. That one structure is the whole method.

Each new value evicts weaker candidates from the back, because a smaller earlier value can never win while the new value is in range. Indices that slide out of the window leave from the front. Storing indices, not values, lets the queue expire members by position.

from collections import deque


def deque_maxima(nums, k):
    window = deque()
    result = []
    for i, value in enumerate(nums):
        while window and window[0] <= i - k:
            window.popleft()
        while window and nums[window[-1]] <= value:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

cases = [
    ([1, 3, -1, -3, 5, 3, 6, 7], 3, [3, 3, 5, 5, 6, 7]),
    ([1, 3, -1, -3, 5, 3], 3, [3, 3, 5, 5]),
    ([5, 4, 3, 2, 1], 2, [5, 4, 3, 2]),
    ([2, 2, 2], 2, [2, 2]),
    ([4, 1, 3, 5, 2], 5, [5]),
]
for nums, k, expected in cases:
    result = deque_maxima(nums, k)
    print("nums", nums, "k:", k, "->", result, "expected:", expected, "match:", result == expected)

All five cases pass. Each index enters the queue once and leaves once, so the whole list costs one pass.

Walkthrough: [1, 3, -1, -3, 5, 3] with k = 3

The state is the queue of candidate indices with their values. Each step first expires the front if it aged out, then evicts weaker values from the back, then appends the new index. Once the first window fills, the front value is the answer for that window.

from collections import deque

nums = [1, 3, -1, -3, 5, 3]
k = 3
window = deque()
for i, value in enumerate(nums):
    while window and window[0] <= i - k:
        window.popleft()
    while window and nums[window[-1]] <= value:
        window.pop()
    window.append(i)
    state = [(index, nums[index]) for index in window]
    print("i =", i, "value:", value, "queue:", state, end=" ")
    if i >= k - 1:
        print("-> window maximum:", nums[window[0]])
    else:
        print("-> window not full yet")

At i = 4 the old maximum, 3 at index 1, leaves by age from the front. The value 5 then clears the back in the same step. The queue never holds a value that a later, larger value has already beaten.

Complexity

The brute force scans each window, so its time is O(n k) for n values and window size k. The deque version appends each index once and removes it at most once, so its time is O(n) whatever k is.

The deque stores at most k indices, so its extra space is O(k). The brute force stores only its running best, so its extra space is O(1). The counts below run both on growing lists with the window set to half the list.

from collections import deque


def naive_checks(nums, k):
    checks = 0
    for i in range(len(nums) - k + 1):
        best = nums[i]
        for j in range(i + 1, i + k):
            checks += 1
            if nums[j] > best:
                best = nums[j]
    return checks


def deque_moves(nums, k):
    window = deque()
    moves = 0
    for i, value in enumerate(nums):
        while window and window[0] <= i - k:
            window.popleft()
            moves += 1
        while window and nums[window[-1]] <= value:
            window.pop()
            moves += 1
        window.append(i)
        moves += 1
    return moves

for n in [6, 60, 600]:
    nums = [(i * 29) % 17 - 8 for i in range(n)]
    k = n // 2
    print("values:", n, "k:", k, "- brute checks:", naive_checks(nums, k), " deque moves:", deque_moves(nums, k))

At 600 values the brute force pays about ninety thousand checks. The deque pays under two moves per value, and its count does not grow with k at all.

Edge cases and pitfalls

A window of size 1 returns the list itself. A window as wide as the list returns a single maximum. A window wider than the list has no windows to answer, so the result is empty.

from collections import deque


def deque_maxima(nums, k):
    window = deque()
    result = []
    for i, value in enumerate(nums):
        while window and window[0] <= i - k:
            window.popleft()
        while window and nums[window[-1]] <= value:
            window.pop()
        window.append(i)
        if i >= k - 1:
            result.append(nums[window[0]])
    return result

nums = [4, 1, 3, 5, 2]
print("k = 1:", deque_maxima(nums, 1))
print("k = 5:", deque_maxima(nums, 5))
print("k wider than the list:", deque_maxima([2, 1], 5))
print("all equal:", deque_maxima([2, 2, 2], 2))
print("single value:", deque_maxima([9], 1))

Equal values carry the classic pitfall. The back eviction uses less-than-or-equal, so an older copy leaves when an equal newer copy arrives. The newer copy outlives the older one, so no window loses its maximum early. Keeping the older copy instead would let it expire mid-window and drop a maximum that is still present.