The Sliding Window Pattern

Most array and string problems have an obvious brute force: try every subarray. That is O(n²) subarrays, and often O(n) work to evaluate each, giving O(n³). The sliding window pattern collapses that to a single O(n) pass by noticing that consecutive subarrays overlap almost entirely.

In this article we will learn what the sliding window pattern is, how it eliminates redundant work, the difference between fixed-size and variable-size windows, how to recognise a sliding window problem from its wording, and the mistakes that quietly break the invariant.

What is the sliding window pattern?

The insight is that the window from index 1 to 4 shares three of its four elements with the window from 0 to 3. Recomputing the sum of all four throws that overlap away. Adding the incoming element and subtracting the outgoing one keeps it.

Why is the brute force so wasteful?

Take: find the maximum sum of any subarray of size k.

def max_sum_bruteforce(nums, k):
    best = float("-inf")
    for i in range(len(nums) - k + 1):
        window_sum = sum(nums[i:i + k])   # O(k) work, repeated every iteration
        best = max(best, window_sum)
    return best

This is O(n × k). Each sum() call re-adds k - 1 numbers that were already added by the previous iteration.

How does a fixed-size window fix it?

Slide the window one position at a time, adjusting the running total:

def max_sum_sliding(nums, k):
    if len(nums) < k:
        return None
 
    window_sum = sum(nums[:k])   # build the first window once
    best = window_sum
 
    for right in range(k, len(nums)):
        window_sum += nums[right]        # element enters on the right
        window_sum -= nums[right - k]    # element leaves on the left
        best = max(best, window_sum)
 
    return best

O(n) time, O(1) space. Every element is added exactly once and subtracted exactly once.

The shape generalises:

Build the first window
For each new right index:
    Add the incoming element
    Remove the outgoing element
    Update the answer

What about variable-size windows?

When the window size is not given but implied by a condition — "the longest substring with at most k distinct characters" — the right pointer expands the window and the left pointer contracts it whenever the condition breaks.

def longest_substring_k_distinct(s, k):
    counts = {}
    left = 0
    best = 0
 
    for right, char in enumerate(s):
        counts[char] = counts.get(char, 0) + 1
 
        # Shrink from the left until the window is valid again
        while len(counts) > k:
            left_char = s[left]
            counts[left_char] -= 1
            if counts[left_char] == 0:
                del counts[left_char]
            left += 1
 
        best = max(best, right - left + 1)
 
    return best

The inner while loop looks like it makes this quadratic. It does not. left only ever moves forward, and it can move at most n times in total across the entire run. Both pointers traverse the array once, so the whole function is O(n).

Fixed vs variable windows

How do you recognise one?

The wording gives it away. Look for all three:

1. The problem concerns a contiguous subarray or substring. If reordering or skipping elements is allowed, this is not a window problem.
2. It asks for a longest, shortest, maximum, minimum or count.
3. There is a condition the window must satisfy — a size, a sum, a distinct-character limit.

If the array contains negative numbers and the condition involves a sum threshold, be careful: the sum is no longer monotonic as the window grows, so the standard shrink rule breaks. Prefix sums with a hash map is usually the right pattern there instead.

Common mistakes

• Updating the answer before restoring validity. In a variable window, measure right - left + 1 only after the while loop has finished shrinking.
• Off-by-one in the outgoing index. For a fixed window ending at right, the element leaving is right - k, not right - k + 1.
• Forgetting to delete zero counts. If you track distinct characters with a hash map, a key with count 0 still counts toward len(counts) until you remove it.
• Using a window on non-contiguous problems. "Any subsequence" is not a window problem.
• Assuming shrinking always helps with negative numbers. Removing a negative element increases the sum.

Conclusion

The sliding window pattern turns repeated evaluation of overlapping ranges into a single pass by adding the element that enters and removing the element that leaves. Fixed-size windows move both pointers in lockstep; variable-size windows expand on the right and contract on the left only when a condition is violated.

The pattern applies whenever a problem asks for an optimal contiguous segment subject to a constraint, and it reliably converts an O(n²) brute force into O(n).

If the complexity argument in the variable-size section was not obvious, time and space complexity explained covers the amortised reasoning it depends on.