Sliding Window, Fixed Length

The question

You are given a list of numbers and a size k. Find the biggest sum of any k numbers that sit next to each other.

Explain it to a ten-year-old

Ten children in a row, each holding some sweets. You want the three neighbours holding the most sweets between them. The slow way: count every group of three from scratch. The fast way: count the first three once. Then step right. One child leaves the group on the left, one joins on the right. Take away what the leaver had, add what the joiner has. You never count more than two children per step.

The trick

The window never changes size, so the only things that change when it moves are one element in and one element out. Keep a running total. Each step: add the newcomer, subtract the leaver, compare. Whatever you are tracking, a sum, a count of vowels, a map of letter frequencies, gets the same two updates.

The brute force recounts k items at each of n positions, so n × k. The window touches each item twice, once in and once out, so n.

The steps

1. Sum the first k items. That is the window and the best so far.
2. For each index i from k to the end:
   • window += a[i], the one coming in.
   • window -= a[i - k], the one going out.
   • best = max(best, window).
3. Return best.

def max_sum_k(a, k):
    window = sum(a[:k])
    best = window
    for i in range(k, len(a)):
        window += a[i] - a[i - k]
        best = max(best, window)
    return best

Time O(n). Space O(1).

The same shape with a frequency map, for “does any window of s contain the same letters as p”:

from collections import Counter

def has_anagram(s, p):
    k = len(p)
    need, window = Counter(p), Counter(s[:k])
    if window == need:
        return True
    for i in range(k, len(s)):
        window[s[i]] += 1
        window[s[i - k]] -= 1
        if window[s[i - k]] == 0:
            del window[s[i - k]]
        if window == need:
            return True
    return False

The template

This is the reason patterns are worth learning. Someone worked out the sliding window shape once, and every fixed-window problem since is the same eight lines with three small pieces swapped. Memorise the shape. Understand why each line is there. Then a problem you have not seen is one you have.

state = INIT                       # STATE: a sum, a count, a Counter, a set. Add and remove in O(1)
start = 0
best = NONE
for end in range(len(a)):
    ADD(state, a[end])             # extend: the newcomer at the right edge
    if end - start + 1 == k:       # the window is exactly k wide
        best = EVALUATE(state, best)   # look at the window once
        REMOVE(state, a[start])    # contract: the leaver at the left edge
        start += 1

The capitals are the parts that change. For the max sum above, state is a number, add is +=, remove is -=, evaluate is max. For anagrams, state is a Counter, add and remove change one count, evaluate compares two Counters. For “any repeat within k”, state is a set, evaluate is “was the newcomer already in it”. The shape never moves.

The snippet in the steps above is the same template with start folded away as i - k. Use whichever you can write without thinking. The reason to understand the shape rather than just memorise it is the moment the interviewer says “longest” instead of “exactly k”. The loop is the same, but the if becomes a while and the left edge moves only when the window breaks a rule. If you know why the fixed version works, that change is obvious. If you memorised it, it is a new problem.

In GPU infrastructure

Every health dashboard I have built is a fixed window. Average NCCL all-reduce time over the last sixty samples per node, and the node whose window sits above the fleet’s is your straggler. Count of XID errors in the last fifteen minutes, and the node that crosses a threshold gets drained. Both are one in, one out, with a sum or a count as the state. The moment someone asks for “the longest stretch with no errors”, the window is no longer fixed and you are on the next rung.

What I am listening for

• Whether you say “n times k” for the brute force and then see that the window overlaps. The overlap is the whole insight.
• Whether the out-going index is i - k. Off by one here is the most common bug in the room.
• Whether the state you keep supports add and remove in constant time. A sum does. A counter does. A sorted list does not, and that is when you need the monotonic deque.
• Whether you can tell me when the window is fixed and when it is not. “Exactly k” is this lesson. “Longest” or “shortest” is a different pattern with two pointers that move independently.

Where it leads

Fixed window, same trick with a different state:

• Maximum Average Subarray I. The problem above, divided by k.
• Contains Duplicate II. A set of the last k items.
• Maximum Number of Vowels in a Substring of Given Length. A count instead of a sum.
• Find All Anagrams in a String and Permutation in String. A letter counter, as in the second snippet.
• Maximum Points You Can Obtain from Cards. Take from both ends, which is a fixed window over the middle, flipped.
• Maximum Sum of Distinct Subarrays With Length K. Sum plus a counter at the same time.
• Sliding Window Maximum. When the state is “the biggest item”, the running total is not enough.

Variable window, the next rung:

• Longest Substring Without Repeating Characters and Minimum Size Subarray Sum. The right edge always moves, the left edge moves only when the window breaks a rule.

Go deeper

• Fixed-length sliding window on Hello Interview. The template above is theirs, and the page has the variable-length version next to it.
• Sliding window problems on LeetCode, the tag page. Do the easy ones in one sitting.
• NeetCode’s roadmap has a sliding window branch with a video per problem. The NeetCode channel is where the videos live.
• Sliding window on LeetCode’s explore cards if you prefer the guided form.

With AI on the table. The assistant writes the sum version perfectly. I ask it to find the window with the most distinct values instead, then I ask you why the code it produced is now slower than it should be. Usually it rebuilt a set every step. Spotting that is the job.