Sliding Window (Fixed Size)

1. The signal

• “subarray/substring of size k”
• “every window of length k”
• “average / maximum / sum of each k consecutive elements”
• Checking for a permutation or anagram inside a string — a permutation has a fixed length, so the window does too.

If the problem names a size, the window is fixed. If it says “longest such that”, it’s variable.

2. The template

for (int r = 0; r < n; r++) {
    add(a[r]);                        // one enters
    if (r >= k) remove(a[r - k]);     // one leaves — window stays size k
    if (r >= k - 1) {
        // the window is exactly [r-k+1, r]; answer the question here
    }
}

for (let r = 0; r < n; r++) {
  add(a[r]);
  if (r >= k) remove(a[r - k]);
  if (r >= k - 1) {
    // window is exactly [r-k+1, r]
  }
}

The two ifs are the whole pattern. r >= k means the window is already full so something must leave; r >= k - 1 means the window has just become full so the answer is available.

3. Why it’s O(n)

Each element enters once and leaves once. There is no inner loop at all in the basic form — this is strictly simpler than the variable window, which is why it’s worth doing first.

4. Complexity

O(n) time, O(k) space at most (often O(1) with a fixed alphabet).

5. Variants

Counting comparison — Permutation in String keeps a count array for the pattern and one for the window, and compares them. Comparing two 26-slot arrays is O(26) = O(1), so the whole thing stays O(n). A neater version tracks a single matches counter so each step is genuinely O(1).

Monotonic deque — Sliding Window Maximum needs the max of each window. A heap gives O(n log k); a deque of indices with decreasing values gives O(n). The invariant:

Values in the deque decrease from front to back, and every index in it is inside the window.

So the front is always the maximum. Before pushing r, pop every index at the back whose value is ≤ a[r] — those can never be a maximum again while a[r] is in the window. Then evict the front if it has fallen out of range.

Store indices, not values: only the index tells you when something falls out of the window.

Degenerate window — Best Time to Buy and Sell Stock is a window whose left edge is “the cheapest day so far”. It’s the gentlest possible version, and a good warm-up.

6. Traps

1. r >= k vs r >= k - 1. One controls eviction, the other controls when to answer. Mixing them gives off-by-one windows.
2. In JavaScript, using shift() on the deque. It’s O(n), which silently makes Sliding Window Maximum O(n²). Use a head index into an array.
3. Popping with < instead of <=. With < you keep equal values, which still works but grows the deque unnecessarily. Either is correct; know which you wrote.
4. k larger than the array. Guard it.

7. Problems, easiest first

1. Best Time to Buy and Sell Stock — the warm-up
2. Permutation in String — fixed window + count compare
3. Sliding Window Maximum — the monotonic deque