Sliding Window

Description

A sliding window is a contiguous range of an array or string that moves forward one step at a time. It carries a running summary of what's inside it: a sum, a count, or a map of how often each value appears. Instead of recomputing that summary for every range, you add the element that enters and remove the one that leaves. It answers "best contiguous range" questions, such as the largest sum of k values in a row, the longest substring without repeats, or the shortest subarray that reaches a target.

We'll go from simple to more technical:

1. The fixed-size window: one add and one subtract per step.
2. The variable-size window: right always advances, left catches up.
3. Where the same idea runs in production (rate limiters, moving averages).
4. When it applies, and the mistakes that make the window drift.

The approach (fixed-size window)

The brute force adds up every window from scratch: k additions for each of the n - k + 1 windows, O(n*k) in all. But two neighboring windows share all but two elements. So keep one running sum. Each step adds the element that enters on the right and, once the window is full, subtracts the one that leaves on the left.

The largest sum of 3 values in a row in [3, 1, 4, 2, 5, 1]:

int windowSum = 0;
for (int i = 0; i < nums.length; i++) {
    windowSum += nums[i];
    if (i >= k) windowSum -= nums[i - k];   // drop the element leaving the window
    if (i >= k - 1) best = Math.max(best, windowSum);
}

window_sum = 0
for i in range(len(nums)):
    window_sum += nums[i]
    if i >= k:
        window_sum -= nums[i - k]    # drop the element leaving the window
    if i >= k - 1:
        best = max(best, window_sum)

The window is never rescanned. Each step does one add and, once the window is full, one subtract. That turns O(n*k) into O(n).

A second flavor: variable-size windows

Some questions have no fixed size. "The shortest subarray with a sum of at least the target" needs a window that grows and shrinks:

int left = 0, sum = 0, best = Integer.MAX_VALUE;
for (int right = 0; right < nums.length; right++) {
    sum += nums[right];                    // right always advances
    while (sum >= target) {                // left advances only while the condition holds
        best = Math.min(best, right - left + 1);
        sum -= nums[left];
        left++;
    }
}

left = total = 0
best = float("inf")
for right in range(len(nums)):
    total += nums[right]                  # right always advances
    while total >= target:                # left advances only while the condition holds
        best = min(best, right - left + 1)
        total -= nums[left]
        left += 1

right moves one step per loop, as before. left moves zero, one or several steps, as long as the window still meets the condition. So the two edges no longer move together. For [1, 4, 2, 2, 5, 1] and a target of 7, the shortest window is [2, 5], of length 2. Each element enters once and leaves at most once, so this is still O(n).

Where you'll see it

A rate limiter works this way. "How many requests in the last 60 seconds?" is a window over a stream of timestamps, updated as requests arrive instead of recounted each time. A dashboard's rolling 5-minute average latency is computed the same way, without rereading the whole buffer every tick.

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A fixed-size window checks i > k instead of i >= k. What goes wrong?

2. Why can't a variable-size window move left by a fixed amount when the window stops meeting the condition?

3. You need the maximum of every window of size k. Can it be updated cheaply as the window slides?

Key takeaways

• A fixed-size window adds the element that enters and subtracts the one that leaves: O(n) instead of O(n*k).
• In a variable-size window, right moves every step and left moves only while the window still meets the condition.
• The most common bug is an off-by-one at the window's edge. Trace k = 1 by hand.
• Whatever you did when an element entered, undo exactly when it leaves (decrement a count, don't just remove from a set).
• The idea only pays off when the summary can be updated more cheaply than recomputed.