The Idea: Slide, Don't Restart

Sliding Window, lesson 1 of 3

The Idea: Slide, Don't Restart

Reuse the previous window's work with a running sum, and learn to spot window problems.

10 min, 0 of 3 activities solved

View cheatsheet

Getting Python ready… examples can run in a moment.

Say you need the largest sum of any 3 consecutive numbers. The obvious way: for every start index, add up the next 3 numbers. That's O(n·k) work, and most of it is repeated.

Step through the windows of [2, 1, 5, 1, 3, 2] with k = 3 and watch what changes:

Walkthrough

Sliding a window of size 3

215132012345sum 8leftright
Step 1 of 5
window = 8
best = 8

First full window: 2 + 1 + 5 = 8, the only time we add up all k numbers.

window
enters
leaves
best

Neighbouring windows share k − 1 numbers. When the window slides one step, only two things change: one number enters on the right and one leaves on the left. So you update the sum in O(1) instead of re-adding k numbers. That's the whole trick, and it makes the scan O(n).

Example

Brute force vs sliding window

Same answer, about 90x less work. Try k = 500: brute force does even more work, the sliding version stays at about n steps.

How to recognise a window problem. Look for all three of these:

  1. The input is a sequence: an array or a string.
  2. The question is about a contiguous piece of it: a subarray or a substring.
  3. You want the longest / shortest / max / min / count of such pieces that satisfy some rule ("at most k distinct", "sum ≥ target", "no repeats").

Windows come in two flavours:

  • Fixed size: "every window of length k". The window just slides. (This lesson.)
  • Variable size: "the longest substring such that…". The window grows and shrinks. (Next lesson.)

The fixed-size template. Walk right over every index. Add nums[right]. Once the window is longer than k, remove nums[right - k]. Once it has exactly k items (right >= k - 1), record an answer. No special case for the first window.

Example

Fixed window, one loop

The window covering right is nums[right - k + 1 : right + 1]. Swap the sum for a count (of vowels, of negatives…) and the same loop answers many "every window of size k" questions.

Quiz

What does this print?

Quiz

Which of these is a natural sliding window problem?

Exercise

Count the good windows

Write count_good_windows(nums, k, threshold) that returns how many windows of exactly k consecutive numbers have an average ≥ threshold.

Use a running sum: each step adds one number and removes one, so the whole scan is O(n). If k > len(nums) there are no windows.

count_good_windows([2, 2, 2, 2, 5, 5, 5, 8], 3, 4)
-> 3   # [2,5,5], [5,5,5], [5,5,8]