Sliding Window Minimum

Interview Prep

HardSliding Window Variation of Sliding Window Maximumarraysmonotonic-deque

The problem

Given an array and a window size k, return the minimum of each length-k sliding window. Symmetric sibling of Sliding Window Maximum.

Pattern: monotonic-increasing deque

Identical algorithm to the max version with the comparison flipped. The deque holds indices with values strictly increasing front-to-back. When a new element arrives, pop from the back any index whose value is greater-or-equal — those can never be the minimum of any future window that also contains the new element.

The front of the deque is always the minimum of the current window. Indices fall off the front when they leave the window. Each index is pushed and popped at most once, so total work is O(n).

Solution

from collections import deque

def min_window(nums: list[int], k: int) -> list[int]:
    """O(n).  Monotonic-increasing deque of indices."""
    dq = deque()          # indices, nums[dq] strictly increasing front-to-back
    out = []
    for i, x in enumerate(nums):
        # 1) Drop indices that have left the window
        if dq and dq[0] <= i - k:
            dq.popleft()
        # 2) Maintain increasing property: anyone bigger than x can never be the min again
        while dq and nums[dq[-1]] >= x:
            dq.pop()
        dq.append(i)
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Trace

nums = [1, 3, -1, -3, 5, 3, 6, 7], k = 3

i=0, x=1:   dq=[0]                  window not full
i=1, x=3:   3 > 1 -> push.  dq=[0, 1].   not full
i=2, x=-1:  -1 <= 1 -> pop 0. -1 <= 3 -> pop 1.  dq=[2].   out=[-1]
i=3, x=-3:  -3 <= -1 -> pop 2.  dq=[3].   out=[-1, -3]
i=4, x=5:   dq[0]=3 == 4-3, pop front. dq=[].
             5 > nothing.  dq=[4].   out=[-1, -3, -3]
i=5, x=3:   3 <= 5 -> pop 4.  dq=[5].   out=[-1, -3, -3, 3]
i=6, x=6:   6 > 3 -> push.  dq=[5, 6].   out=[..., 3]
i=7, x=7:   7 > 6 -> push.  dq=[5, 6, 7].
             dq[0]=5 <= 7-3=4? no, 5>4.   out=[-1, -3, -3, -3, 3, 3]

Wait, recompute: dq[0] is an INDEX. After i=7 the window is [5..7]. dq[0]=5 is the
oldest still-valid index; nums[5]=3.

return [-1, -3, -3, -3, 3, 3]

Complexity

Why this version shows up so often

Sliding Window Minimum has a more direct application than its max sibling: it's the inner loop of several optimized DP problems. For instance, "shortest subarray sum ≥ K with negatives" reduces to a monotonic deque over prefix-sum indices; "Jump Game VI" is a DP where the recurrence is dp[i] = nums[i] + max(dp[i−k..i−1]), and the inner max becomes a sliding-window-max query.

Master the deque mechanics on Min and Max, then most monotonic-queue DP problems become routine.

Symmetric problems to practice