Sliding Window

Overview

The sliding window technique maintains a contiguous range over a list or string and slides it forward instead of recomputing from scratch. It shines for problems about subarrays or substrings, like maximum sums or longest runs. By reusing work as the window moves, it usually runs in O(n) time.

Syntax / Usage

A fixed-size window adds the new element and removes the one leaving the window. A dynamic window grows the right edge and shrinks the left edge when a condition breaks.

def max_sum_window(numbers, k):          # O(n) time, O(1) space
    window = sum(numbers[:k])
    best = window
    for right in range(k, len(numbers)):
        window += numbers[right] - numbers[right - k]  # add new, drop old
        best = max(best, window)
    return best

Examples

Find the largest sum of any k consecutive numbers:

print(max_sum_window([2, 1, 5, 1, 3, 2], 3))  # 9  (5 + 1 + 3)

A dynamic window finds the longest substring without repeating characters:

def longest_unique(s):
    seen = {}
    left = best = 0
    for right, ch in enumerate(s):
        if ch in seen and seen[ch] >= left:
            left = seen[ch] + 1          # shrink window past the repeat
        seen[ch] = right
        best = max(best, right - left + 1)
    return best

print(longest_unique("abcabcbb"))  # 3  ("abc")

Common Mistakes

• Recomputing the whole window each step, which defeats the O(n) benefit.
• Off-by-one errors in window width, e.g. right - left instead of right - left + 1.
• Forgetting to subtract the element that leaves a fixed-size window.
• Failing to move the left edge when the window becomes invalid.
• Assuming the input is non-empty and reading numbers[:k] when k exceeds the length.

See Also

algorithms-two-pointers algorithms-searching algorithms-big-o-notation