EXAMTOPICS / TECHNOLOGY INSIGHTS

Sliding Window Maximum: Deque Algorithm and Examples

The problem: find each window’s maximum

Given a sequence of n numbers and a fixed window length k, return the largest value in every contiguous subarray of length k. Windows overlap: after inspecting positions zero through k - 1, shift one position to the right and repeat. There are n - k + 1 results when 1 <= k <= n. An implementation should explicitly define what happens when the requested window length is zero, negative or larger than the input.

For the values [1, 3, -1, -3, 5, 3, 6, 7] with k = 3, the window maxima are [3, 3, 5, 5, 6, 7]. Negative numbers and repeated values are valid inputs; the algorithm should not depend on the values being nonnegative or distinct. The challenge is to reuse information from neighboring windows instead of rescanning all k values every time.

Baseline: scan every window

The simplest method examines the first k elements, records the largest, advances one position and scans again. Its runtime is O(nk) because the same elements may be compared in several neighboring windows. Aside from the result array, it needs only constant extra working space. For a very short input this can be adequate and easy to validate.

For large n and substantial k, repeated scans waste work. A maximum value can stay relevant for several windows until its index leaves the current range. The optimized solution needs to know not just a candidate value but also the position where that value occurred. Otherwise it cannot efficiently decide when the candidate has expired.

The monotonic deque invariant

Maintain a double-ended queue of candidate indices. From front to back, the corresponding values are in nonincreasing order. The front always represents the maximum within the current valid window. When a new element arrives, discard indices that are already outside the window, then discard candidates from the back whose values are less than or equal to the new value. Append the new element’s index. Each discarded candidate can never be needed as the maximum of a future window that contains the new element, because the newer element is at least as large and expires later.

Keeping indices instead of values solves the expiration problem. At processing position i, an index j is outside the window if j <= i - k. When i >= k - 1, the deque front gives the maximum for the window ending at i. Removing equal-valued older candidates is safe when only maximum values are required; retaining ties would also work with a slightly different invariant.

Python implementation

The following code uses collections.deque, which supports efficient append and removal at both ends. It checks the input window size rather than silently returning a plausible but incorrect result for an invalid k. The algorithm was exercised against negative inputs, duplicate values, a single-element case and the classic example.

from collections import deque

def sliding_max(values, k):
    if not 1 <= k <= len(values):
        raise ValueError("k must be between 1 and len(values)")

    q = deque()  # indices of candidates
    result = []

    for i, value in enumerate(values):
        # Remove indices that have left this window.
        while q and q[0] <= i - k:
            q.popleft()

        # A newer, larger value makes older candidates obsolete.
        while q and values[q[-1]] <= value:
            q.pop()

        q.append(i)
        if i >= k - 1:
            result.append(values[q[0]])

    return result

numbers = [1, 3, -1, -3, 5, 3, 6, 7]
print(sliding_max(numbers, 3))
# [3, 3, 5, 5, 6, 7]

The Python deque documentation describes the double-ended structure used here. A Python list could store the same candidates, but repeatedly removing its first element would introduce unnecessary shifting and could undermine the intended efficiency.

Trace one run by hand

Start with the first three values 1, 3, -1. Index zero is discarded when value 3 arrives; the deque contains the index of 3 followed by the index of -1. The first maximum is 3. Add -3: the index of 3 remains valid and still leads. The second result is 3.

When 5 arrives, candidates -3 and -1 are removed from the back as smaller values. The previous 3 is outside or dominated for the new window. The deque front now identifies 5, producing the next maxima. Later, 6 and 7 replace smaller candidates as they arrive. The sequence of results is 3, 3, 5, 5, 6, 7.

Tracing the indices makes the proof intuitive: the deque never contains an expired index and its values remain ordered. The candidate at the front is not merely the largest observed value globally; it is the largest among elements still eligible for the current window.

Why the runtime is linear

The implementation uses two nested while loops, but that does not make it quadratic. Each index is appended to the deque exactly once. Each index can be removed at most once, either from the front when it expires or from the back when dominated by a newer candidate. Across the entire sequence, the total number of deque insertions and removals is proportional to n.

Therefore the time complexity is O(n). The deque holds at most k indices, so its auxiliary space is O(k); the returned list itself occupies O(n - k + 1) space. These distinctions matter when someone reports the memory cost of an implementation that must return every answer.

Edge cases and implementation choices

When k = 1, every number is its own window maximum, so the result equals the input sequence. When k = n, there is one result: the maximum of the whole sequence. Duplicate values work because the code removes older equal candidates, and a new equal maximum can represent later overlapping windows. Negative numbers require no special case. An empty input cannot have a valid positive-length window under the contract used here.

If the application needs the position of each maximum rather than the value, append the deque front index instead. If a fixed-length stream must emit a result after every new item, the same deque technique can be maintained as data arrives, with a bounded buffer for the values needed by live candidate indices. Changing k during processing is a different problem and should not be assumed to work unchanged.

A heap with lazy deletion is another solution but generally has logarithmic update costs and needs care about stale entries. A prefix/suffix block method can achieve linear time for batch processing with different memory trade-offs. Two-stack maximum queues can also support amortized constant-time operations. The monotonic deque is usually the clearest choice for one fixed sliding-window maximum query.

Practice by verifying rather than memorizing

First implement the brute-force method as a correctness oracle for small inputs. Generate arrays with repeated numbers, negative values and windows of different valid lengths. Compare the deque result with the baseline on every case. If there is a disagreement, print the window bounds and the candidate indices to locate the violated invariant.

After those tests pass, explain why an index leaves from the front and why a smaller candidate leaves from the back. That reasoning transfers to other sliding-window problems, but not every window question requires a monotonic deque. The data structure is justified here because the query asks for a maximum while the window advances one position at a time.