Sliding window

A sliding window is a pair of indices [left, right] that together define a contiguous range — a "window" — into an array or string. The window slides across the input rather than restarting from scratch at every position, turning many O(n²) nested-loop problems into O(n) ones.

Fixed-size windows

When the window size is constant (size k), both pointers advance together. Add the incoming element on the right, remove the outgoing element on the left.

Canonical problem — maximum sum subarray of size k:

def max_sum_subarray(nums, k):
    window_sum = sum(nums[:k])
    best = window_sum
    for i in range(k, len(nums)):
        window_sum += nums[i] - nums[i - k]
        best = max(best, window_sum)
    return best

Each element enters and leaves the window exactly once: O(n). The naive approach sums k elements at every position: O(nk).

Variable-size windows

When the constraint is something like "at most k distinct characters" or "no repeating characters," the window size varies. The pattern is:

1. Expand right: advance right and incorporate s[right] into the window's state.
2. Shrink left while invalid: if the window now violates the constraint, advance left and remove s[left] from state until the window is valid again.
3. Record the answer for the current valid window.

s = "a b c b d e"
         L
               R

If the constraint is "no repeating chars" and R just hit 'b' (already at L+1),
shrink L past the first 'b' to restore validity.

Constraint as inequality: every variable window problem reduces to maintaining a condition like invalid_chars == 0 or distinct_count <= k. The shrink loop runs until that condition holds.

Recognising window problems

The structural tell-tale signs:

• The question asks for the longest or shortest contiguous subarray or substring satisfying some condition.
• The condition can be maintained incrementally — adding or removing one element updates it in O(1) or O(log n).
• The answer can be updated at each right-pointer position.

If you find yourself writing for i in range(n): for j in range(i, n):, stop and ask whether a window approach can eliminate the inner loop.

Where to go next

Next: sliding window practice — three concrete implementations: max sum subarray (fixed), longest substring without repeating characters (variable), and minimum window substring.