The Fixed-Sized Sliding Window Technique

The Fixed-Sized Sliding Window Technique

Imagine you have a long row of numbers and you want to answer a question about *every* group of k numbers in a row. For example: "What is the sum of every 4 numbers in a row?" or "What is the average of every 4 numbers in a row?"

A small group of items that sit next to each other in an array is called a subarray. A subarray of size k is just k neighboring items. So the task is: look at every subarray of size k and compute something for each one.

The slow way, and why we want better

The obvious way is to use two loops (a loop inside a loop). The outer loop picks a starting spot, and the inner loop adds up the k items starting there. This works, but it is slow. If the array has N items and the window is size k, you do roughly N × k work, because for every starting spot you re-add the same numbers again and again.

Here is the key waste: when you move from one group to the very next group, most of the items are the same. Only one item leaves on the left and one new item joins on the right. Re-adding the middle items every time is repeated work.

The fixed-sized sliding window technique removes that waste. It computes the answer for *all* groups of size k in a single pass over the array.

The big idea: slide, don't rebuild

Think of a window — like a small frame — that covers exactly k items. Instead of rebuilding the whole sum each time, we *slide* the frame one step to the right:

• Add the new item that just entered on the right.
• Remove the old item that just fell off on the left.

That's it. One add and one remove per step, instead of re-summing everything.

This only works when your "aggregate function" supports both an add operation and a remove operation. Good examples are:

• sum — add a number, or subtract a number.
• product — multiply by a number, or divide it out.
• average — keep a running sum and divide by k.

We can describe the goal with a function f(i, j), which means "the combined value over the subarray from index i to index j." Our job is to compute f(0, k-1), f(1, k), f(2, k+1), all the way to f(n-k, n-1) — one value for every window of size k.

The three variables

The technique uses three simple variables:

• start — the index of the left edge of the window.
• end — the index of the right edge of the window.
• aggregate — the running result (the sum, product, etc.) for the items currently inside the window.

The algorithm, step by step

1. Step 1: Set start = 0 and end = 0.
2. Step 2: Set aggregate to a starting value (for a sum, that is 0).
3. Step 3: While end < arr.size(), repeat:

• 3.1 Add the contribution of arr[end] to aggregate (the window grows on the right).
• 3.2 If the window is now too big, that is end - start + 1 > k, then remove the contribution of arr[start] from aggregate and do start++ (the window shrinks on the left).
• 3.3 If the window is exactly the right size, that is end - start + 1 == k, then process aggregate — this is where you use the answer (save it, compare it, print it — whatever the problem asks).
• 3.4 Do end++ to get ready to bring in the next item.

Notice the rhythm: grow on the right, shrink on the left if needed, use the answer when the size is right, then move on.

A walk-through with k = 4

Picture an array v1 v2 v3 v4 v5 v6 v7 at indices 0..6, with k = 4.

• end walks right, adding v1, then v2, then v3, then v4. Now the window covers indices 0..3, its size is 4, so we process aggregate = f(0, 3).
• end moves on and adds v5. Now the window is 0..4, size 5, which is too big. So we remove v1 and move start to 1. The window is now 1..4, size 4, and we process aggregate = f(1, 4).
• The same dance repeats: add v6, drop v2 → process f(2, 5). Add v7, drop v3 → process f(3, 6).

We have now produced the answer for every window of size 4 — and each item was added once and removed at most once.

A peek at the code

void fixedSizeSlidingWindow(vector<int> &arr, int k) {
    // Initialize start and end to 0
    int start = 0, end = 0;
    // Initialize aggregate to a default value
    int aggregate = 0;
    // Move the window one step to the right until
    // it reaches the end of the array
    while (end < arr.size()) {
        // Add contribution of arr[end]
        aggregate = fAdd(aggregate, arr[end]);
        // Check if window size is greater than k
        if (end - start + 1 > k) {
            // Remove contribution of arr[start]
            aggregate = fRemove(aggregate, arr[start]);
            // Increment start to contract the window from start
            start++;
        }
        // ... process aggregate when size == k, then end++
    }
}

Here fAdd does the "add" operation and fRemove does the "remove" operation for whatever function you chose.

Why it is fast

The right edge end moves from 0 to N-1 exactly once and never goes back. As long as the add and remove operations each take constant time O(1):

• Time complexity: O(N) — one smooth pass through the array.
• Space complexity: O(1) — we only keep a few variables, no extra data structure.

This is true in both the best and worst case. That single-pass, constant-extra-memory behavior is exactly what makes the sliding window such a loved trick.

Where this fits

This is the fixed-sized sliding window — the window never changes size; it just slides. It is one branch of a bigger family called the sliding window pattern. Later you will also meet the variable-sized sliding window, where the window can grow and shrink based on a condition rather than staying fixed at k.