Stop 21 · Data Structures & AlgorithmsTopics · 13/17

Sliding Window

In short

"Longest substring", "max sum of K items", "smallest subarray with sum ≥ X": these turn from O(n²) into O(n) once you stop recomputing and start sliding.

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

The purple blob sips chai by a train window as trees slide past outside.

Think of it like this

Looking out of a train window

The window shows a fixed stretch of scenery. As the train moves, one new tree appears on the right and one old tree disappears on the left. You don't re-look at the whole view; you just notice what came in and what went out.

Watch it happen

Best sum of 3 days in a row

1/5First window covers days 0 to 2: 4 + 2 + 7 = 13. Best so far: 13.

The big ideas

What you need to know

Fixed-size window

When the window size K is given, add the new item and drop the old one at each step.

Variable-size window

Grow the right edge until a rule breaks, then shrink the left edge until it's fine again.

Track what's inside

A Map or Set remembers the window's contents, like character counts or the last index of each character.

Why it's O(n)

Each item enters the window once and leaves once, so total work is linear even with two pointers.

See it in code

Walk through the code

1function longestUnique(s: string): number {2  const lastSeen = new Map<string, number>();3  let left = 0;4  let best = 0;5 6  for (let right = 0; right < s.length; right++) {7    const ch = s[right];8    if (lastSeen.has(ch) && lastSeen.get(ch)! >= left) {9      left = lastSeen.get(ch)! + 1;   // shrink: jump past the repeat10    }11    lastSeen.set(ch, right);12    best = Math.max(best, right - left + 1);13  }14  return best;15}

1/4Remember where each character was last seen, and track the left edge and best length.

Longest substring without repeating characters, a very common interview question. longestUnique("abcabcbb") returns 3, for "abc".

Save yourself the pain

Common mistakes

Oops

Recomputing the window sum from scratch with an inner loop.

Do this instead

Keep a running value. Add what enters, subtract what leaves.

Oops

Moving left backwards when an old repeat is outside the window.

Do this instead

Only jump if the last position is >= left, as in the code above.

Your mission

Slide, don't recompute

~40 min

Quick check

A fixed window of size 3 has sum 13. It slides right: 4 leaves, 1 enters. What's the new sum?

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.