Stop 20 · Data Structures & AlgorithmsTopics · 7/8

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 — turns many O(n²) problems into O(n).

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

1Practice fixed-size and variable-size sliding window problems.
2Learn to identify sliding-window-shaped problems from the phrase 'contiguous subarray/substring.'
3Solve a few classics: longest substring without repeats, max sum subarray of size k.