Sliding Window Minimum

The mirror twin of Sliding Window Maximum.
Solved by inverting exactly one line: flip the eviction policy to discard larger tails.

Real-World Analogues

Infrastructure

Rolling Baseline Latency Floor
A telemetry agent at the edge calculates the baseline network jitter floor over a rolling 10,000-sample window to distinguish transient network spikes from true persistent degradation.

Distributed Systems & Autoscaling

Minimum Idle Worker Pool
An elastic task orchestrator tracks the minimum count of idle worker threads over the last 10 minutes to trigger proactive auto-scaling before capacity is exhausted.

IoT & Sensor Hardware

Minimum Battery Voltage Floor
An embedded supervisor continuously records battery discharge cycles and alarms if the lowest voltage observed during any rolling 60-second window breaches safe cutoff thresholds.

Interview Abstraction

Sliding Window Minimum strips away the hardware and infrastructure telemetry to ask the mirror mathematical question: given an array nums and a window size k, return the minimum value in every forward-sliding window of length k in $O(n)$ total time.

Recognition

Reach for this pattern when:

• ✓ The window slides strictly forward without rewinding.
• ✓ You must report the minimum at every step.
• ✓ Rescanning window elements creates an $O(nk)$ bottleneck.
• ✓ A min-heap introduces $O(\log k)$ overhead per element.

Why This Problem Matters

This drill proves that the monotonic deque algorithm is policy-driven. The outer loop, index storage, and FIFO expiration logic remain 100% identical to the maximum problem. Only the eviction comparator changes.

The Mental Shift

Naive Thought   → "Search the active window for the smallest element."
Correct Thought → "Delete older elements the moment a smaller or equal newcomer arrives."

Once element $B$ arrives behind element $A$ with $B \le A$, element $A$ can never be the minimum for any current or future window covering both. $A$ is permanently dominated.

Solution Evolution

Why This Beats a Min-Heap

The min-heap answers: “What is the smallest value I have seen?”
The deque answers: “What is the smallest value that is still relevant?”

That single distinction eliminates lazy deletion overhead and drops every window update from $O(\log k)$ to amortized $O(1)$.

Filling the Framework

Only the eviction comparator inverts:

# 1. EVICT: Prune tail candidates that are >= incoming value x
while dq and nums[dq[-1]] >= x:
    dq.pop()

# 2. STORE: Store index for positional expiry checks
dq.append(i)

# 3. EXPIRE: Drop front if it slid out of the active window
if dq[0] <= i - k:
    dq.popleft()

Optimal Solution

from collections import deque
from typing import List

def min_sliding_window(nums: List[int], k: int) -> List[int]:
    if not nums or k <= 0 or k > len(nums):
        return []
    if k == 1:
        return nums[:]
    
    dq = deque()  # stores indices; values nums[dq] strictly increasing
    out = []
    
    for i, x in enumerate(nums):
        # 1. Evict dominated candidates (larger/equal tails)
        while dq and nums[dq[-1]] >= x:
            dq.pop()
        
        # 2. Append current candidate index
        dq.append(i)
        
        # 3. Expire head if out of window
        if dq[0] <= i - k:
            dq.popleft()
        
        # 4. Record answer once first full window is reached
        if i >= k - 1:
            out.append(nums[dq[0]])
            
    return out

Visual Walkthrough

Tracing nums = [1, 3, -1, -3, 5, 3, 6, 7] with k = 3.
Band W is the active window; caret M is the front of the deque (the window’s min).

Complexity Analysis

4-Dimension Edge-Case Matrix

Common Mistakes

• ❌ Flipping the wrong comparator: Using <= instead of >= turns the solution into a maximum finder.
• ❌ Emitting before window reaches size $k$: Only append to output when i >= k - 1.
• ❌ Storing values instead of indices: Prevents testing for positional expiration dq[0] <= i - k.
• ❌ Using > instead of >=: Fails to evict older identical values, unnecessarily bloating memory.

Problem Progression & Difficulty Evolution

Mastering this problem enables you to solve a progression of harder variations:

1. Continuous Subarrays (Medium): Combine min and max monotonic deques simultaneously to track dynamic window bounds (max - min <= 2).
2. Jump Game VI (Medium): Monotonic deque over dynamic programming transitions.
3. Shortest Subarray with Sum at Least K (Hard): Monotonic deque over prefix sums with greedy left-pointer pops.

Principal Lens

The algorithm isn’t valuable because of sliding windows. It is valuable because it replaces recomputation with state maintenance:

$$\text{Precompute} \longrightarrow \text{Maintain} \longrightarrow \text{Incrementally Update}$$

Related Production Systems

• Observability (DataDog / Prometheus): Rolling minimum latency floor and jitter baseline detection.
• Auto-scalers (Kubernetes HPA): Minimum available capacity tracking over dynamic cooling windows.
• Embedded Sensors: Minimum voltage and thermal health monitoring.

Continue Learning

• Pattern Note: Monotonic queue
• Sibling Problem: Sliding Window Maximum
• Next Problem: Continuous Subarrays

Appendix · Design Evolution

Why include alternative solutions?
The goal isn’t to memorize multiple implementations. It is to understand the sequence of design decisions that leads from a straightforward baseline to one that exploits stronger invariants.

When Would I Actually Use These?

A.1 · Brute Force Rescan ($O(nk)$ Time · $O(1)$ Space)

This implementation serves as the correctness baseline. It computes each window independently using Python’s min().

def min_sliding_window_brute(nums: list[int], k: int) -> list[int]:
    if not nums or k <= 0 or k > len(nums):
        return []
    return [min(nums[i : i + k]) for i in range(len(nums) - k + 1)]

A.2 · Min-Heap with Lazy Deletion ($O(n \log k)$ Time · $O(k)$ Space)

Store (val, idx) in a standard binary min-heap. Because interior nodes cannot be removed in $O(1)$, stale entries are purged lazily only when they bubble up to the top.

import heapq

def min_sliding_window_heap(nums: list[int], k: int) -> list[int]:
    if not nums or k <= 0 or k > len(nums):
        return []
    
    heap = []  # (value, index) for min-heap
    out = []
    
    for i, x in enumerate(nums):
        heapq.heappush(heap, (x, i))
        
        if i >= k - 1:
            # Remove expired minima until the root belongs to the current window
            while heap[0][1] <= i - k:
                heapq.heappop(heap)
            out.append(heap[0][0])
            
    return out

A.3 · Comparative Evolution Matrix