Fixed-size sliding window — LeetCode patterns

Problem

"Largest sum of k consecutive numbers", "does any substring of length k match this pattern", "any repeat within k positions": each asks about all windows of one fixed width. Recomputing a window from scratch costs O(k), so n windows cost O(n·k). Neighbouring windows share k − 1 items, and the summary can be updated instead of rebuilt.

Signal	Pattern	Why
"Maximum (or average) of every k consecutive elements"	Running sum	Add the entering value, subtract the leaving one.
"Does a permutation or anagram of p occur in s?"	Window of len(p) with a count map	An anagram has the same letter counts as p, and counts update in O(1).
"Two equal values within distance k"	Set holding the last k values	Evicting the value that falls out keeps the set equal to the window.
"Max or min of every window of size k"	Window plus a monotonic deque	A running sum cannot undo a max, so a deque keeps candidates in order.
"Events in the last 300 seconds"	Queue evicted by time	The window is defined by a time span rather than a count, which makes it a queue problem.
Circular array, windows that wrap	Index modulo n, or double the array	Wrapping adds no new idea, only a different way to index.

Intuition

Think of a train passing a platform that fits exactly k carriages. Every tick, one carriage steps onto the platform and one steps off. To know the total weight on the platform you do not re-weigh the whole platform; you add the arriving carriage and subtract the departing one. The only requirement is that the summary is reversible: it must be possible to remove an item as cheaply as adding it. Sums, counts and sets are. Maximums are not.

One row per window position, sums 8, 7, 9, 6, 14, 12. Blue is the window; green marks the best one.

Mechanics

The invariant

After processing index right, the summary describes exactly nums[right − k + 1 .. right]. Each iteration performs two updates in a fixed order: fold in nums[right], then, once the window has overgrown (right ≥ k), remove nums[right − k]. After that the window has size k again. Results are read only from right ≥ k − 1, when the first full window exists. Because the update is the exact inverse of the addition, the summary never drifts away from the window's true contents.

The mismatch counter for anagrams

To test "window letter counts equal pattern letter counts" you do not compare two maps on every step, which would cost O(26) or O(k). Store for each letter the difference window − pattern, and keep one integer: how many letters have a non-zero difference. Adding or removing a letter changes one entry, and the integer changes only when that entry crosses zero. The window is an anagram exactly when the integer is 0. Each step is O(1).

Near-duplicates with a set

Keep a set of the last k values. For each new value, check the set first (a hit means a repeat within distance k), then add it, then evict the value that is now k positions behind. The order matters: if you evict before checking, you shrink the window to k − 1 and miss repeats at exactly distance k.

Bar height is how many letters still differ from the pattern. Green means zero: an anagram.

Worked example

Best sum of 3 in [2, 1, 5, 1, 3, 2, 9, 1]. Each row adds the entering value and subtracts the leaving one.

Window	Entering	Leaving	Sum	Best
[0..2]	5	–	8	8
[1..3]	1	2	7	8
[2..4]	3	1	9	9
[3..5]	2	5	6	9
[4..6]	9	1	14	14
[5..7]	1	3	12	14

The best is 14, found with 6 constant-time updates instead of 18 additions.

Anagrams of "abc" in cbaebabacd:

Start	Window	Letters still differing
0	cba	0
1	bae	2
2	aeb	2
3	eba	2
4	bab	2
5	aba	2
6	bac	0
7	acd	2

The counter reaches zero at starts 0 and 6.

Near duplicates in [4, 7, 9, 4, 2] with k = 3:

Index	Value	Set before	Repeat?
0	4	[]	no
1	7	[4]	no
2	9	[4, 7]	no
3	4	[4, 7, 9]	yes

The repeat is found at index 3, exactly 3 positions after the first 4.

Implementation

from collections import Counter


def best_window_sum(nums, k):
    total = sum(nums[:k])
    best = total
    for right in range(k, len(nums)):
        total += nums[right] - nums[right - k]      # enter, leave
        best = max(best, total)
    return best


def anagram_starts(text, pattern):
    k = len(pattern)
    if k > len(text):
        return []
    diff = Counter(text[:k])
    diff.subtract(Counter(pattern))
    differing = sum(1 for v in diff.values() if v)
    starts = [0] if differing == 0 else []
    for right in range(k, len(text)):
        for ch, change in ((text[right], 1), (text[right - k], -1)):
            before = diff[ch]
            diff[ch] += change
            differing += (diff[ch] != 0) - (before != 0)
        if differing == 0:
            starts.append(right - k + 1)
    return starts


def contains_nearby_duplicate(nums, k):
    window = set()
    for i, x in enumerate(nums):
        if x in window:
            return True
        window.add(x)
        if len(window) > k:
            window.remove(nums[i - k])
    return False

Variations and edge cases

Count-based mismatch vs. map equality. Comparing two small Counters every step is simpler and fine for an alphabet of 26; the mismatch counter is the version that is O(1) per step regardless of alphabet.
Window maximum. A sum is reversible but a max is not: removing the leaving item may expose a new maximum. Keep a deque of indices with decreasing values (see monotonic stack).
Time-based windows. A hit counter or rate limiter is a window defined by time, not count; use a queue and pop entries older than the cutoff before reading the size.
Binary arrays and flips. Fixed windows over 0/1 data count ones with a running sum, e.g. minimum swaps to group all ones together is the best window of size (number of ones).
Edge cases: k larger than the array (return early), k = 1, k = 0, negative numbers (fine for fixed windows, unlike variable ones), reading results before the first full window, and evicting before checking in the set version.

Complexity and tradeoffs

Time: O(n) updates, each O(1); the anagram version is O(n + alphabet) to set up.
Space: O(1) for sums, O(alphabet) for letter counts, O(k) for the set.
Baseline. Recomputing each window is O(n·k). For small k the difference is invisible; for k close to n/2 it is the difference between a second and a millisecond.
When it fails. The summary must be reversible. If the window size is not fixed but defined by a condition, use a variable-size window; if you need the max or min, add a deque; if you need arbitrary range queries, use prefix sums.

Problems

The home problems all slide a window of a width known up front: a pattern length or a given k. The "also uses" list adds the window maximum, whose twist is the deque.

Easy

219. Contains Duplicate II NeetCode 250
Keep a set of the last k values; a new value already in that set is a near duplicate.

Medium

362. Design Hit Counter Grind 169
Keep timestamps in a queue and pop everything older than 300 seconds before answering.
438. Find All Anagrams in a String Grind 169
Slide a window as long as the pattern and compare the letter counts inside it with the pattern's counts.
567. Permutation in String NeetCode 150 NeetCode 250
Slide a window the length of the pattern and check whether its letter counts match.

Also uses this pattern

These problems have a different home page, but this idea is part of their solution.

239. Sliding Window Maximum Hard

Connections

Read first

Two pointers intro

Check yourself

Why does the running-sum window update need both an addition and a subtraction?

After adding the entering value the window holds k + 1 items; removing the leaving one restores size k, and the sum equals the window's contents exactly. The trace needed 6 such updates.

How does the mismatch counter let you test an anagram in O(1)?

It counts how many letters have different counts in the window and the pattern. Each added or removed letter changes one count and moves the counter only when that count crosses zero, so equality is the single test "counter == 0". It is zero at starts 0 and 6 in the example.

Why can a sliding-window maximum not be done with just a running value?

Subtraction undoes a sum, but nothing undoes a max: when the largest item leaves, the new maximum is somewhere among the remaining items and was not recorded. A deque of candidates in decreasing order keeps that information.

References

Cormen, Leiserson, Rivest and Stein, Introduction to Algorithms: chapter 17 on amortized analysis (3rd edition), the accounting behind constant-time incremental updates.
Sedgewick and Wayne, Algorithms: section 5.3 on substring search, where the window over the text is the central object (Rabin-Karp updates a rolling hash exactly this way).
Steven Skiena, The Algorithm Design Manual: the sections on string matching.
Karp and Rabin, "Efficient randomized pattern-matching algorithms" (1987), the rolling-hash window.
The NeetCode roadmap and the Blind 75, Grind 169, NeetCode 150 and NeetCode 250 lists, used as the index of topics and problems.