Fixed-Size Window
A fixed-size sliding window has a single rule: the window is always exactly k elements long. As you scan the array, one element enters on the right, one element leaves on the left, and the running state updates accordingly.
This is the easier of the two flavors and lives behind a 7-line template.
The template
1. Build the first window: process nums[0 .. k-1].
2. Initialize the answer from the first window.
3. For each index r = k .. n-1:
- ADD nums[r] → it just entered the window.
- REMOVE nums[r - k] → it just left.
- Update the answer from the current window state.In code:
What changes problem-to-problem is what state is, what add / remove do, and what answer_from(state) returns.
Worked example 1: Max sum of size-k subarray
Find the maximum sum of any contiguous subarray of length
k.
State: the running sum.
Add: sum += x. Remove: sum -= x. Answer from state: sum itself.
Time: O(n). Space: O(1).
Worked example 2: Moving Average
Implement a class that computes the moving average of the last
kvalues from a stream of integers.
State: running sum + a queue of the most-recent k values (because we need to know what to subtract when the queue overflows).
Add: push to queue, sum += x. Remove: pop oldest if queue size exceeds k, sum -= popped.
The queue is the window state. The sum is just a precomputed projection of that state for O(1) answer extraction.
Time: O(1) per next() call. Space: O(k).
Worked example 3: Find All Anagrams of p in s
Given two strings
sandp, return the starting indices of every substring ofsthat is an anagram ofp.
Insight: an anagram of p is any size-|p| window of s whose character-frequency map equals p’s. So the window has fixed size |p|, and the state is a frequency hash map. We test equality with p’s frequency map after every slide.
A naïve “compare two maps with 26 entries” check is O(26) per slide. There’s a slicker O(1) check: maintain a match count — number of characters whose window-frequency matches p’s target. When matches == 26 (or however many distinct chars p has), the window is an anagram.
Time: O(n). Space: O(1) — fixed-size 26-entry alphabets.
The “matches counter” trick is gold. Instead of comparing two arrays of 26 ints (O(26)) every shift, you track a single integer and update it in O(1) whenever a frequency crosses or moves away from its target. This same trick comes back in Minimum Window Substring (a variable-window problem).
Worked example 4: Contains Nearby Duplicate
Given
numsandk, returntrueif there are two distinct indicesiandjwithnums[i] == nums[j]and|i − j| <= k.
Window: the last k + 1 elements. State: a hash set of values currently in the window. Answer extraction: if nums[r] is already in the set, return true.
Time: O(n). Space: O(k).
Common pitfalls
Off-by-one on the first slide. The first window covers indices 0 .. k-1. The first new element added by the slide loop is at index k. The first removed element is at index 0 (= k - k). Get either of these wrong and your first window is the wrong size.
Recording the answer at the wrong time. Decide whether you record:
- Every iteration (most max/min sum problems).
- Only when the window first reaches size
k(Find All Anagrams). - Only when a specific condition holds (Contains Nearby Duplicate — return
trueimmediately).
Recording before the first window is fully built, or skipping the very last window, is a classic off-by-one bug.
Choosing the right state
The hardest decision in any fixed-window problem is what to maintain in the running state. Here’s a decision tree:
| You’re tracking… | State to maintain |
|---|---|
| Sum / count | A single integer |
| Max / min | A monotonic deque (covered in Advanced) |
| Whether a duplicate exists | A hash set |
| Whether the window matches a character profile | A frequency array (26 for lowercase / 128 for ASCII) + match counter |
| Whether the window contains specific elements | A hash set + counter |
| Average (for streaming problems) | A queue (so you know what to evict) + sum |
When in doubt, ask: “What’s the smallest piece of data I need to answer the question for the current window in O(1)?” That’s your state.
Quick check
Next: variable-size windows — the harder half, where the two pointers move independently based on a validity predicate.