Sliding Window Minimum, in depth: the monotonic deque invariant, an amortised O(n) proof, time-based windows and DP acceleration

The idea: dominated values can be forgotten

Start from a question: when the window moves right and a new value x arrives, which old values can still become the minimum of some future window? Any older value y with y >= x is finished. It entered earlier, so it will leave the window earlier than x, and while both are inside, x is at least as small. y can never again be the unique answer. Throwing it away loses nothing.

Apply that rule every time and the survivors have a special shape. Read from oldest to newest, their values strictly increase, because any older value that was not smaller than a newer one has been removed. The oldest survivor is therefore the smallest, so it is the window minimum. The only other way a survivor leaves is by age: when its index falls out of the window, it is dropped from the old end. A double-ended queue supports exactly these operations: push and pop at the back for new values, pop at the front for expired ones, peek at the front for the answer.

The invariant, stated precisely: the deque holds indices j1, j2, ..., jm of the current window in increasing order, with A[j1] < A[j2] < ... < A[jm], and every index of the window that is not in the deque has a later index in the deque with a value no larger. From that, A[j1] is the minimum of the window.

The algorithm in code

The implementation stores indices, not values, because expiry is decided by position. The window ending at i covers indices i-k+1 through i, so an index j has expired when j <= i-k.

from collections import deque

def sliding_window_min(a, k):
    if k <= 0:
        raise ValueError("k must be positive")
    if k > len(a):
        return []
    dq = deque()          # indices; a[dq[0]] < a[dq[1]] < ...
    out = []
    for i, x in enumerate(a):
        # 1. evict the front if it has left the window
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2. drop every older value that x dominates
        while dq and a[dq[-1]] >= x:
            dq.pop()
        dq.append(i)
        # 3. once the first full window exists, the front is its minimum
        if i >= k - 1:
            out.append(a[dq[0]])
    return out

def sliding_window_max(a, k):
    return [-v for v in sliding_window_min([-x for x in a], k)]

assert sliding_window_min([4, 2, 12, 11, -5, 3, 6, 8], 3) == [2, 2, -5, -5, -5, 3]

Three details matter. The eviction test uses if, not while: the window moves one step per element, so at most one index can expire per step, and it can only be the front because indices in the deque are increasing. The domination test uses >= so that equal values keep only the newest copy, which keeps the deque strictly increasing and slightly shorter; > is also correct but keeps duplicates. The maximum is the same algorithm with the comparison reversed; negation, shown above, works for numbers but not for arbitrary orderable keys, so production code usually takes a comparator.

Why it is correct and why it is linear

Correctness follows from the invariant. Initially the deque is empty and the invariant holds vacuously. Suppose it holds before step i. Eviction removes only an index outside the new window. The back-popping loop removes indices whose values are at least x; each of those now has a later index, i, with a value no larger, which is what the invariant demands of indices not in the deque. Appending i keeps the values strictly increasing because the loop stopped at a smaller value or an empty deque. So the invariant holds after step i, and the front is the window minimum.

Running time uses an amortised count rather than a per-step bound. A single step can pop many elements, up to k, which looks like O(nk). But each index is appended exactly once and removed at most once, either from the back or from the front. Over the whole run there are n appends and at most n removals, so the total work is at most 2n deque operations plus n comparisons that end a back-popping loop. That is O(n) total, O(1) amortised per element, and the deque never holds more than k indices. The worst case for a single step is a long increasing run followed by a very small value, which clears the whole deque in one go; the accounting already charged those pops to the appends that created them.

Worked example

Walk through the figure. At i=1 the value 2 arrives and pops 4, because 4 can never be a minimum while 2 is in the window. At i=2 the first full window [4, 2, 12] is complete; 12 is larger than 2, so it is kept behind it, and the answer is the front, 2. At i=3, 11 pops 12, because 11 is smaller and newer, and the answer is still 2. At i=4, the front index 1 has expired because 1 <= 4-3, so 2 is evicted from the front, and -5 then clears 11 from the back. The deque is just [-5]. Indices 5 and 6 append 3 and 6 behind it. At i=7 the index of -5 is 4, which equals 7-3, so it expires, 8 is appended, and the answer is 3. The output is [2, 2, -5, -5, -5, 3], six answers for eight inputs and k=3, matching n-k+1.

Count the operations: eight appends, three back-pops (4 at i=1, 12 at i=3 and 11 at i=4) and two front evictions (2 at i=4 and -5 at i=7). Eight appends and five removals is thirteen deque operations for eight elements, inside the 2n bound of sixteen.

Alternatives and when to prefer them

The deque is not the only linear method, and knowing the alternatives tells you when to use them.

The two-stack queue deserves a sentence because it generalises. Keep an input stack and an output stack, each entry storing its value and the minimum of the stack below and including it. Push to the input stack; when popping and the output stack is empty, move everything across. The window minimum is the smaller of the two stack-top minima. It works for any associative operation, such as gcd or a matrix product, where a monotonic deque does not apply, because domination only makes sense for min and max. For range queries that are not sliding at all, see Segment Tree, in depth; for the heap approach and its costs, the priority queue deep dive.

Time-based windows for streams

Real streams rarely have a fixed count window. Monitoring asks for the minimum over the last 60 seconds, however many samples arrived. The same deque works: store (timestamp, value) pairs, pop from the back while the stored value is at least the new one, and evict from the front with a while loop, because several samples can expire at once when the clock jumps.

from collections import deque

class RollingMin:
    # Minimum over the last `horizon` seconds of a stream with non-decreasing timestamps.
    def __init__(self, horizon):
        self.horizon = horizon
        self.dq = deque()       # (t, v), v strictly increasing front to back
        self.last_t = float("-inf")

    def add(self, t, v):
        if t < self.last_t:
            raise ValueError("timestamps must not go backwards")
        if v != v:              # NaN: reject rather than poison comparisons
            raise ValueError("NaN sample")
        self.last_t = t
        while self.dq and self.dq[-1][1] >= v:
            self.dq.pop()
        self.dq.append((t, v))

    def query(self, now):
        while self.dq and self.dq[0][0] <= now - self.horizon:
            self.dq.popleft()
        return self.dq[0][1] if self.dq else None

Separating add from query matters in services: the answer must reflect expiry at query time even if no new sample has arrived. Decide explicitly whether the boundary is inclusive; the code above treats a sample exactly one horizon old as expired. Library rolling functions make their own choice here, and mixing two conventions in one dashboard produces off-by-one-sample disagreements that are hard to explain.

Accelerating dynamic programming

The deque is also a dynamic programming accelerator. Consider: a frog on stones 0..n-1 can jump at most k stones forward, landing on stone j costs c[j], and we want the minimum total cost to reach the last stone. The recurrence is dp[j] = c[j] + min(dp[j-k..j-1]). Computed directly it is O(nk); the inner min is a sliding window minimum over the dp array itself, so it drops to O(n).

def min_cost_bounded_jumps(c, k):
    n = len(c)
    dp = [0] * n
    dp[0] = c[0]
    dq = deque([0])                      # indices into dp, dp values increasing
    for j in range(1, n):
        while dq[0] < j - k:             # outside the reachable range j-k .. j-1
            dq.popleft()
        dp[j] = c[j] + dp[dq[0]]
        while dq and dp[dq[-1]] >= dp[j]:
            dq.pop()
        dq.append(j)
    return dp[-1]

The order of operations differs from the plain version: the window for dp[j] ends at j-1, so the query happens before j is pushed. Getting that order wrong silently includes dp[j] in its own minimum. The same trick speeds up bounded knapsack, some scheduling recurrences and the constrained-subsequence-sum family.

Failure modes

• Storing values instead of indices. Expiry cannot be decided from a value, and with duplicates you evict the wrong copy. Store indices or timestamps.
• Emitting before the first full window. Answers for i < k-1 are minima of partial windows. Decide whether you want them; most specifications do not.
• Wrong expiry boundary. dq[0] < i - k keeps one stale index; the window covers i-k+1..i, so the test is <= i - k. A brute-force comparison on random inputs catches this in seconds.
• NaN in the stream. Every comparison with NaN is false, so a NaN neither pops nor is popped from the back, and the increasing invariant breaks. With [1, NaN, 0] and k=3 the deque ends as [1, NaN, 0] and reports 1, not 0; once the NaN reaches the front it reports NaN. Wrong answers, not a crash. Filter or reject NaN at the boundary.
• Out-of-order timestamps. A late sample breaks the assumption that the front is oldest. Buffer and reorder within a lateness bound, or reject late data, before the deque.
• Using list.pop(0) in Python. It is O(k), which turns the algorithm quadratic in k. Use collections.deque or a ring buffer with head and tail indices.
• Max and min sharing a deque. They need opposite invariants. Keep two deques when you need both.

Testing and performance in practice

Testing is cheap and catches nearly every bug above: compare against the O(nk) rescan on thousands of random arrays with small value ranges (to force ties), random k including 1 and n, and empty input. Property tests that also check the deque invariant after every step, strictly increasing values and in-window indices, localise failures immediately.

For performance, a ring buffer of size k with integer head and tail beats a general deque in compiled languages because it never allocates. In vectorised Python, pandas Series.rolling(k).min() and SciPy's scipy.ndimage.minimum_filter1d already implement linear-time rolling minima in compiled code, so write the deque yourself only in streaming loops, DP recurrences or languages without such a library. If you generate training windows from sequences, the windowing semantics in Scala sliding and grouped are worth comparing with your own, and for the heap operations used in the alternative design see Heap Operations.

What to do next

1. Implement sliding_window_min from the invariant without looking, then diff it against the version above.
2. Write the brute-force oracle and a randomised test with ties, k=1, k=n and empty input.
3. Add an invariant check inside the loop under a debug flag.
4. Convert one rolling-min or rolling-max computation in your code base, especially a Python loop with min(a[i-k+1:i+1]), to the deque or to a library rolling function.
5. Implement the time-based RollingMin for one metric and decide the inclusive or exclusive boundary explicitly.
6. Solve the bounded-jump DP with and without the deque and confirm both agree on random inputs.