Sliding Window Technique Explained (Fixed and Variable Size)

A window is a contiguous range of a list or string, from index left to right. The sliding window technique moves that range along the input, updating a running answer as items enter on the right and leave on the left, instead of recomputing everything for each range.

Fixed-size window: best sum of k items#

Find the largest sum of any k consecutive numbers.

Recomputing every window from scratch is O(n·k). Sliding is O(n): when the window moves one step, add the new item and subtract the one that left.

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

daily_sales = [2, 1, 5, 1, 3, 2, 8, 1]
print(max_sum_k(daily_sales, 3))

13

The best 3-day stretch is 3 + 2 + 8 = 13.

Variable-size window: longest substring without repeats#

Find the length of the longest substring with no repeated characters.

Grow the window by moving right. When the new character is already inside the window, shrink from the left until it is not:

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

for s in ["abcabcbb", "bbbbb", "pwwkew", ""]:
    print(repr(s), longest_unique(s))

'abcabcbb' 3
'bbbbb' 1
'pwwkew' 3
'' 0

Although there is a while inside the for, each character is added once and removed at most once, so the total work is O(n).

Smallest window with a sum of at least a target#

Find the length of the shortest contiguous range whose sum is at least target (all numbers positive).

Expand right until the sum is big enough, then shrink from the left as far as possible while it stays big enough:

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

print(min_window_sum([2, 3, 1, 2, 4, 3], 7))
print(min_window_sum([1, 1, 1], 10))

2
0

[4, 3] is the shortest range reaching 7.

The general template#

def sliding_window(items):
    left = 0
    state = ...                      # what the window currently holds
    for right in range(len(items)):
        add items[right] to state
        while the window is invalid:
            remove items[left] from state
            left += 1
        update the answer using the window [left, right]

That block is pseudocode, not runnable Python. The problem decides what "state" is (a sum, a set, a counter) and what "invalid" means.

Common mistakes#

Practice#

def max_vowels(s, k):
    vowels = set("aeiou")
    count = sum(ch in vowels for ch in s[:k])
    best = count
    for right in range(k, len(s)):
        count += s[right] in vowels
        count -= s[right - k] in vowels
        best = max(best, count)
    return best

print(max_vowels("abciiidef", 3))
print(max_vowels("leetcode", 3))
print(max_vowels("rhythm", 2))

3
2
0

Key takeaway#

Next: precomputing sums so any range can be answered in O(1), Prefix Sums.