Sliding WindowSliding Window
Sliding Window (Fixed Size)
Maintain an aggregate over every length-k contiguous subarray by adding the entering element and removing the leaving one, turning O(n·k) into O(n).
2
0
1
1
5
2
1
3
3
4
2
5
8
6
1
7
4
8
6
9
1/16Window size k=3. Sum the first window a[0..2] directly: 8. This is the only time we add k elements.
Current windowLeft the windowEnteringBest window
PseudocodeLearn Sliding Window (Fixed Size) →
1sum = a[0] + ... + a[k-1]; best = sum2for r in k .. n-1:3 sum += a[r] - a[r-k]4 best = max(best, sum)5return bestVariables
sum8
best8
k3
Complexity
best O(n)
avg O(n)
worst O(n)
space O(1)
Speed