Mastering Sliding Window Patterns

The core idea: reuse the work

Suppose a problem asks for the best result among every contiguous block of length k. Computing each block independently examines up to k values each time, for roughly O(nk) work. A sliding window starts with the first block, then updates its state when it moves: remove the value leaving on the left and add the value entering on the right. Each item is handled a constant number of times, so the scan is O(n).

The “window” is usually represented by two indices, left and right. The state might be a running sum, a frequency table, a count of distinct values, or a maximum maintained by a deque. The key is to define precisely what the state means after every boundary change.

Fixed-size windows

For a known length, initialize the first window once and slide one position at a time. For example, this returns the largest sum of any k consecutive numbers:

def max_window_sum(nums, k):
    if k <= 0 or k > len(nums):
        raise ValueError("k must be between 1 and len(nums)")

    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]
        best = max(best, window)
    return best

Initialization costs O(k); the loop costs O(n-k), giving O(n) time and O(1) auxiliary space. The same pattern works for averages, counts of a property, and fixed-length substring frequencies.

Variable-size windows

When the valid range can grow and shrink, expand the right boundary and shrink from the left until a condition is restored. For nonnegative values, the shortest subarray with sum at least a target can be found this way:

def min_subarray_len(target, nums):
    left = 0
    total = 0
    best = len(nums) + 1

    for right, value in enumerate(nums):
        total += value
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1

    return 0 if best > len(nums) else best

The inner loop does not make this quadratic: left only moves forward and can cross each element once. Together both pointers perform O(n) total moves. This version relies on nonnegative values; with negative numbers, expanding the window no longer guarantees that its sum moves predictably.

When it works—and common mistakes

Sliding windows are strongest when the target is a contiguous range and the maintained state can be updated incrementally. For “longest substring without repeating characters,” track the most recent position of each character and jump the left boundary past duplicates. For “at most K distinct values,” maintain a frequency map and shrink until its size is at most K.

• Do not confuse contiguous subarrays with arbitrary subsequences.
• Prove that the shrink condition is safe; negative values often break sum-based assumptions.
• Be clear whether the result is the longest valid range, shortest valid range, or best fixed-size range.
• Check empty input, k at the boundaries, and whether the answer may be zero.