Sliding Window

Sliding window maintains information about a contiguous range as that range moves through an array or string.

It avoids recomputing the same information from scratch for every possible range.

Core Idea

The algorithm expands the window by moving the right boundary and shrinks it by moving the left boundary. While the window changes, it updates a running count, sum, set, or other summary.

This is useful when the answer depends on a contiguous subarray or substring.

Python Example

def max_sum_fixed_window(values, k):
    window_sum = sum(values[:k])
    best = window_sum
 
    for right in range(k, len(values)):
        window_sum += values[right]
        window_sum -= values[right - k]
        best = max(best, window_sum)
 
    return best

The window sum is updated by adding one new value and removing one old value.

Common Confusions

Sliding window only applies to contiguous ranges. It is not for arbitrary subsets.

Fixed-size windows and variable-size windows have different movement rules. Variable-size windows need a condition that tells when to shrink.

When To Use It

Use sliding window for subarray or substring problems involving sums, counts, distinct characters, maximum length, minimum length, or moving range constraints.