Sliding window: fixed size

What a window is

A window is a run of neighbouring items, described by where it starts and where it ends. A fixed-size window always holds exactly k items. Many questions ask about every window of size k: the best 7-day sales total, the average of every 24 hourly readings, or whether some stretch of a string is an anagram of a word. A list of n items has n − k + 1 windows of size k (when k ≤ n).

The slow way: recompute every window

Adding up k items for each of the n − k + 1 windows costs O(k) per window, so O(n × k) in total. With n = 100,000 days and k = 30 that is about 3 million additions; with k = 50,000 it is over a billion. sum(nums[i:i + k]) inside a loop is exactly this slow way, plus a copy of every slice.

The sliding trick

Two neighbouring windows share k − 1 items. When the window slides one step right, exactly one item enters (nums[i]) and one item leaves (nums[i − k]). So update the sum in O(1): window += nums[i] − nums[i − k]. Build the first window once, then slide. That is O(n) time in total and O(1) extra space.

def max_window_sum(nums, k):          # assumes 1 <= k <= len(nums)
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]    # one enters, one leaves
        best = max(best, window)
    return best

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))   # Output: 9

Averages over a window

A moving average (also called a rolling average) is the average of each window: window_sum / k. It smooths noisy data, which is why dashboards show 7-day averages of sales or 24-hour averages of air quality. When the data are integers, keep the running sum as an integer and divide only when you report, so small rounding errors do not build up. Round only the final values, for example round(avg, 2).

Windows of counts: anagram windows

A window can hold more than a sum. To count the windows of s that are anagrams of p (same characters, same counts), keep a count map of the current window of size len(p). When the window slides, add 1 for the entering character and subtract 1 for the leaving one. Compare the window's map with p's map at each step.

Delete a key when its count drops to 0. A plain dict that still holds a zero entry is not equal to one without that key, so equal windows would look different:

window = {"a": 1, "b": 0}
print(window == {"a": 1})    # Output: False  (the zero entry still counts)
del window["b"]
print(window == {"a": 1})    # Output: True

With a fixed alphabet, such as 26 lowercase letters, comparing two maps is O(26) = O(1), so the whole scan is O(n). A faster variant keeps a single number, "how many characters currently have the right count", and updates it as counts change.

Edge cases to settle first

• k larger than n: there is no window at all. Decide what to return (None, [] or 0) and say it.
• k = 0 or negative: usually invalid; handle it the same way.
• Empty input: same as k > n.
• Negative numbers are fine for fixed windows. The size is fixed, so you never have to decide when to shrink; that decision is what makes Topic 5 harder.

Common mistakes

• Recomputing sum(nums[i:i + k]) for every window: O(n × k). Fix: slide with one add and one subtract.
• Off-by-one in the leaving index. Fix: when nums[i] enters, nums[i − k] leaves; check it by hand with k = 1.
• Starting best at 0, which is wrong when every window sum is negative. Fix: start best at the first window's sum.
• Not handling k > len(nums): sum(nums[:k]) quietly sums a too-short list and returns a wrong answer. Fix: check k first.
• Leaving zero counts in a dict window, so equal windows compare unequal. Fix: delete keys that reach 0.