Core pattern

Sliding window: a train window passing houses

Learn the sliding window pattern through one picture you won’t forget, worked on Max sum of k neighbours.

The example problem

Given a list of numbers and a window size k, find the largest sum of k neighbouring numbers.

Input:  [2, 1, 5, 1, 3, 2, 4, 1, 2], k = 3
Output: 9   (5 + 1 + 3, or 3 + 2 + 4)

Picture it

Picture riding a train past a row of houses; the window always shows exactly k houses, and each house has some lit windows. Instead of recounting all k houses at every stop, when the train moves one house forward we add the house that appears and subtract the one that disappears.

The key idea

Fixed-size sliding window: update the sum by +new − old. O(n) instead of O(n × k).

Python

def max_window(lit, k):
    total = sum(lit[:k])
    best = total
    for i in range(k, len(lit)):
        total += lit[i] - lit[i - k]
        best = max(best, total)
    return best

Practise sliding window

NeetCode 150 problems that use it

Sliding Window ·