Sliding windows

Many problems ask about contiguous parts of a list or string: subarrays and substrings. The brute force looks at all of them, O(n²) or worse. A sliding window keeps one window and moves its edges, updating its contents in O(1) per move.

A fixed-size window

The largest sum of any k consecutive numbers.

Sum the first k. Then slide: add the number entering on the right, subtract the one leaving on the left. O(n), not O(n k).

def max_window_sum(nums, k):
    window = sum(nums[:k])
    best = window
    for right in range(k, len(nums)):
        window += nums[right] - nums[right - k]   # one in, one out
        best = max(best, window)
    return best

print(max_window_sum([2, 1, 5, 1, 3, 2], 3))
print(max_window_sum([-1, -2, -3], 2))

A window that grows and shrinks

The length of the longest substring without repeating characters.

Grow the window by moving right. When the new character is already inside, shrink it from the left until the repeat is gone. A set holds the characters inside the window.

def longest_unique(s):
    inside = set()
    left = best = 0
    for right, ch in enumerate(s):
        while ch in inside:                # shrink until ch is no longer repeated
            inside.remove(s[left])
            left += 1
        inside.add(ch)
        best = max(best, right - left + 1)
    return best

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

Each character enters the window once and leaves it at most once, so although there is a loop inside a loop, the total work is O(n). This is the key argument for every sliding window: count the moves of each edge, not the loops.

The template

left = 0
for right in range(len(items)):
    add items[right] to the window
    while the window breaks the rule:
        remove items[left] from the window
        left += 1
    update the answer with the window items[left .. right]

To find the shortest window that meets a condition (the smallest subarray with sum ≥ target), turn it round: shrink while the window still meets the condition, and record the length before each shrink.

Sliding windows need the window's condition to change in one direction as it grows: adding an element can only make "has a repeat" or "sum ≥ target" more true. With negative numbers, "sum ≥ target" loses that property, and prefix sums with a hash map are needed instead.

Mark lesson complete