Sliding Window: The "Worm" Technique

What Problem Does It Solve?

Imagine you are reading a book and someone asks: "What is the most interesting 3-page stretch?" You wouldn't re-read from page 1 every time you move forward — you'd slide your bookmark one page at a time, dropping the page you left behind and picking up the new one ahead. That is exactly what the Sliding Window technique does with arrays and strings.

Use Sliding Window whenever a problem asks about a contiguous subarray or substring — a chunk of consecutive elements — and you need to find a maximum, minimum, or condition across all such chunks.

The Brute Force Problem ($O(N^2)$)

Consider: "Find the maximum sum of any 3 consecutive numbers in [2, 1, 5, 1, 3, 2]."

The naive approach uses a nested loop:
- Start at index 0: sum(2, 1, 5) = 8
- Start at index 1: sum(1, 5, 1) = 7
- Start at index 2: sum(5, 1, 3) = 9
- ...

Notice that moving from index 0 to index 1, you re-add 1 and 5 even though they were already summed. For large arrays, this redundancy is expensive.

The Sliding Window Mechanism ($O(N)$)

Instead of recalculating from scratch, maintain a running sum and update it incrementally:

1. Initialize: Compute the sum of the first window: sum([2, 1, 5]) = 8.
2. Slide: To advance the window by one position:
3. Subtract the element leaving on the left: 8 - 2 = 6
4. Add the element entering on the right: 6 + 1 = 7
5. Track: Keep a max_sum variable updated at each step.

def max_sum_subarray(arr, k):
    window_sum = sum(arr[:k])   # Initialize first window
    max_sum = window_sum

    for i in range(len(arr) - k):
        window_sum = window_sum - arr[i] + arr[i + k]  # Slide
        max_sum = max(max_sum, window_sum)

    return max_sum

# Example
print(max_sum_subarray([2, 1, 5, 1, 3, 2], 3))  # Output: 9

Fixed vs. Variable Windows

The example above uses a fixed-size window (always exactly k elements). Many harder problems use a variable-size window where you expand the right pointer freely and shrink the left pointer when a constraint is violated (e.g., "longest substring with at most 2 distinct characters"). The core mechanic — expand right, shrink left, track a running state — is identical.