Data Structures & Algorithms Cheatsheet

Sliding Window

Use this Data Structures & Algorithms reference while you build software engineering projects, review code, or refresh the syntax you reach for most.

When To Reach For This

A window is a contiguous range [left, right] that grows on the right and shrinks on the left. Both pointers only move forward, so the pass is O(n) even though the inner while looks nested.

Signals in a problem statement:

The words subarray, substring, or contiguous. If the problem allows skipping elements it is not a window, it is DP or a subsequence problem.
"Longest" or "shortest" range satisfying a condition, or "count the subarrays" that satisfy one.
A fixed size k is given ("every window of size k", "average of k consecutive").
A constraint that is monotone in window size: once the window is invalid, growing it further keeps it invalid. Distinct-character counts, sums of positive numbers, and frequency caps all qualify.
Asked to do it in one pass with O(1) or O(k) extra space.

Classic problems it solves:

Longest Substring Without Repeating Characters
Minimum Window Substring
Longest Repeating Character Replacement
Maximum Average Subarray I (fixed size)
Permutation in String and Find All Anagrams in a String
Fruit Into Baskets (at most k distinct)
Sliding Window Maximum (monotonic deque variant)
Minimum Size Subarray Sum

Negative numbers break the sum-based window, because shrinking no longer reliably lowers the sum. Use prefix sums with a hash map instead.

Complexity

Variant	Time	Space
fixed size k, running aggregate	O(n)	O(1)
variable size, longest valid	O(n)	O(k) for the counter
variable size, shortest valid	O(n)	O(k)
count subarrays with at most k	O(n)	O(k)
window max or min via monotonic deque	O(n)	O(k)
naive all subarrays (the baseline you beat)	O(n²)	O(1)

Each of left and right advances at most n times, so the total pointer movement is bounded by 2n regardless of how the inner loop nests.

Fixed Size Window

Add the entering element, remove the leaving element, never recompute the whole window.

def max_sum_k(a, k):
    """Max sum of any k consecutive elements. O(n)."""
    total = sum(a[:k])
    best = total
    for r in range(k, len(a)):
        total += a[r] - a[r - k]
        best = max(best, total)
    return best

def find_anagrams(s, p):
    """All start indices where a permutation of p occurs in s."""
    from collections import Counter
    need, win = Counter(p), Counter()
    k, out = len(p), []
    for r, ch in enumerate(s):
        win[ch] += 1
        if r >= k:
            drop = s[r - k]
            win[drop] -= 1
            if win[drop] == 0:
                del win[drop]        # keep the dict clean so == works
        if win == need:
            out.append(r - k + 1)
    return out

Variable Window, Longest Valid

Grow right always. Shrink left only while the window is invalid. Record the answer after the window is valid again.

def longest_unique(s):
    """Longest Substring Without Repeating Characters."""
    last = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in last and last[ch] >= left:
            left = last[ch] + 1      # jump past the previous copy
        last[ch] = right
        best = max(best, right - left + 1)
    return best

def at_most_k_distinct(s, k):
    """Longest substring with at most k distinct characters."""
    from collections import defaultdict
    cnt = defaultdict(int)
    left = best = 0
    for right, ch in enumerate(s):
        cnt[ch] += 1
        while len(cnt) > k:
            cnt[s[left]] -= 1
            if cnt[s[left]] == 0:
                del cnt[s[left]]
            left += 1
        best = max(best, right - left + 1)
    return best

def char_replacement(s, k):
    """Longest Repeating Character Replacement. Window is valid when
    size - most_frequent_count <= k."""
    cnt = [0] * 26
    left = best = top = 0
    for right, ch in enumerate(s):
        i = ord(ch) - 65
        cnt[i] += 1
        top = max(top, cnt[i])
        while (right - left + 1) - top > k:
            cnt[ord(s[left]) - 65] -= 1
            left += 1
        best = max(best, right - left + 1)
    return best

Variable Window, Shortest Valid

Mirror image: shrink while the window is valid, and record before shrinking.

def min_subarray_len(target, a):
    """Shortest subarray with sum >= target. Positives only. 0 if none."""
    left = total = 0
    best = float("inf")
    for right, x in enumerate(a):
        total += x
        while total >= target:
            best = min(best, right - left + 1)
            total -= a[left]
            left += 1
    return 0 if best == float("inf") else best

def min_window(s, t):
    """Minimum Window Substring. O(len(s) + len(t))."""
    from collections import Counter
    need = Counter(t)
    missing = len(t)
    best = (0, 0)
    left = 0
    for right, ch in enumerate(s, 1):     # right is a 1-based end
        if need[ch] > 0:
            missing -= 1
        need[ch] -= 1
        if missing == 0:
            while need[s[left]] < 0:      # trim useless left chars
                need[s[left]] += 1
                left += 1
            if best == (0, 0) or right - left < best[1] - best[0]:
                best = (left, right)
    return s[best[0]:best[1]]

Counting Subarrays

"Exactly k" is rarely computable directly. Compute at most k and subtract.

def subarrays_at_most_k_distinct(a, k):
    from collections import defaultdict
    cnt = defaultdict(int)
    left = ans = 0
    for right, x in enumerate(a):
        cnt[x] += 1
        while len(cnt) > k:
            cnt[a[left]] -= 1
            if cnt[a[left]] == 0:
                del cnt[a[left]]
            left += 1
        ans += right - left + 1     # every window ending at right
    return ans

def subarrays_exactly_k_distinct(a, k):
    return (subarrays_at_most_k_distinct(a, k)
            - subarrays_at_most_k_distinct(a, k - 1))

ans += right - left + 1 is the counting idiom: if [left, right] is valid, every suffix of it ending at right is valid too.

Monotonic Deque For Window Max

A plain window cannot track its maximum in O(1) because the max may leave. A deque holding indices in decreasing value order can.

from collections import deque

def max_sliding_window(a, k):
    """Sliding Window Maximum. O(n) time, O(k) space."""
    dq = deque()          # indices, values decreasing front to back
    out = []
    for i, x in enumerate(a):
        while dq and a[dq[-1]] <= x:
            dq.pop()                    # x dominates everything smaller
        dq.append(i)
        if dq[0] <= i - k:
            dq.popleft()                # front fell out of the window
        if i >= k - 1:
            out.append(a[dq[0]])
    return out

// Java: ArrayDeque of indices, identical logic
Deque<Integer> dq = new ArrayDeque<>();
int[] out = new int[a.length - k + 1];
for (int i = 0; i < a.length; i++) {
    while (!dq.isEmpty() && a[dq.peekLast()] <= a[i]) dq.pollLast();
    dq.addLast(i);
    if (dq.peekFirst() <= i - k) dq.pollFirst();
    if (i >= k - 1) out[i - k + 1] = a[dq.peekFirst()];
}

Gotchas

Delete zero-count keys. Comparing Counter objects or calling len(cnt) for the distinct count is wrong if stale zero entries linger.
Record the answer in the right place. Longest: after the shrink loop. Shortest: inside it.
Negative numbers. A sum window needs all non-negative values. Otherwise use prefix sums plus a hash map, or a monotonic deque on prefix sums.
while not if on the shrink. One entering element can force several removals.
Fixed-size windows evict exactly one element per step, so use if r >= k, not a while.
Empty and short inputs. Guard k > len(a) and empty strings before indexing a[:k].
"Subsequence" is not a window. Non-contiguous selection needs DP, not two pointers.