Sliding Window

What is it?

Maintain a window over a contiguous run of elements together with a summary of what it contains — a sum, a count, a frequency map. Extend the right edge to take in new elements; pull the left edge in when the window violates its condition. Because each edge only ever moves forward, every element is added once and removed at most once, turning a quadratic re-scan into a linear sweep.

The core idea

Template

The shape, not a solution. Adapt the condition and the state to the problem in front of you.

1def variable_window(items):2    """Grow on the right; shrink from the left while the window is invalid."""3    left = 04    best = 05    state = {}  # whatever summary the condition needs6 7    for right, value in enumerate(items):8        add(state, value)9 10        # 'while', not 'if': one new element can force several removals.11        while not is_valid(state):12            remove(state, items[left])13            left += 114 15        best = max(best, right - left + 1)16 17    return best18 19 20def fixed_window(items, k):21    """Window of constant width: add one, drop one."""22    if len(items) < k:23        return None24 25    total = sum(items[:k])26    best = total27    for right in range(k, len(items)):28        total += items[right] - items[right - k]29        best = max(best, total)30    return best

Common mistakes

• Using `if` instead of `while` when shrinking — a single new element can require removing several from the left.
• Measuring the window as `right - left` and losing one element; the width of an inclusive range is `right - left + 1`.
• Recording the best answer while the window is still invalid, before the shrink loop has run.
• Leaving zero counts in a frequency map, so a size check reports characters the window no longer contains.