Sliding Window

The idea

Many problems want the best (longest/shortest/max) contiguous subarray or substring. A sliding window keeps a range [left, right], expands right to include elements, and contracts left when a constraint breaks. Each index enters and leaves once → O(n).

Fixed-size window

When the length k is given, slide it and update an aggregate in O(1) instead of recomputing:

def max_sum_k(nums, k):
    window = sum(nums[:k]); best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]   # add the new, drop the old
        best = max(best, window)
    return best

Used for fixed-window averages, “contains a duplicate within k,” and anagram-substring scans (slide a frequency window of the pattern’s length).

Variable-size window — longest (expand, then shrink to valid)

Grow right; when the window becomes invalid, shrink left until valid again; track the best width:

def longest_unique(s):
    seen, left, best = set(), 0, 0
    for right, c in enumerate(s):
        while c in seen:                  # shrink until the duplicate is gone
            seen.remove(s[left]); left += 1
        seen.add(c)
        best = max(best, right - left + 1)
    return best

“Longest substring without repeats,” “longest with at most K distinct” (keep a frequency map, shrink when distinct > K) are this shape.

Variable-size window — shortest (minimum window)

For “smallest window satisfying X,” expand to become valid, then shrink while still valid, recording the minimum:

def min_window(s, t):
    from collections import Counter
    need = Counter(t); missing = len(t)
    left = 0; best = (0, float("inf"))
    for right, c in enumerate(s):
        if need[c] > 0: missing -= 1
        need[c] -= 1
        while missing == 0:               # valid → try to shrink
            if right - left < best[1] - best[0]: best = (left, right)
            need[s[left]] += 1
            if need[s[left]] > 0: missing += 1
            left += 1
    return s[best[0]:best[1]+1] if best[1] < float("inf") else ""

The need/missing counters are the canonical “cover a target multiset” technique (“minimum window substring,” “smallest subarray with sum ≥ target”).

The “exactly K” trick

Counting subarrays with exactly K of something is awkward to window directly, but easy as a difference of “at most” windows:

exactly(K) = atMost(K) − atMost(K − 1)

atMost(K) is a standard shrinking window (shrink when the count exceeds K, add right − left + 1 subarrays each step). Solves “subarrays with K distinct integers,” “count nice subarrays” (K odd numbers), “binary subarrays with sum K.”

When the window breaks (important)

Sliding window needs the constraint to be monotonic as the window grows/shrinks. It fails when adding an element could help a violated constraint — classically, negative numbers break “subarray sum ≥ target” (extending might lower the sum back). For subarray-sum-equals-K with negatives, use a prefix-sum + hash map instead (its own primer). Knowing this boundary is a strong signal.

Signs it’s a sliding window

• “Longest / shortest / max / count contiguous subarray (or substring) such that …”
• A constraint you can incrementally add and remove (a sum, a count, a frequency map, a distinct-count).
• Often paired with a hash map for “at most K distinct / frequency” limits, or a monotonic deque for window min/max (see the stacks primer).

Pitfalls

• Forgetting to shrink (only expanding gives O(n²) or wrong answers).
• Using a window where the constraint isn’t monotonic (negatives → prefix sums).
• Off-by-one in window width right − left + 1.