Fixed-Size Window · bigonotes

A sliding window is a pair of pointers, start and end, that marks a contiguous run of an array or string. Reach for it whenever a problem asks about contiguous subarrays or substrings. This note covers the simplest version, where the window always holds exactly k items. Each step you add the item that enters and remove the one that leaves, and that's all the work there is.

The idea#

In a fixed window, start moves automatically to keep the window exactly k wide. You never shrink because of the values inside (sum too big, too many zeros). You shrink because of the index. That one rule is what separates it from the variable windows in the rest of this category:

Window type	When does `start` move?
Fixed	"Is the index too far?" Always, once the window passes size `k`
Variable	"Is the window invalid?" Only when a rule is broken

With that rule in place, every step has three parts:

Grow: add nums[i] to the window state (sum, count, map).
Trim: once i >= k, remove nums[i - k], the item that just fell off the left.
Process: once i >= k - 1, the window is exactly size k, so update the answer.

Why does this work? Consecutive windows share k - 1 items. Recomputing each window from scratch costs $O(nk)$ . Updating only the two edges costs $O(1)$ per step, so $O(n)$ total.

How to spot it#

The problem tells you the window size, or the size follows from the input.

"Subarray / substring of length k", "every k consecutive", "k minutes in a row".
An answer per window: max sum, average, count of vowels, number of distinct items.
A pattern to match whose length is fixed, like an anagram of p (window size len(p)).
A rotation of a string: every rotation is a window of length n in s + s.

Template#

In the trace below the window state is a running sum. Swap it for a counter or a dict and the shape stays the same.

state = empty                       # sum, count or map
best = worst possible value
for i in range(len(items)):
    add items[i] to state           # grow: items[i] enters
    if i >= k:
        remove items[i - k]         # index too far: it leaves
    if i >= k - 1:                  # from here on the size is exactly k
        best = better of best and the answer for state
return best

To see the three parts in action, here is the trace for a running sum with nums = [2, 1, 5, 1, 3, 2] and k = 3.

`i`	enters	leaves	window	best
0	2		2	not yet size 3
1	1		3	not yet size 3
2	5		8	8
3	1	2	7	8
4	3	1	9	9
5	2	5	6	9

Pitfalls#

The template is short, but small slips in it give wrong windows. Watch for these.

Processing too early. The window is not full until i == k - 1. Updating the answer before that compares partial windows.
Removing the wrong item. In the index-based template the leaving item is nums[i - k]. If you keep an explicit start instead, remove nums[start] and then do start += 1. Don't mix the two styles.
Stale keys in a frequency map. Decrementing a count to zero leaves the key in the dict, so len(freq) overcounts. Delete it.
Off-by-one in the size check. The window start..end holds end - start + 1 items. Trimming on end - start >= k before adding nums[end] and trimming on end - start + 1 > k after adding are both correct. Pick one.

Worth exploring: a sum is easy to undo when an item leaves, but a max or min is not. For that case, look at the monotonic deque (Sliding Window Maximum, LC 239).

Problems in this pattern#

These problems use this pattern. Solve them before you open the hints below. Start with the first two.

Hints#

Open a hint only after you have tried the problem for a while.

Hint: Maximum Average Subarray I

The state is a running sum. Track the best sum of size k, and divide by k only once at the end.

Hint: Maximum Number of Vowels in a Substring of Given Length

Keep a vowel count. It only changes at the two edges: +1 if the entering character is a vowel, -1 if the leaving one was.

Hint: Contains Duplicate II

The state is a set of the most recent k values. Before you add nums[i], check whether it is already in the set.

Hint: Find K-Length Substrings With No Repeated Characters

Keep a frequency map of the window and check len(freq) == k. Delete a key when its count drops to zero, so the length stays honest.

Hint: Grumpy Bookstore Owner

Every customer who arrives while the owner is not grumpy counts no matter what. That's a fixed base score. The "calm down for minutes" trick only changes the grumpy minutes, so slide a window of size minutes over the customers lost to grumpiness. Add the best window to the base.

Hint: Find All Anagrams in a String

The window size is len(p). Keep a character count for the window and compare it with the count for p at every full window.

Hint: Minimum Number of Flips to Make the Binary String Alternating

Trying every rotation is $O(n^2)$ . Every rotation of s is a window of length n in s + s, so slide that window and update the mismatch count at its two edges. Count mismatches against 0101... only: the count for 1010... is n - mismatch.

Hint: Find K Closest Elements

The array is sorted. Start with the whole array and, while it holds more than k items, drop whichever end is farther from x. That is $O(n)$ . A max-heap of size k also works at $O(n \log k)$ plus a final sort, and a faster variant binary-searches for where the window should start.

Hint: Sliding Window Maximum

Keep a deque of indexes whose values decrease from front to back. Before pushing i, pop smaller values off the back, and pop the front once it leaves the window. The front is then always the window's maximum.

Key takeaways#

Fixed window: start moves because of the index, never because of the values.
Grow, trim nums[i - k], then process once i >= k - 1.
Update only the two edges, so the whole scan is $O(n)$ .
Rotations of a string are windows of length n in s + s.
A fixed base score plus the best window is a common disguise.

Core idea#

The window always holds exactly k items. Each step adds the item that enters and removes the one that leaves, so the scan is $O(n)$ .

Key points#

start moves because of the index, never because of the values.
Each step: grow (add nums[i]), trim (once i >= k, remove nums[i - k]), process (once i >= k - 1).
Consecutive windows share k - 1 items. Recomputing each window costs $O(nk)$ ; updating the two edges costs $O(1)$ .
The window state can be a sum, a counter or a dict. The shape stays the same.
Spot it: "subarray or substring of length k", "every k consecutive", an anagram of p (size len(p)).

Common variants#

Problem	Trick
Grumpy Bookstore Owner	Fixed base score plus the best window of size `minutes`
Max vowels in length k	Vowel count changes only at the two edges
No repeated characters	Frequency map; check `len(freq) == k`
Min flips, alternating string	Every rotation is a window of length `n` in `s + s`; the `1010...` target costs `n - mismatch`
Find K Closest Elements	Sorted: drop the farther end until `k` items remain

Template#

state = empty                   # sum, count or map
best = worst possible value
for i in range(len(items)):
    add items[i] to state       # grow: items[i] enters
    if i >= k:
        remove items[i - k]     # index too far: it leaves
    if i >= k - 1:              # size is exactly k from here
        best = better of best and the answer for state
return best

Pitfalls#

Processing too early. The window is not full until i == k - 1.
Mixing styles. Remove nums[i - k] in the index style, or nums[start] then start += 1 with an explicit start.
Stale keys. A count of zero still adds to len(freq). Delete the key.
Off-by-one in the size check. The window start..end holds end - start + 1 items.

Say it in an interview#

"In a fixed window, start moves because of the index, not the contents."
"Update only the two edges, so the whole scan is O(n)."