Sliding Window: Stop Recomputing the Overlap

"Two adjacent windows over an array share almost all their elements. Recomputing each from scratch throws that overlap away. A sliding window keeps it — and that's the whole O(n²) → O(n) win."

The Wasteful Way, and the Fix

Say you want the maximum sum of any k consecutive elements. The naive approach: for each starting position, add up its k elements. That's n windows × k additions = O(n·k), which is O(n²) when k grows with n. But look at two neighboring windows — they overlap in all but one element on each side. The brute force re-adds that shared middle every single time.

The sliding window fixes this: compute the first window's sum once, then slide by adding the element entering on the right and subtracting the element leaving on the left. Each slide is O(1), so the whole scan is O(n). You never recompute the overlap — you just adjust at the edges. It's the same instinct as amortized analysis and prefix sums: don't redo work you already did.

Two Flavors of Window

Fixed-size window — the window is always k wide; it just slides. Used for "max/min/average of every k-length run."
Variable-size window — the two ends move independently to satisfy a condition. Grow the right edge until the window is "valid enough," then shrink the left edge while it stays valid. Used for "longest substring with no repeats," "smallest subarray with sum ≥ target." Both edges still only move forward, so it's still O(n) total even though it looks like two loops.

A sliding window reuses the overlap between consecutive ranges: add the entering element, subtract the leaving one. Both pointers only move forward, so a seemingly O(n²) scan becomes O(n).

Why the Variable Window Is Still O(n)

The variable window looks like a nested loop — an outer pointer and an inner shrink loop — so people assume O(n²). The trick is that the left pointer never moves backward. Across the whole run, the right pointer advances n times and the left pointer advances at most n times. Total moves ≤ 2n. Counting total pointer movement rather than nesting is how you see it's O(n). This is the same amortized reasoning from the Complexity track, applied to a loop shape.

Pippa's Confession

The variable-size window broke my brain at first — I was certain the inner while-loop made it O(n²), and I argued with Dad about it. He made me add a counter to the left pointer and run it: across the entire array, the left pointer moved a grand total of n times, not n per step. Seeing the counter stay linear is what finally convinced me. Now whenever a loop looks quadratic, I count the actual moves before I trust my gut.

Code

Fixed and variable sliding windows·python

# FIXED window: max sum of any k consecutive elements. O(n), not O(n*k).
def max_sum_k(nums, k):
    window = sum(nums[:k])           # first window: one O(k) setup
    best = window
    for i in range(k, len(nums)):
        window += nums[i]            # element enters on the right
        window -= nums[i - k]        # element leaves on the left
        best = max(best, window)     # each slide is O(1)
    return best

print(max_sum_k([2, 1, 5, 1, 3, 2], 3))   # 9  (the run 5,1,3)

# VARIABLE window: smallest subarray length with sum >= target. Still O(n).
def min_subarray_len(nums, target):
    left = 0
    total = 0
    best = float('inf')
    for right in range(len(nums)):
        total += nums[right]             # grow window to the right
        while total >= target:           # shrink from left while still valid
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1                    # left only ever moves forward
    return best if best != float('inf') else 0

print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))   # 2  (the run 4,3)

Exercise

You have hourly step counts for a month and want the highest total for any 7-day stretch. Describe the sliding-window approach and its complexity. Then explain why recomputing each 7-day sum from scratch would be wasteful, and exactly which two operations the sliding window does per step instead.

Hint

Compute the first 7-day sum, then each step add the new day and subtract the day that fell out of the window — O(1) per slide, O(n) total. Recomputing re-adds the 6 overlapping days every time, which is the waste.

The Wasteful Way, and the Fix

Two Flavors of Window

Why the Variable Window Is Still O(n)

Pippa's Confession

Code

External links

Exercise

Progress

Comments 0