Sliding window (fixed size)

How does Sliding window (fixed size) work?

Build the first window from the first k elements. Compute its answer once, the slow way.

Now roll the window one slot to the right. Exactly one element enters and one leaves.

Update the running value from those two elements. Add the newcomer and subtract the one that left.

Record the answer for this window before rolling on. The best so far lives in one variable.

Repeat until the right edge reaches the last element. There are n minus k plus one windows.

No window is ever recomputed from scratch. That is what turns O(nk) into O(n).

1. [4, 2, 7] sum = 13Window size is three. The first window is summed directly.
2. [2, 7, 1] sum = 101 enters and 4 leaves. So 13 plus 1 minus 4 is 10.
3. best = 13This window is worse than the first. The best does not move.
4. [7, 1, 5] sum = 135 enters and 2 leaves. So 10 plus 5 minus 2 is 13.
5. answer = 13The right edge reached the end. Three windows, five reads.

function windowStat(arr, k) {
    let windowSum = 0;
    for (let i = 0; i < k; i++) windowSum += arr[i];
    let best = windowSum;
    for (let i = k; i < arr.length; i++) {
        windowSum += arr[i] - arr[i - k];
        best = Math.max(best, windowSum);
    }
    return best;
}

A worked example of Sliding window (fixed size)

Find every anagram of a word

You get a string s and a shorter string p. Return every start index where s holds an anagram of p.

An anagram uses the same letters with the same counts.

Count the letters of p once. Then roll a window of that same length across s.

Each roll adds one letter and removes one. Compare the counts and record the index on a match.

function findAnagrams(s, p) {
    if (p.length > s.length) return [];

    const need = new Array(26).fill(0);
    const have = new Array(26).fill(0);
    const at = (c) => c.charCodeAt(0) - 97;

    for (const c of p) need[at(c)]++;

    const result = [];
    for (let i = 0; i < s.length; i++) {
        have[at(s[i])]++;

        // one letter leaves as soon as the window is longer than p
        if (i >= p.length) have[at(s[i - p.length])]--;

        if (i >= p.length - 1 && need.every((n, j) => n === have[j])) {
            result.push(i - p.length + 1);
        }
    }

    return result;
}

When should you use Sliding window (fixed size)?

These phrases in a problem statement point here:

• •contiguous subarray/substring of a given length k
• •every window of size k
• •rolling average or moving sum
• •min/max/count/sum over each fixed span

What is Sliding window (fixed size) confused with?

• Sliding window (variable): A variable window decides its own width from a condition. This one is k wide for the whole pass.
• Prefix sums: Prefix sums are built once and then answer any range. A fixed window answers about one moving span.
• Monotonic deque (sliding window max/min): A sum survives a subtraction, so plain arithmetic is enough. A maximum needs the deque.
• Hash set / map: A map counts over the whole collection and knows no positions. The window asks only about k neighbours.

Common mistakes with Sliding window (fixed size)

• Rebuilding the window every step

  Summing k elements at each position costs O(nk). Reuse the previous total instead.

• Recording an answer too early

  The first k minus one positions hold a partial window. Start recording once it is full.

• Dropping the wrong element

  The value leaving sits at index i minus k. An off-by-one here shifts every window.

• Using a rolling sum for a maximum

  Subtracting the element that left cannot restore a maximum. That case needs a monotonic deque.

Which interview problems use Sliding window (fixed size)?

• Maximum sum subarray of size k: The plain form: one addition and one subtraction per step.
• Maximum average subarray I: The same sum, divided by k at the end.
• Find all anagrams in a string: The window carries letter counts instead of a total.
• Permutation in string: The same counts, but it stops at the first match.
• Repeated DNA sequences: Every window of ten characters, tallied in a map.
• Sliding window maximum: A fixed window whose answer needs a monotonic deque.
• K radius subarray averages: A window centred on each index instead of trailing it.

What is the time and space complexity of Sliding window (fixed size)?

O(n)

n up to 1e6 with window size k gives O(n). Each element enters the window once and leaves once.