Sliding Window

Sliding window is two pointers’ close cousin, specialised for contiguous sub-arrays and substrings. It’s one of the highest-frequency interview patterns, so learn both its forms well.

The idea

A brute force recomputes the sum (or state) of each sub-array from scratch — O(n·k). The window trick: as the window slides one step right, you add the element entering on the right and subtract the element leaving on the left. Each slide is O(1), so the whole scan is O(n). The window comes in two flavours.

Fixed-size window

The window is a constant size k. Compute the first window, then slide:

def max_sum_k(a, k):
    s = sum(a[:k])          # first window
    best = s
    for i in range(k, len(a)):
        s += a[i] - a[i-k]  # add entering, subtract leaving — O(1)
        best = max(best, s)
    return best
# max_sum_k([2,1,5,1,3,2], 3) -> 9

Variable-size window

Here the window grows and shrinks. The universal shape: expand the right edge each step; while a condition is violated, shrink from the left; track the best valid window. Example — longest substring without repeating characters:

def longest_unique(s):
    seen = {}            # char -> last index
    start = 0
    best = 0
    for i, c in enumerate(s):
        if c in seen and seen[c] >= start:
            start = seen[c] + 1     # jump the left edge past the repeat
        seen[c] = i
        best = max(best, i - start + 1)
    return best
# longest_unique("abcabcbb") -> 3  ("abc")

Worked example: minimum window substring

The harder variable-window problems grow the right edge until the window is valid, then shrink the left as much as possible while keeping it valid:

from collections import Counter
def min_window(s, t):
    need = Counter(t); missing = len(t)
    i = start = end = 0
    for j, c in enumerate(s, 1):
        if need[c] > 0: missing -= 1
        need[c] -= 1
        if missing == 0:                       # window has all of t
            while need[s[i]] < 0:              # shrink from the left
                need[s[i]] += 1; i += 1
            if end == 0 or j - i < end - start:
                start, end = i, j
    return s[start:end]
# min_window("ADOBECODEBANC", "ABC") -> "BANC"

Step-by-step walkthrough

Trace Longest Substring Without Repeating Characters on s = "abcabcbb". The right edge advances one character at a time; when a character repeats inside the window, the left edge jumps just past its previous position — it never moves backwards.

Each character enters the window once and the left edge only moves forward, so it is O(n). The longest valid window is 3 ("abc").

When to reach for it

Signals: the problem is about a contiguous sub-array or substring, and asks for the longest / shortest / maximum / minimum one satisfying some condition (“at most K distinct”, “sum ≥ target”, “no repeats”). If you catch yourself writing a nested loop that recomputes a sub-array each time — that’s the cue to switch to a window.

Pitfalls

• Non-contiguous problems. Sliding window needs contiguous elements. If the sub-sequence can skip elements, it’s a different pattern (often DP).
• Shrinking logic. In variable windows, be precise about when and how much to shrink the left edge — this is where bugs live. Write the invariant (“the window is always valid after the inner while”).
• Forgetting to update incrementally. If you recompute the window sum each step, you’ve lost the whole benefit — it’s O(n·k) again.

Recap

For contiguous sub-array / substring problems, maintain a moving window and update it incrementally (add entering, subtract leaving) for O(n). Fixed-size windows slide by k; variable-size windows grow the right edge and shrink the left when a condition breaks. Signal: contiguous + longest/shortest/at-most-K.

Practice: 12 solved problems on sliding window → — cover each one, solve it yourself, then check the tested code.

Next: Lesson 5 — Fast & Slow Pointers, for cycles and list middles.