Sliding Window cheatsheet

🪟 Sliding Window

Contiguous subarray/substring + a rule: grow right, shrink left, each index enters and leaves once. O(n).

Recognize the pattern

Every window of exactly k consecutive items (max sum, average, count) → fixed window with a running total
Longest substring/subarray such that <rule> → variable window, shrink while invalid, record after
Shortest subarray such that <rule> → variable window, record and shrink while valid
Rule is about letter counts (anagram, cover, at most k distinct) → Counter or 26-slot list for the window
Count subarrays with exactly k of something → at_most(k) − at_most(k − 1)
Max/min of every window of size k → monotonic deque of indices
Subsequence, or sums with negative numbers → not a window: think DP or prefix sums

Fixed-size window

One loop: add the entering item, remove the one k behind, record once full.

Python template

def fixed_window(nums: list[int], k: int) -> int:
    window = 0
    best = float("-inf")
    for right in range(len(nums)):
        window += nums[right]          # enters
        if right >= k:
            window -= nums[right - k]  # leaves
        if right >= k - 1:             # window full
            best = max(best, window)
    return best

Longest valid window

Write down "the window is valid when…" first. Record after shrinking.

Python template

from collections import Counter

def longest(s: str, k: int) -> int:
    count = Counter()
    left = best = 0
    for right, ch in enumerate(s):
        count[ch] += 1                   # expand
        while len(count) > k:            # invalid
            count[s[left]] -= 1
            if count[s[left]] == 0:
                del count[s[left]]
            left += 1                    # shrink
        best = max(best, right - left + 1)
    return best

Shortest valid window

Needs monotonicity (e.g. all numbers ≥ 0). Record inside the shrink loop.

Python template

def shortest(nums: list[int], target: int) -> int:
    left = window = 0
    best = float("inf")
    for right, x in enumerate(nums):
        window += x                      # expand
        while window >= target:          # valid
            best = min(best, right - left + 1)
            window -= nums[left]         # shrink
            left += 1
    return 0 if best == float("inf") else best

Cover a target (need / have / formed)

Valid when every needed char is present often enough. formed changes only when a count crosses its requirement.

Python template

from collections import Counter

def min_cover(s: str, t: str) -> str:
    need = Counter(t)
    have = Counter()
    formed, left = 0, 0
    best = (float("inf"), 0, 0)
    for right, ch in enumerate(s):
        have[ch] += 1
        if have[ch] == need[ch]:
            formed += 1
        while formed == len(need):
            if right - left + 1 < best[0]:
                best = (right - left + 1, left, right)
            out = s[left]
            have[out] -= 1
            if have[out] < need[out]:
                formed -= 1
            left += 1
    size, lo, hi = best
    return "" if size == float("inf") else s[lo:hi + 1]

Exactly k = at most k − at most (k − 1)

Counting windows: every right adds right - left + 1 subarrays ending there.

Python template

def at_most(nums: list[int], k: int) -> int:
    count: dict[int, int] = {}
    left = total = 0
    for right, x in enumerate(nums):
        count[x] = count.get(x, 0) + 1
        while len(count) > k:
            y = nums[left]
            count[y] -= 1
            if count[y] == 0:
                del count[y]
            left += 1
        total += right - left + 1
    return total

def exactly(nums: list[int], k: int) -> int:
    return at_most(nums, k) - at_most(nums, k - 1)

Window maximum (monotonic deque)

Deque holds indices with decreasing values; the front is the max.

Python template

from collections import deque

def window_max(nums: list[int], k: int) -> list[int]:
    dq: deque[int] = deque()
    out = []
    for i, x in enumerate(nums):
        while dq and nums[dq[-1]] <= x:
            dq.pop()
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()
        if i >= k - 1:
            out.append(nums[dq[0]])
    return out

Operation costs

Operation	Time	Space
Fixed window over n items	O(n)	O(1)
Variable window (each index enters/leaves once)	O(n)	O(1) or O(alphabet)
Counter update / delete on slide	O(1)	O(distinct)
Compare two 26-slot count lists	O(26) = O(1)	—
Window max via monotonic deque	O(n) total	O(k)
Brute force: recompute every window	O(n·k) or O(n²)	—

Watch for

Window length is right - left + 1; the window of size k ending at right starts at right - k + 1.
Longest: record after the shrink loop. Shortest: record inside it. Swapping them gives wrong answers.
When len(counter) means "distinct in window", delete keys whose count drops to 0.
Sum-based shrinking needs non-negative numbers; with negatives use prefix sums or a deque.
Last-seen index jumps: use left = max(left, last[ch] + 1) so left never moves backwards ("abba").
Empty input, k > len(nums), and "no valid window" (return 0 / "" not infinity).