Stop 21 · Data Structures & AlgorithmsTopics · 13/17

Sliding Window

In short

'Longest substring', 'max sum of k elements', 'smallest subarray with sum at least X'. When a question says contiguous, slide a window instead of checking every range.

A technique for efficiently processing contiguous subarrays/substrings by maintaining a moving 'window' instead of recomputing from scratch for every position.

The jaadu in a cricket cap slides a cardboard frame along a row of cricket balls.

Think of it like this

A batter's best 5-match run

To find a batter's best total over any 5 matches in a row, you don't re-add five scores each time. Add the new match, subtract the one that dropped off, and move on.

Watch it happen

Longest run without repeats in "abcabcbb"

left

right

1/5right moves over a, b and c. All new, so the window grows to length 3. best = 3.

The big ideas

What you need to know

Two pointers, one window

left and right mark the window's edges. Both only ever move forward.

Reuse, don't recompute

Update the window's sum or counts as items enter and leave, instead of starting fresh.

Fixed or growing

Fixed-size windows move together. Variable ones grow on the right and shrink on the left when a rule breaks.

O(n) even with a while inside

Each pointer crosses the array at most once, so total work is about 2n.

See it in code

Walk through the code

1function longestUnique(s) {2  const inWindow = new Set();3  let left = 0;4  let best = 0;5 6  for (let right = 0; right < s.length; right++) {7    while (inWindow.has(s[right])) {8      inWindow.delete(s[left]);9      left++;10    }11    inWindow.add(s[right]);12    best = Math.max(best, right - left + 1);13  }14  return best;15}

1/4A Set of what's in the window, its left edge, and the best length so far.

right moves n times and left moves at most n times in total, so time is O(n). The Set holds at most k distinct characters, so space is O(k).

Save yourself the pain

Common mistakes

Oops

Calling it O(n²) because there's a while loop inside the for loop.

Do this instead

Count total pointer moves, not nested loops. left never goes backwards, so it's O(n) overall.

Oops

Using sliding window on 'subsequence' questions.

Do this instead

Windows only work for contiguous ranges. Subsequences usually need DP.

Your mission

Slide through three

~40 min

Quick check

In the longestUnique function above, why is the time O(n) and not O(n²)?

Go deeper

1Solve 'maximum sum subarray of size k' using the sliding window technique.
2Practice both fixed-size and variable-size sliding window problems.
3Recognize sliding-window-shaped problems: anything about a contiguous subarray/substring with a constraint.