Sliding Window
How Sliding Window works
Before you start
- Open lesson
Write in place
A window is two indexes moving in the same direction, like read and write in Move Zeroes.
Why it matters
Monitoring systems recalculate fixed-length averages whenever a new sample arrives. Summing the full interval on every refresh repeats almost all the previous work and makes wide intervals expensive. For [1, 12, -5, -6, 50, 3] with k = 4, find the best average while processing each value only a constant number of times.
Real-world constraint
A moving average on a dashboard
Monitoring dashboards plot values like average response time over the last five minutes, refreshed every few seconds. Adding up every sample in the window on each refresh would cost time proportional to the window. Instead the running total adds the newest sample and subtracts the one that just fell out of the window: the same two operations you traced here.
Example
Maximum Average Subarray I
Return the maximum average of any contiguous subarray of nums with length exactly k.
- Input
- nums = [1, 12, -5, -6, 50, 3], k = 4
- Output
- 12.75
Approach 2 · Resolve the bottleneck
The idea
Keep one example in view
Maximum Average Subarray I
nums = [1, 12, -5, -6, 50, 3], k = 4→12.75
The baseline, Sum every window from scratch, is O(n · k) · O(1). The better model below keeps this exact input and removes that bottleneck.
For [1, 12, -5, -6, 50, 3], the first four values sum to 2 and the next four sum to 2 + 50 - 1 = 51. Reusing that overlap replaces the brute force's four additions per range with one addition and one subtraction.
The first four values [1, 12, -5, -6] sum to 2. Move the range one place: 50 enters and 1 leaves, so its sum becomes 2 + 50 - 1 = 51. There is no reason to add 12, -5, and -6 again.
Move once more: 3 enters and 12 leaves, changing the sum to 51 + 3 - 12 = 42. The largest sum was 51 for [12, -5, -6, 50], so divide by k = 4 only at the end to return 12.75.
Pro
The rest of this is on Pro
The idea above is free. The walkthrough, the cost, and the practice are on Pro.