Lesson 19 — Sliding window

Sliding window: reuse the overlap

Find the biggest sum of k consecutive numbers. Re-adding k numbers at every position is wasteful, because neighbouring windows share k − 1 numbers. Instead, slide: add the new number entering on the right and subtract the one leaving on the left.

# window [1, 4, 2] = 7 -> slide right by one: 7 + 10 - 1 = 16 = [4, 2, 10]

Why it matters: moving averages, "busiest hour" reports and network rate-limiters all slide a window in O(n) instead of O(n × k).