Sliding window

Sliding window: fixed size

A window is a contiguous slice of a list. Many problems ask about the best window: the highest 3-day sales total, the longest clean substring, the shortest chunk with a big enough sum.

The naive way recomputes each window from scratch, at n windows times k elements for O(n·k). Most of that work is repeated, since consecutive windows share k − 1 elements.

The sliding window trick starts from that observation. When the window slides one step right, only two elements change, so you add the one entering and subtract the one leaving.

window += nums[i] - nums[i - k]

That one line replaces re-summing k elements, which makes each slide O(1) and the whole scan O(n).

The saving grows with the window. At k = 100 the naive version reads a hundred values per window and this reads two, and the sliding cost does not depend on k at all.

The largest sum of k consecutive values

One add and one subtract per slide.

def best_window(nums, k):
    window = sum(nums[:k])
    best = window
    for i in range(k, len(nums)):
        window += nums[i] - nums[i - k]
        best = max(best, window)
    return best

sales = [4, 2, 9, 3, 7, 1, 8]
print(best_window(sales, 3))

Output

19

The first window is computed once with sum(nums[:k]), and that is the only place a full k-element sum happens.

The loop starts at k rather than 0 because index k is the first element that can enter a window already full. nums[i - k] is the element falling off the left edge at the same moment.

best is seeded with the first window rather than with 0, which matters on all-negative data. Starting from 0 would return 0 for a list where every window sums to something negative.

The answer 19 is the window [9, 3, 7] starting at index 2. The other windows sum to 15, 14, 11, and 16, so none of them reaches it.

Variable-size windows

Harder problems do not fix the window size, they fix a condition: the longest substring with no repeated character, or the shortest run summing to at least a target.

The pattern has three parts.

1. right marches forward one step per loop, growing the window.
2. After each growth, a while loop shrinks from left as long as the window is invalid. For shortest-window problems it inverts, shrinking while the window is still valid and recording answers as it goes.
3. Track the best window seen.

It looks like nested loops, but it is O(n). left only ever moves forward, so each element enters the window once and leaves at most once.

That amortized argument is worth internalizing, because the shape reappears with stacks and BFS later in the course.

This is the single most common pattern in string interview problems, which makes the two directions of the while test worth being able to write from memory.

Longest substring without repeating characters

The while loop evicts from the left until the incoming character is no longer a repeat.

def longest_unique(s):
    seen = set()
    left = 0
    best = 0
    for right, ch in enumerate(s):
        while ch in seen:
            seen.remove(s[left])
            left += 1
        seen.add(ch)
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))
print(longest_unique("bbbbb"))
print(longest_unique("pwwkew"))

Output

3
1
3

The set is the validity test, and ch in seen is O(1), which is what keeps the loop cheap. Scanning the window for a duplicate instead would put the cost back to O(n·k).

Shrinking removes s[left] rather than the duplicate directly, and that is the correct move. Everything from left up to and including the old copy has to go, because the window must stay contiguous.

The window length is right - left + 1, and the + 1 is there because both ends are included.

The three results show the range of behavior. abcabcbb peaks at abc, bbbbb can never hold more than one character, and pwwkew reaches 3 with wke, which is a window that starts after the shrink rather than at index 0.

min_subarray_len

The mirror problem, the shortest run whose sum reaches the target.

def min_subarray_len(nums, target):
    left = 0
    total = 0
    best = float("inf")
    for right, n in enumerate(nums):
        total += n
        while total >= target:
            best = min(best, right - left + 1)
            total -= nums[left]
            left += 1
    return 0 if best == float("inf") else best

print(min_subarray_len([2, 3, 1, 2, 4, 3], 7))
print(min_subarray_len([1, 1, 1], 100))

Output

2
0

This flips longest_unique. There the while shrank while the window was invalid, and here it shrinks while the window is still valid, recording each valid length before shrinking further.

The order inside the loop is what makes it correct: record the length, then remove nums[left], then advance left. Recording after the removal would measure a window that no longer meets the condition.

float("inf") is the sentinel for no answer found, and the final line converts it to 0. Comparing against a plain large number would work but reads worse and can be wrong for big inputs.

For [2, 3, 1, 2, 4, 3] with a target of 7 the answer is 2, from the run [4, 3], and the second call returns 0 because the whole list sums to 3.

One caveat is worth stating: this only works for non-negative numbers, since a negative value could make a longer window valid again after shrinking. Lesson 4-3 handles that case with prefix sums.

It is still O(n) because left only moves forward, so across the whole run each character is added once and removed at most once.

The trap is reasoning about the worst case per iteration. A single while loop could run many times, which suggests O(n²) if you multiply it by the outer loop.

Counting total work instead gives the right answer. right takes n steps, and left can also take at most n steps across the entire run because it never moves backward.

So all the while-loop iterations combined are at most n, and the total is at most 2n, which is O(n).

This style of accounting is called amortized analysis, and it is the argument you will need again for stack-based problems and for BFS, where a per-step bound looks alarming and the total is linear.

There are n − k + 1 = 10 − 3 + 1 = 8 windows, starting at indices 0 through 7.

The formula is easier to trust from the endpoints. The last valid start is index n − k, which is 7 here, and counting starts 0 through 7 inclusive gives 8.

The cost comparison follows. The naive version reads 8 windows times 3 elements for 24 reads, while sliding pays 3 reads for the first window plus 2 per slide, for 3 + 14 = 17.

At this size the gap is unremarkable, and it widens fast as k grows. With n = 10,000 and k = 1,000 the naive version does about 10 million reads and the sliding version about 20,000.

The reason is that the sliding cost is independent of k, which is the whole point of the pattern.