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.

Function Contracts

max_sum_fixed_window(values, k) expects numeric values and a window size k with 1 <= k <= len(values). It returns the largest sum of any contiguous window of length k.

min_length_at_least(values, target) expects positive numbers. It returns the length of the shortest contiguous subarray whose sum is at least target, or 0 when none exists.

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.

Variable-Size Window

Some windows grow and shrink based on a condition:

def min_length_at_least(values, target):
    left = 0
    total = 0
    best = float("inf")
 
    for right, value in enumerate(values):
        total += value
 
        while total >= target:
            best = min(best, right - left + 1)
            total -= values[left]
            left += 1
 
    return best if best != float("inf") else 0

This version assumes values are positive. Positivity makes shrinking the window predictable.

Why It Works

A sliding window works when the answer changes locally as the range moves. Instead of recomputing the whole window, the algorithm updates the summary by adding the entering value and removing the leaving value.

For variable windows, the condition must tell when the left boundary can safely move.

Complexity

Each boundary moves forward at most n times, so many sliding-window algorithms are O(n).

Failure Example

The variable-size sum window assumes positive numbers. If negative numbers are allowed, shrinking the left side might increase the sum, and expanding the right side might decrease it.

Without predictable movement, the window rule no longer proves that candidates are safely discarded.

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.

Variable-size windows often fail when negative numbers are allowed, because expanding or shrinking no longer changes the sum in a predictable direction.

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.

Do not use it if the chosen range is not contiguous or if no safe rule exists for moving the left boundary.

The Main Point

Sliding window is for contiguous ranges whose summary can be updated as boundaries move. Variable windows need a condition that makes shrinking safe.