Sliding Window Technique: Fixed and Variable Windows

Quick Answer

Sliding window solves problems about contiguous subarrays or substrings by keeping a moving range instead of recomputing from scratch. A fixed window of size k slides one step at a time, adding the new element and removing the old one, which turns O(n times k) into O(n). A variable window grows until a condition breaks, then shrinks from the left until it holds again, which finds longest or shortest ranges in O(n). It relies on extending the window changing the result predictably, so negative numbers break the sum-based version.

The Idea: Stop Recomputing

Given an array, find the maximum sum of any k consecutive elements. The naive version sums every window from scratch.

def max_sum_brute(arr, k):
    best = float('-inf')
    for i in range(len(arr) - k + 1):
        best = max(best, sum(arr[i:i+k]))   # re-adds k values every time
    return best

That is O(n times k), and almost all of the work is repeated. Consecutive windows overlap in all but two positions.

arr = [2, 1, 5, 1, 3, 2],  k = 3

window 1: [2, 1, 5]        sum = 8
window 2:    [1, 5, 1]     sum = 8 - 2 + 1 = 7    <- reuse, don't re-add
window 3:       [5, 1, 3]  sum = 7 - 1 + 3 = 9

Each slide removes the element leaving and adds the one entering. Two operations instead of k.

def max_sum(arr, k):
    window = sum(arr[:k])
    best = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]   # add entering, drop leaving
        best = max(best, window)
    return best

O(n) time, O(1) space. The whole technique is that one insight: carry the previous answer forward rather than rebuilding it.

Fixed Windows

Use a fixed window when the size is given in the question — "subarray of size k", "average of every k days", "any k consecutive".

The template is always the same. Build the first window, then for each new element add it and remove the one that fell out of range.

Maximum average of k elements is the sum version divided by k; do not divide inside the loop, it only adds work.

Count anagrams of a pattern in a string uses a window of the pattern's length holding character counts. Slide by incrementing the entering character and decrementing the leaving one, then compare count maps.

The off-by-one that catches everyone: the element leaving the window is at index i - k, not i - k + 1. When i is the index entering, the window covers i-k+1 through i, so the one that just left is i-k. Getting this wrong produces answers that are subtly close but wrong, which is far harder to debug than a crash.

Variable Windows: Grow, Then Shrink

Most interview questions use the variable form, where the size is what you are solving for: "longest substring without repeating characters", "smallest subarray with sum at least S".

The structure is a right pointer that always advances, and a left pointer that catches up only when a condition is violated.

def longest_unique_substring(s):
    seen = {}
    left = 0
    best = 0
    for right, ch in enumerate(s):
        # the condition broke: shrink from the left until it holds again
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

Note that left never moves backwards. Each pointer travels the string at most once, which is why this is O(n) even though there are two nested-looking movements.

The shortest-range variant shrinks greedily while the condition still holds, recording the answer each time:

def min_subarray_len(target, arr):
    left = 0
    total = 0
    best = float('inf')
    for right, x in enumerate(arr):
        total += x
        while total >= target:          # still valid: try to shrink
            best = min(best, right - left + 1)
            total -= arr[left]
            left += 1
    return 0 if best == float('inf') else best

The difference between the two shapes is when you record the answer. For a longest window, record after restoring validity. For a shortest one, record while it is still valid, just before shrinking further.

The Trap: Negative Numbers

This is the single most common wrong answer in sliding window problems, and it is worth internalising.

The variable-window sum pattern assumes that extending the window increases the sum and shrinking it decreases the sum. That is what makes it safe to stop shrinking once the condition fails: nothing further left could help.

With negative numbers that assumption is false. Adding an element might reduce the sum, so a window that currently fails could start working again after extending it further. The greedy shrink throws away valid answers.

arr = [3, -2, 4],  target sum = 5

Sliding window: [3] = 3, too small. [3,-2] = 1, still small.
                [3,-2,4] = 5 — found, but only by luck of ordering.
On other inputs the shrink step discards the window that would have worked.

For subarray-sum problems that allow negatives, use prefix sums with a hash map instead. Store each running total and look up whether running - target has been seen; that finds subarrays summing to a target in O(n) regardless of sign.

So before applying a sliding window to a sum question, check the constraints for "all positive". If they do not say it, the pattern may be the wrong tool.

Recognising It in a Question

The signals are consistent enough to be a checklist.

• The question says contiguous, consecutive, subarray or substring. If elements may be skipped, it is not a window — that is usually dynamic programming.
• It asks for a longest, shortest, maximum or minimum range satisfying some property.
• A brute-force solution would try every start and end, giving O(n squared) — and the constraints make that too slow.
• The property can be updated incrementally as elements enter and leave. Sums, counts and character frequencies all qualify. Something requiring a full re-sort of the window does not.

That last point is the real boundary. Sliding window is fast because updating the window is O(1). If maintaining your condition costs O(k) per step, you have rebuilt the brute force with extra bookkeeping. Problems like "maximum in every window" need a monotonic deque precisely because a plain max cannot be updated in O(1) when the maximum is the element leaving.

Frequently Asked Questions