Sliding Window — a moving frame over the array

You look at a contiguous slice of the array or string. As you move to the right, you add the new element and subtract (or shrink until you can drop) the leftmost element. Turns many O(n·k) or O(n²) problems into O(n).

Two flavors

Fixed-size window

The window is always exactly k wide. Slide it right by 1. Update the aggregate incrementally.

• Max sum of k consecutive elements
• Average of every window of size k
• Number of window-of-size-k anagrams

Variable-size window

Grow the window until a condition breaks. Shrink from the left until it's valid again.

• Longest substring with unique characters
• Smallest subarray with sum ≥ target
• Longest substring with at most k distinct characters

The shape

lo = 0
for hi, x in enumerate(seq):
    # add x to the window
    while <window is invalid>:
        # remove seq[lo]
        lo += 1
    # window from lo..hi is valid — record answer

Common pitfalls

• Forgetting to update the answer inside the loop. Track the best while you go.
• Off-by-one on window length. hi - lo + 1 is the length when hi and lo are inclusive indices.
• Assuming the window can only grow. Some variants (min-sum with negatives) need both grow AND shrink.

Try it

1. Write min_subarray_len(target, nums) — smallest window whose sum is ≥ target.
2. Write longest_at_most_k_distinct(s, k) — longest substring with at most k distinct characters.