Fixed-Size Window

The window is locked at exactly k elements — one enters, one leaves, every step. That rigidity makes fixed windows the easy half of the pattern, behind a 7-line template. The only real skill is choosing what running state to maintain (a sum? a frequency map? a deque? a set?), and the slickest trick — a single “match counter” — turns an O(26) anagram check into O(1).

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).

Run it and watch the window slide — change the array or k and see which length-k block wins:

Run it yourself — Python

def max_sum_subarray(nums, k):
  window = sum(nums[:k])          # first window
  best, best_start = window, 0
  for r in range(k, len(nums)):
      window += nums[r] - nums[r - k]   # add entering, drop leaving — O(1)
      if window > best:
          best, best_start = window, r - k + 1
  return best, nums[best_start:best_start + k]

nums = [2, 1, 5, 1, 3, 2]
k = 3
total, block = max_sum_subarray(nums, k)
print("array:", nums, "  k =", k)
print("best window sum:", total, "from", block)

Worked example 2: Moving Average

Implement a class that computes the moving average of the last k values 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.

Recall the eviction step that keeps the moving-average window at size k — drop the oldest when it overflows:

python · fill in the blanks0/1 hints

def next(self, val):
  self.q.append(val)
  self.sum += val
  if len(self.q) > self.k:
      # window is too big -> remove the element that left
      # ??? evict the oldest value when the window overflows
  return self.sum / len(self.q)

Time: O(1) per next() call. Space: O(k).

Worked example 3: Find All Anagrams of `p` in `s`

Given two strings s and p, return the starting indices of every substring of s that is an anagram of p.

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.

Predict first

Comparing the window's 26-entry frequency map against p's map every slide is O(26) per step. How do you make the 'is this window an anagram of p?' check O(1)?

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 nums and k, return true if there are two distinct indices i and j with nums[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 true immediately).

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

In the Max-Sum-of-size-k template, why do we run a separate loop for the first window before entering the slide loop?

What's the time complexity of Find All Anagrams using the 'match counter' trick?

For Contains Nearby Duplicate, why do we use a hash SET (not a hash map)?

Fixed windows are the rigid, one-in-one-out case. Next: variable-size windows — the harder half, where the two pointers move independently based on a validity predicate (and the matches-counter trick returns for Minimum Window Substring).

Introduction Variable-Size Window

Finished this page?