Skip to content

level 8 · Core techniques

Sliding Window

Reuse the last answer instead of recomputing — a window that slides, not restarts.

9 min 75 XP

what is it

Start here

Many problems ask about every run of k consecutive items: the highest-scoring 3 games in a row, the busiest hour of traffic, the best stretch of anything. The obvious way is to add up each run from scratch — but that redoes almost all the same work every time.

The sliding window notices something: when you move one step right, the new run is almost identical to the last one. Only two things changed — one value entered on the right, one value left on the left. So instead of re-adding k values, you add the newcomer and subtract the leaver. One plus, one minus, however big the window is.

Watch the highlighted window slide across the array. The running total updates with just those two changes each step, and we remember the best total we've seen. What would have been O(n·k) work collapses to a single O(n) pass.

real-life analogy

Picture it

A train window on a moving journey

As the train moves, you don't re-survey the entire view — almost all of it is the same as a second ago. One new field slides into view on one side, one slides out the other. You only ever notice the difference. A sliding window updates its total exactly like that.

interactive visualization

Watch it run

The target sets the window size k. Find the k-in-a-row with the biggest sum.

  1. 4
    0
  2. 2
    1
  3. 7
    2
  4. 1
    3
  5. 8
    4
  6. 3
    5
  7. 6
    6
  8. 5
    7

Start with the first 3 values. Their sum is 13. This is our first window — and, for now, the best we've seen.

step 01/9

  • comparing
  • in final place
  • found it
  • ruled out
1function maxWindow(a, k) {
2 let sum = 0;
3 for (let i = 0; i < k; i++) sum += a[i];
4 let best = sum;
5 for (let i = k; i < a.length; i++) {
6 sum += a[i] - a[i - k];
7 best = Math.max(best, sum);
8 }
9 return best;
10}

variables right now

k
3
windowSum
13
comparisons 0moves 0

the dry run · every step, in words

9 steps

complexity

What it costs

best case
O(n)
average
O(n)
worst case
O(n)
extra memory
O(1)

Each slide is one addition and one subtraction, no matter how wide the window — so the whole sweep is O(n), not O(n·k). And it keeps only a running total and the best seen, so O(1) extra space.

  • O(1)
  • O(log n)
  • O(n) · this one
  • O(n log n)
  • O(n²)
input size →work →

common mistakes

Common traps

  • Recomputing the whole window sum on every step.

    That's the slow O(n·k) version the technique exists to avoid. Add the entering value and subtract the leaving one — the rest of the window is unchanged.

  • Forgetting to subtract the value that leaves the window.

    If you only add the newcomer, the window grows instead of sliding. You must drop the value at the far-left of the old window.

  • Off-by-one errors on the window's edges.

    A window of size k starting at i covers i to i+k−1. Getting that boundary wrong is the most common bug — trace the first and last window by hand.

quiz

Check yourself

Three questions. Get them all right to finish the lesson.

+75 XP

01When the window slides one step right, what changes?

02What does the sliding window do to an O(n·k) brute-force solution?

03How much extra memory does the sliding window use here?

practice

Solve it on LeetCode

You've seen it run — now write it yourself. These are real LeetCode problems that use exactly this idea, from gentlest to toughest.