A lesson from the Algorithms & Patterns module of the bootcamp. About an 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. It does that 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 coming in on the right, subtract the one leaving on the left, record the result, and 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 operations per step, for O(n), and the savings grow with k. Everything harder in this lesson is the same add-one, remove-one idea, just tracking something more interesting 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 576 practice puzzles