The Variable-Sized Sliding Window Pattern

The Variable-Sized Sliding Window Pattern

Sometimes a problem asks you to look at subarrays of an array. A subarray is just a stretch of next-to-each-other elements, like arr[2] through arr[5]. For each subarray you compute some value with a function f (a sum, a maximum, a count — whatever the problem needs), and then you combine all those values into one final answer.

The slow way: check every subarray

The most obvious approach is to look at *every* possible subarray. You pick a starting position i, then let an ending position j walk to the right, adding the contribution of each arr[j] as it goes. This gives you every subarray that starts at i. Then you move i one step right and repeat.

For an array of size N, this means:

• Start i at position 0, grow j across the rest of the array.
• Move i to 1, grow j again.
• Keep going until i reaches the end.

This is like running fixed-sized windows of every size, from 1 up to N, through the array. It works, but it does a lot of repeated work. Two nested loops means roughly N × N steps — slow for big arrays.

The good news: for many problems you don't need every subarray. You can skip large groups of them. That is exactly what the variable-sized sliding window technique does.

The idea of a variable-sized window

Imagine a window that sits over a piece of the array. We track its two edges with two numbers:

• start — the left edge of the window.
• end — the right edge of the window.

The window covers the subarray from start to end. Unlike a fixed window, this one can change size: it can stretch wider (expand) or shrink (contract) as it moves. We also keep one more variable:

• aggregate — always holds the value of f over the current window.

Because we update aggregate step by step instead of recomputing it from scratch, we can often solve in a single pass what would otherwise need nested loops.

How the technique works

We set start = 0 and end = 0 (a zero-sized window to begin with) and give aggregate a sensible starting value that the problem decides. Then we loop until end reaches the end of the array. In each turn of the loop we do some or all of these four operations:

1. Update aggregate with the item at end. Add the contribution of arr[end] so it becomes part of the current window's value: aggregate = f(aggregate, arr[end]).

1. Process the aggregate. Right now aggregate is the value of f over the subarray from start to end. Use it however the problem asks — record it, compare it, add it to a running answer.

1. Contract the window (move start forward). If we can safely ignore all the remaining subarrays that start at start, we increment start by 1. Before doing so, we remove arr[start]'s contribution from aggregate so the value stays correct for the smaller window.

1. Expand the window (move end forward). If we want to consider the next, longer subarray, we increment end by 1. We do not add the new item's contribution yet — that happens at the start of the next iteration.

The key insight: in every iteration at least one of start or end moves forward, and neither ever moves backward.

The generic algorithm

• Step 1: Set start and end to 0.
• Step 2: Set aggregate to an initial value the problem decides.
• Step 3: Loop while end < arr.size():
• 3.1: If we should compute the aggregate, add the contribution of arr[end] to aggregate.
• 3.2: Process aggregate.
• 3.3: If we should contract, remove arr[start]'s contribution and increment start.
• 3.4: If we should expand, increment end.

Here is the generic C++ skeleton:

void slidingWindow(vector<int> &arr) {
    // 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()) {
        if (shouldComputeAggregate) {
            // Add contribution of arr[end]
            aggregate = f(aggregate, arr[end]);
        }
        // Process aggregate
        // ......
        // (Add your processing code here)
    }
}

You fill in the shouldComputeAggregate check and the processing/contract/expand logic to match your specific problem.

Why it is fast

Both start and end begin at 0, and in each iteration at least one of them steps forward and never goes back. So across the whole run they can move forward a combined maximum of about 2 * N times before both reach the end of the array.

• Time: at most 2 * N iterations, which simplifies to O(N) — assuming the helper functions f and g each take constant O(1) time. In the best case end reaches the end after just N iterations, still O(N).
• Space: we only use a few variables and create no new data structure, so space is constant O(1) in every case.

So in both the best and the worst case: Time O(N), Space O(1) — a big improvement over the nested-loop approach.

Later in the course we will look at how to recognize which problems fit this pattern and walk through a full worked example.