44. Sliding Window Min Response Time

Problem

Track the minimum response time over the last k responses as new response-time measurements stream in. This is the mirror image of the sliding-window-maximum peak-load problem elsewhere in this set: same technique, opposite comparison direction.

Given a list of response times and a window size k, return the minimum value in every contiguous window of k consecutive measurements, in order. The classic approach is a Sliding Window Minimum via a monotonic increasing deque, achieving O(n) time overall (versus the naive O(n*k) of recomputing the min for every window from scratch). The output length is len(times) - k + 1.

Source: src/44_sliding_window_min_response_time.py

def sliding_window_min(times: list[float], k: int) -> list[float]:
    ...

>>> sliding_window_min([4, 2, 12, 11, 3, 5, 6, 1], k=3)
[2, 2, 3, 3, 3, 1]

>>> sliding_window_min([1, 2, 3, 4, 5], k=2)
[1, 2, 3, 4]

>>> sliding_window_min([5], k=1)
[5]

Step-by-Step Approach

1. Maintain a deque of *indices* (not values), kept in an order such that the response times at those indices are strictly increasing from front to back. The front of the deque is therefore always the index of the current window's minimum.
2. For each new measurement at index i with value t: before adding it, pop from the back of the deque any indices whose values are >= t. Those values can never be the minimum of any future window that also contains i, since t is smaller and arrived later (so it stays in the window at least as long) — this is what keeps the deque monotonic.
3. Append index i to the back of the deque.
4. Evict from the *front* of the deque any index that has fallen out of the current k-window (i.e. dq[0] <= i - k), since it's now too old to count.
5. Once i >= k - 1 (the window is fully populated for the first time), the value at the front of the deque, times[dq[0]], is the minimum of the current window — append it to the result.

The key insight is that once a later, smaller value enters the window, every earlier, larger value still in the deque is permanently useless — it will lose to the smaller value in every future window they're both in until the smaller value expires. Discarding those dominated values as soon as they're seen is what collapses the naive O(n*k) re-scan into O(n) amortized, since each index is pushed and popped from the deque at most once.

Reference solution

from collections import deque


def sliding_window_min(times: list[float], k: int) -> list[float]:
    # monotonic increasing deque of indices, O(n) time, O(k) space
    # deque[int] holds indices, not values (PEP 585 subscript)
    dq: deque[int] = deque()
    result: list[float] = []
    # yields (index, value) pairs
    for i, t in enumerate(times):
        # dq stores indices, so look up times[...] to compare
        while dq and times[dq[-1]] >= t:
            # evict dominated (too-large) values from the back
            dq.pop()
        dq.append(i)
        # expiry check: oldest index fell out of the k-window
        if dq[0] <= i - k:
            # evict expired (too-old) index from the front
            dq.popleft()
        if i >= k - 1:
            result.append(times[dq[0]])
    return result

Key Functions & Tricks

• deque[int] = deque() — O(1) push/pop at both ends; holds indices, not values.
• enumerate(times) — yields (index, value) pairs without a manual counter.
• dq.pop() vs dq.popleft() — evict from the back (dominated values) vs. the front (expired indices), both O(1).
• dq[-1] / dq[0] — O(1) peek at either end without popping.
• times[dq[-1]] >= t — indirect comparison since dq stores indices, not values.
• dq[0] <= i - k — expiry check for the oldest surviving index.

How to Recognize This Pattern