Sliding Window Maximum

Use a deque that holds the indices of the candidates for the maximum, with their values in decreasing order. When a new value arrives you remove from the back every index whose value is smaller, because the new value makes them redundant. You also drop from the front any index that has fallen out of the window, and the front of the deque always points at the current maximum.

from collections import deque


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


print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_max([1], 1))

The outputs are 3, 3, 5, 5, 6, 7 and 1. The windows of size three have maxima of three, three, five, five, six and seven.

The mechanism is the redundancy rule. If a new value is at least as large as an element behind it, that element can never be the maximum of a window containing both, because the new value will leave the window later and is at least as big. So removing it loses nothing. The deque therefore holds only elements that could still become the maximum, and the front is always the answer.

The trade-off to name is that the answer has to be the front of the deque, so you need a structure that supports removal from both ends, which is exactly what a deque provides and what a plain list does not. The complexity is linear because every index is added once and removed at most once, from either end, so the amortised cost per element is constant even though a single iteration may do several removals.

Slide a window across the array and take the maximum of each window using the built-in max function. It is short, obviously correct, and slow.

from collections import deque


def window_max(values, k):
    result = []
    for start in range(len(values) - k + 1):
        result.append(max(values[start:start + k]))
    return result


print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_max([1, 2, 3, 4], 2))

The outputs are 3, 3, 5, 5, 6, 7 and 3, 4. The first array gives one maximum per window of three elements, and the second gives the maxima of the three overlapping pairs.

The mechanism is that each window is materialised as a slice and scanned by the built-in max, so every element of the array is looked at once per window it belongs to. That is why the cost is proportional to the number of windows multiplied by the window size.

The trade-off to name is that this is quadratic in the size of the input for a fixed window size, whereas the monotonic deque version is linear. It is still the right answer for small inputs, and it is a good way to start an interview because it pins down what the output should be. The insight that unlocks the linear version is that consecutive windows overlap heavily, so most of the work is redundant, and the deque keeps only the elements that could still win.

The same monotonic deque works, with the expiry test driven by the current window size rather than a fixed one. Track the size of the live window and remove from the front any index that has fallen outside it.

from collections import deque


def window_max(values, k):
    window = deque()
    result = []
    for i, value in enumerate(values):
        while window and values[window[-1]] <= value:
            window.pop()
        window.append(i)
        left = max(0, i - k + 1)
        while window and window[0] < left:
            window.popleft()
        result.append(values[window[0]])
    return result


print(window_max([1, 3, -1, -3, 5, 3, 6, 7], 3))
print(window_max([4, 2, 12, 3], 4))

The outputs are 1, 3, 3, 5, 5, 6, 7 and 12. The second call uses a window as wide as the whole array, so the running maximum never leaves the window and the result is the running maximum of the prefix.

The mechanism is the same redundancy rule as before. An element smaller than one that arrived later can never win a window containing both, so it is discarded. What changes is the expiry condition: instead of comparing against a fixed index bound, you compute the left edge of the current window and drop anything to its left.

The trade-off to name is that a shrinking window needs the left edge computed from the current size, and if the size varies on every step you have to pass the size in rather than fixing it. The algorithm still holds, because the deque always contains exactly the elements of the live window that could still be the maximum. If the window grows as well as shrinks, the same code works with the left edge derived from the minimum size seen so far.