Patternwise

Sliding Window

Grow the right edge, shrink the left, never restart.

Brute force
O(n²) — try every start, extend every end
With the pattern
O(n) — each index enters and leaves the window once
Extra space
O(k) — size of the alphabet / window state

In plain English

“Imagine reading a long necklace of colored beads through a cardboard tube you can stretch. You stretch the tube forward one bead at a time, and the moment you see a repeated color inside it, you pull the back end forward until the repeat is gone. The tube only ever moves forward, so you never re-read the necklace from scratch.”

Why it's fast

Brute force restarts at every left index and re-scans, re-counting the same characters over and over (O(n²) or worse). A window keeps a running summary (a set, a counter, a sum) and updates it incrementally: add one element on the right, remove one on the left. Because left and right only move forward, total work is O(n).

Spot it when the problem says…

  • contiguous subarray / substring
  • longest / shortest / maximum window such that…
  • at most k distinct characters
  • without repeating characters
  • window of size k
  • contains all characters of t (anagram / permutation)

Visualize

Longest substring without repeating characters

Given a string, find the length of the longest substring with all-unique characters.

0
a
1
b
2
c
3
a
4
b
5
c
6
b
7
b
8
x
9
y
10
z

seen (char → last index)

{}
01/34

Window is empty. It will only ever grow on the right and shrink on the left.

pythonline 3
1def longest_unique(s):2    seen = {}            # char -> last index3    left = best = 04    for right, ch in enumerate(s):5        if ch in seen and seen[ch] >= left:6            left = seen[ch] + 1   # jump past the duplicate7        seen[ch] = right8        best = max(best, right - left + 1)9    return best

variables

left
0
best
0

How to apply it

  1. 01Pick the state the window must track (set of chars, Counter, running sum).
  2. 02For each right, add s[right] to the state.
  3. 03While the window is invalid, remove s[left] from the state and left += 1.
  4. 04Window [left, right] is now valid — update the answer (right - left + 1).
  5. 05For fixed-size windows, instead slide both ends together once the size reaches k.

Variations you'll meet

Variable window: longest valid

The visualizer's example — longest substring without repeats. Shrink while invalid, then record.

python
def length_of_longest_substring(s: str) -> int:    seen = set()    left = best = 0    for right, ch in enumerate(s):        while ch in seen:            # window invalid: shrink            seen.remove(s[left])            left += 1        seen.add(ch)        best = max(best, right - left + 1)    return best

Variable window: shortest valid

Flip it: expand until valid, then shrink while still valid and record the minimum (Minimum Window Substring, Minimum Size Subarray Sum).

python
def min_subarray_len(target: int, nums: list[int]) -> int:    left = total = 0    best = float("inf")    for right, x in enumerate(nums):        total += x        while total >= target:       # valid: try to shrink            best = min(best, right - left + 1)            total -= nums[left]            left += 1    return 0 if best == float("inf") else best

Fixed-size window

Add nums[i], subtract nums[i-k]. Great for averages, anagram checks with a 26-length count array.

Monotonic deque window

When you need the max/min inside each window, keep a deque of candidate indices (Sliding Window Maximum).

Common mistakes

  • Off-by-one on window size: it's right - left + 1, not right - left.
  • Using if instead of while to shrink, leaving the window still invalid.
  • Updating the answer before the window is valid again.
  • Forgetting to delete a key from the Counter when its count hits 0, so len(counter) is wrong for 'k distinct'.
  • Using sliding window on arrays with negative numbers for sum targets — shrinking no longer guarantees the sum drops (use prefix sums).

Practice ladder

Easy → hard. Tick them off as you go.

0/8 solved
  1. 01Maximum Average Subarray I ↗Easy
  2. 02Longest Substring Without Repeating Characters ↗Medium
  3. 03Minimum Size Subarray Sum ↗Medium
  4. 04Fruit Into Baskets ↗Medium
  5. 05Longest Repeating Character Replacement ↗Medium
  6. 06Permutation in String ↗Medium
  7. 07Minimum Window Substring ↗Hard
  8. 08Sliding Window Maximum ↗Hard

Think you've got it?

Let the AI interviewer throw a Sliding Window problem at you and grade how you explain it.

Mock interview