0
Challenge · 25Array & String Patterns
Sliding window: fixed size
Patternsused in ~95% of apps
You need the best block of k in a row. Recomputing each block from scratch is the obvious answer and it is far too slow. Sliding the window instead, add one, drop one, turns the same job into a single pass.
Core idea. Compute the first window the slow way, once. After that, move it one step at a time: add the value entering on the right, subtract the value leaving on the left. Each move costs one addition and one subtraction, not k of them.
poke it, drag it,
try to break it
try to break it
no slides here.
you drive.
you drive.
Playground, this isn't a screenshot
best sum of 3 in a row, [2, 1, 5, 1, 3, 2]
2
1
5
1
3
2
2
1
5
1
3
2
2
1
5
1
3
2
2
1
5
1
3
2
Four windows, but only one full addition. Every later window cost two operations instead of three.
↑ play a little first, then dig in