Sliding Window — Fixed and Variable-Size Subarrays

The Concept

A sliding window is a contiguous subarray described by two indices, left and right, that together define a range [left, right] inside a larger array. Instead of re-examining every element each time the window moves, you maintain a running aggregate — adding the element that just entered on the right and removing the one that just left on the left. That incremental update costs O(1) per step, which is what makes the whole scan O(n).

There are two distinct flavours, and knowing which one to reach for is the main skill.

Fixed-size window

The window width is a constant k. You slide it one step at a time across the array:

1. Compute the aggregate for the initial window [0, k-1].
2. For every new position, add nums[right] and subtract nums[right - k] — the element that fell off the left edge.
3. Track the best aggregate seen so far.

A canonical example: maximum sum of any subarray of length k. Because both indices advance monotonically and the update is O(1), the full scan is O(n) with O(1) extra space.

Variable-size window

Here the window width is not fixed — it is bounded by a constraint (e.g. "at most k zeros", "sum ≤ target"). The strategy is:

1. Grow right to include the next element.
2. While the constraint is violated, advance left to shrink the window until the constraint holds again.
3. At each step where the constraint holds, record the window size (or whatever you are optimizing).

A canonical example: longest subarray of 1s you can form by flipping at most k zeros (LeetCode 1004 / Max Consecutive Ones III variant). The key insight is that left never moves backwards — both pointers only advance — so the total number of steps across the entire scan is at most 2n, giving O(n) overall.

Code Implementation

Complexity Analysis

The O(n) bound holds even for the variable-size variant despite the inner while loop. Because left never decreases, the total number of times it advances across the entire outer loop is at most n — the inner and outer loops together take O(n) steps.

Interactive Lab

Watch the fixed-size window slide across the array, updating its running aggregate with a single addition and subtraction at each step.

This visualizer shows the maximum-average-subarray problem: a fixed window of width k slides across the input and the running average is updated O(1) per step.

In this variable-size variant, the right edge grows to include the next element and the left edge advances whenever the zero count exceeds k — tracking the longest subarray of ones achievable with at most k flips.

Key Takeaways

• Window invariant. At every step the window [left, right] satisfies the problem's constraint. Maintaining that invariant — not just checking it after the fact — is what makes the approach correct and efficient.
• Fixed vs. variable. Fixed-size windows update with a single add-and-subtract. Variable-size windows grow on the right and shrink on the left until the constraint holds; the constraint drives left, not a fixed offset.
• Each element enters and leaves once → linear time. right sweeps from 0 to n-1 exactly once. left only ever advances. The total number of index movements is at most 2n regardless of how many times the inner shrink loop runs.
• O(1) extra space. Both patterns only track a constant number of running values (sum, zero count, etc.) — no auxiliary array needed.