The Index That Left

Sliding window minimum with a monotonic deque of indices. One maintenance step is missing.

from collections import deque

def window_mins(a, k):
    dq, out = deque(), []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] >= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(a[dq[0]])
    return out

Run it on a = [2, 1, 4, 5, 3, 4, 1, 2] with k = 4. Which window is the first one reported wrongly?

None of them on this input; the stale index only wastes memory, since a value that already left the window is never smaller than the true minimum

The third window, indices 2..5; it reports 1 but the minimum of [4, 5, 3, 4] is 3

The second window, indices 1..4; index 0 is still in the deque and drags the answer down

Every window after the first, because index 1 is never removed from the front