Fixed Windows: Slide, Don't Recount
A café counts customers each hour: 5, 1, 3, 8, 2 and 6. The owner wants the busiest three-hour stretch, to schedule an extra barista. You could add up every stretch of three from scratch. But neighbouring stretches share two of their three hours, and recounting shared hours is wasted work.
The rule
Add the one coming in, subtract the one going out.
A fixed window is a stretch of exactly k consecutive items that moves one step at a time. When it moves right, exactly one item enters on the right and exactly one leaves on the left. Everything in between is unchanged, so the new total is the old total plus the newcomer minus the leaver.
def best_k_total(nums, k):
window = sum(nums[:k]) # the first window, added once
best = window
for i in range(k, len(nums)):
window += nums[i] - nums[i - k] # in comes nums[i], out goes nums[i - k]
best = max(best, window)
return bestRecounting costs k additions per window, about n × k in total: for 100,000 hours and a window of 1,000 that is a hundred million additions. Sliding costs two operations per step, about n in total, whatever k is. The best average of k consecutive items comes for free, too: it is the best total divided by k, because k never changes.
The same move works for anything you can add and remove: a sum, a count of vowels, a dictionary of letter counts. It does not work directly for things you cannot "subtract", like the maximum of the window, because when the maximum leaves you do not know what the new one is.
The shortcut
Find the leaver's index: for a window ending at i, the item leaving is nums[i - k]. Get that index right and the whole pattern is one line.
First window: hours 0 to 2
5 + 1 + 3 = 9. Best so far: 9.
The trap is an off-by-one leaver. Subtract nums[i - k + 1] instead and you remove an item that is still inside the window, while the very first item never leaves at all. The totals still look believable, and they are wrong.
Drills
Answer fast — trust the rule.
What does best_k_total([2, 7, 1, 4, 9, 3, 5], 2) return?
And best_k_total([2, 7, 1, 4, 9, 3, 5], 4)?
The window ending at position i has size k. Which item leaves when it slides to end at i + 1?
You want the most vowels in any 5-letter stretch of a long string. What does one slide do?
Remember
- Add the one coming in, subtract the one going out.
- Shortcut: for a window ending at
i, the leaver isnums[i - k]. - Trap: an off-by-one leaver, or trying to "subtract" a maximum.