A lesson from the data structures and algorithms bootcamp. About a 11 minute read.
A sliding window is two pointers moving the same direction over a CONTIGUOUS run. It turns 'check every subarray', which is O(n^2) ranges before you have even looked inside one, into a single pass, and it does it by reusing the previous window's answer instead of recomputing it. That reuse is the whole technique.
For a window of exactly k items, compute the answer for the first k, then slide: add the element entering on the right, subtract the one leaving on the left, record the result, repeat. The point is that you never look inside the window again. The naive version recomputes a sum of k items at every one of n positions for O(n*k); the sliding version does two arithmetic operations per step for O(n), and the saving grows with k. Everything harder in this lesson is that same add-one-remove-one idea with a more interesting thing being maintained than a sum: a count, a frequency map, a maximum.
The rest of this lesson continues with 4 further sections. See the full curriculum.
Browse all 536 practice puzzles