🎓 A1Learner
🔍
0 of 47 lessons completed

The Sliding Window Pattern

Sliding window is a technique that keeps one segment of a list in view at a time. The segment grows on one side and shrinks on the other side as it moves.

The recognition signal

The signal is a question about a segment of nearby values.

signals = ["Question asks for a segment", "Segment has a fixed size or a rule", "Values sit next to each other"]
for signal in signals:
    print("Signal " + signal)

The template

The template keeps a running sum for the current segment.

def max_sum_k(numbers, k):
    window_sum = sum(numbers[:k])
    best = window_sum
    for i in range(k, len(numbers)):
        window_sum = window_sum + numbers[i] - numbers[i - k]
        if window_sum > best:
            best = window_sum
    return best
print(max_sum_k([2, 1, 5, 1, 3, 2], 3))

Worked problem longest segment

A set tracks the values inside the current window.

def longest_no_repeat(text):
    seen = set()
    left = 0
    best = 0
    for right in range(len(text)):
        while text[right] in seen:
            seen.remove(text[left])
            left = left + 1
        seen.add(text[right])
        if right - left + 1 > best:
            best = right - left + 1
    return best
print(longest_no_repeat("abcabcbb"))

Example

def max_sum_k(numbers, k):
    window_sum = sum(numbers[:k])
    best = window_sum
    for i in range(k, len(numbers)):
        window_sum = window_sum + numbers[i] - numbers[i - k]
        if window_sum > best:
            best = window_sum
    return best
print(max_sum_k([1, 4, 2, 10, 23, 3, 1, 0, 20], 4))

Key points

  • A window has a start position and an end position.
  • The end position moves forward to grow the window.
  • The start position moves forward to shrink the window.
  • Each value enters the window once and leaves the window once.
  • A window fits a question about a segment of values.
  • A window is simply a segment that moves across the data.

The program builds the sum of the first four values. It then slides the segment forward one step at a time. The best sum seen so far is printed at the end.

Try it Yourself

Edit the code, then press Run.

Running is simulated · Python Playground

Exercise

A window breaks its rule after growing. What should happen next?