Sliding window: variable size

The sliding window: variable size

Fixed windows have a constant width. Variable windows grow and shrink to satisfy a condition — "the longest substring with no repeats," "the shortest subarray summing to at least target," "count subarrays whose product is below k." Two pointers, left and right, bound the window.

The recipe

left = 0
for right in 0..length(nums)-1:
    // 1. include nums[right] in the window
    add(nums[right])

    // 2. shrink from the left while the window is invalid
    while windowIsInvalid():
        remove(nums[left])
        left += 1

    // 3. the window [left..right] is now valid — record the answer
    best = max(best, right - left + 1)
return best

right always moves forward; left only ever moves forward too. So even though there's an inner loop, each element is added once and removed once — the total work is O(n).

Choosing the invariant

The whole problem is in deciding when the window is invalid and what to record:

Longest with a property → shrink until the property holds again, then record the width. (no repeated chars; at most k distinct.)
Counting subarrays → when the window is valid, every subarray ending at right and starting at any index in [left, right] is valid, so add right-left+1.

A caveat

Variable windows that rely on "shrink when the sum is too big" assume non-negative numbers — with negatives, growing the window can decrease the sum, so shrinking logic breaks (you'd reach for prefix sums and a hash map instead). For the problems here, the inputs are chosen so the window technique applies cleanly.