Sliding Window (Fixed Size)

A window that slides

Problem: find the biggest total of any k days in a row. The simple way adds up k numbers for every starting day – O(n·k). But neighbouring windows share almost everything!

Think of it like this: Looking out of a train window: as the train moves, one new tree comes into view on the right and one disappears on the left. You don't need to look at the whole view again.

def best_k_days(nums, k):
    window = sum(nums[:k])          # first window
    best = window
    for right in range(k, len(nums)):
        window += nums[right]       # new item comes in
        window -= nums[right - k]   # oldest item leaves
        best = max(best, window)
    return best

print(best_k_days([2, 1, 5, 1, 3, 2], 3))

Output

9

Each step does one addition and one subtraction, so the whole thing is O(n).

Watch it slide

nums = [2, 1, 5, 1, 3, 2]
k = 3
window = sum(nums[:k])
print(nums[0:k], "=", window)
for right in range(k, len(nums)):
    window += nums[right] - nums[right - k]
    print(nums[right - k + 1:right + 1], "=", window)

Output

[2, 1, 5] = 8
[1, 5, 1] = 7
[5, 1, 3] = 9
[1, 3, 2] = 6