Lesson 43

The Fixed-Size Sliding Window Pattern

What is a fixed-size sliding window?

Imagine you have a long row of numbers and you must look at exactly 4 of them at a time. You start with the first 4 numbers, then slide your view one step to the right to see the next 4, then slide again, and so on — like looking through a small window as it moves across the row. This idea is called the fixed-size sliding window technique.

It works on a very specific kind of problem: when you must compute some result (like a sum, average, or count) for every block of k items in a row — these blocks are called *subarrays* of size k. Sometimes you also combine all those results (for example, keep the largest one) to get the final answer.

A subarray is just a continuous slice of the array. For an array [5, 1, 4, 3, 2, 6], the subarrays of size 4 are [5,1,4,3], [1,4,3,2], and [4,3,2,6].

The problem we will solve

> Given an array arr and an integer k, find the maximum average of all subarrays of size k.

We will use arr = [5, 1, 4, 3, 2, 6] and k = 4. The answer turns out to be 3.75.

When does this pattern apply?

A problem fits the sliding window template if:

You are given an array.
You must compute some function f (sum, average, count, etc.) for all subarrays of size k.
You can add the contribution of a new item and remove the contribution of an old item from that result. (Sum is perfect for this: adding a number and subtracting a number is cheap.)

The slow way first: brute force

The most obvious method uses two loops. The outer loop picks a starting position i (from 0 up to n - k). The inner loop adds up the k numbers starting at i, computes the average, and keeps the maximum.

double kSubarrayAverage(vector<int> &arr, int k) {
    int n = arr.size();
    // Initialize maxAverage to negative infinity
    double maxAverage = -1e9;
    for(int i=0; i<=n-k; i++){
        int sum = 0;
        for(int j=0; j<k; j++) {
            sum += arr[i+j];
        }
        maxAverage = max(maxAverage, (double)sum / k);
    }
    return maxAverage;
}

This is correct, but it does too much repeated work. For every new window it adds up all k numbers from scratch. In the worst case (when k = N/2) this gives a time complexity of O(N²) — slow for large arrays.

The smart way: slide the window

Here is the key insight. When the window moves one step to the right, most of the numbers stay the same. Only one number leaves on the left and one new number enters on the right. So instead of re-adding everything, we just:

add the new number entering on the right, and
subtract the number leaving on the left.

We keep a running sum. We never store the average directly — the average is simply sum / k whenever we need it.

We use two pointers, start and end, both beginning at 0. The variable sum is 0 and maxAverage is -infinity. Then we move end across the array.

Step-by-step on `[5, 1, 4, 3, 2, 6]`, `k = 4`

Start with sum = 0, maxAverage = -inf, both pointers at index 0.
Add arr[end] to sum, then move end forward — keep doing this until the window holds k items.

Add 5 → sum = 5; move end to 1
Add 1 → sum = 6; move end to 2
Add 4 → sum = 10; move end to 3
Add 3 → sum = 13. Now the window is [5,1,4,3] and its size end - start + 1 == k (that is 4).

Window full → compute average = sum / k = 13 / 4 = 3.25. Since 3.25 > -inf, set maxAverage = 3.25.
Move end to 4 and add 2 → sum = 15. Now the window is too big (end - start > k), so we must shrink it from the left.
Remove arr[start] = 5 → sum = 10, then move start to 1. The window is [1,4,3,2], size k again.

Compute average = 10 / 4 = 2.5. This is not bigger than 3.25, so maxAverage stays 3.25.

Move end to 5 and add 6 → sum = 16. Too big again, so remove arr[start] = 1 → sum = 15, move start to 2. The window is [4,3,2,6], size k.

Compute average = 15 / 4 = 3.75. Since 3.75 > 3.25, update maxAverage = 3.75.

end has reached the end of the array. The final answer is maxAverage = 3.75.

The pattern in plain words

Grow the window by moving end and adding arr[end].
When the window has k items, do your calculation (here: average) and update the answer.
When the window grows past k, remove arr[start] and move start to keep the size at exactly k.

class Solution {
public:
    double kSubarrayAverage(vector<int> &arr, int k) {
        int n = arr.size();
        int start = 0;
        int end = 0;
        int sum = 0;
        double maxAverage = -1e9;
        while (end < n) {
            // add arr[end], check window size,
            // compute average when size == k,
            // shrink from start when size > k
        }
    }
};

Why this is better

Each number is added once and removed at most once, so we make a single pass through the array. That gives a time complexity of O(N) — much faster than the O(N²) brute force, and it scales well to big inputs.