15. Sliding Window Maximum Load

Problem

Fin's operational dashboards sample the number of concurrent conversations at fixed intervals. To spot peak load, compute the maximum value in every rolling window of size k over that stream (e.g. "peak concurrent conversations in any rolling 5-sample window").

This is the classic Sliding Window Maximum problem, solvable via a monotonic deque in O(n) time. The output length is len(counts) - k + 1 — one maximum per window position as the window slides from the start to the end of the array.

Source: src/15_sliding_window_max_load.py

def sliding_window_max(counts: list[int], k: int) -> list[int]: ...

>>> sliding_window_max([1, 3, -1, -3, 5, 3, 6, 7], k=3)
[3, 3, 5, 5, 6, 7]
>>> sliding_window_max([4, 2, 1, 3], k=2)
[4, 2, 3]

Step-by-Step Approach

1. Maintain a deque of indices (not values) into counts, kept in an order such that the corresponding values are strictly decreasing from front to back — the front index always points at the current window's maximum.
2. For each new index i with value value, first pop from the back of the deque while the value at the back index is <= value. Those back elements can never be the maximum of any future window (once value is in play and outlasts them), so they're permanently useless and safe to discard.
3. Append the current index i to the back of the deque — it's now a candidate for future windows.
4. Evict from the front of the deque if the front index has fallen out of the current window, i.e. dq[0] <= i - k. This keeps the front always representing a valid in-window index.
5. Once the sweep has advanced far enough that a full window of size k exists (i >= k - 1), record counts[dq[0]] as that window's maximum.
6. Repeat for every index; the recorded values, in order, are the answer.

The key insight is that once a smaller value appears after a larger one still in the window, the smaller value can never become the window max before the larger one leaves — so it's safe to discard it immediately, which is what keeps the deque monotonic and bounds each index to at most one push and one pop across the whole run (amortized O(n) total, vs. the naive O(nk) of scanning each window from scratch).

Reference solution

from collections import deque


def sliding_window_max(counts: list[int], k: int) -> list[int]:
    # Monotonic decreasing deque of indices: each index pushed/popped at most once, O(n) time
    # indices, not values, so front-of-window aging can be checked
    dq: deque[int] = deque()
    result: list[int] = []
    # enumerate gives index + value in one pass
    for i, value in enumerate(counts):
        # back (O(1)): drop now-useless smaller candidates
        while dq and counts[dq[-1]] <= value:
            dq.pop()
        dq.append(i)
        # front (O(1)): evict once it's outside the k-wide window
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            result.append(counts[dq[0]])
    return result

Key Functions & Tricks

• collections.deque — O(1) push/pop at both ends; a plain list would make one end O(n).
• Storing indices, not values — needed to test whether the front candidate has aged out.
• dq[-1]/dq.pop() vs. dq[0]/popleft() — O(1) access to back and front only.
• while dq and counts[dq[-1]] <= value: dq.pop() — discards now-useless candidates, keeps amortized O(n).
• if dq[0] <= i - k: dq.popleft() — evicts the front once it's fallen out of the window.
• enumerate(counts) — yields index and value together in a single pass.

How to Recognize This Pattern