DSA Crash Course
17 FAANG Patterns

Pattern 3: Sliding Window

Mark when done:

Deep Dive: Fixed vs Variable Window

Fixed Window (Max Sum of Size K)

arr = [1, 4, 2, 10, 2, 3, 1, 0, 20], k = 4:

Window [1,4,2,10] sum=17
       [4,2,10,2] sum=17-1+2=18
       [2,10,2,3] sum=18-4+3=17
       [10,2,3,1] sum=17-2+1=16
       [2,3,1,0]  sum=16-10+0=6
       [3,1,0,20] sum=6-2+20=24  <- MAX

Slide: remove leftmost, add rightmost. O(1) per step.

Variable Window (Longest with At Most K Distinct)

s = "eceba", k = 2:

R=0 'e'    window={e:1}      len=1  valid (1<=2)
R=1 'c'    window={e:1,c:1}  len=2  valid (2<=2)  best=2
R=2 'e'    window={e:2,c:1}  len=3  valid (2<=2)  best=3
R=3 'b'    window={e:2,c:1,b:1} INVALID (3>2)!
  shrink L: remove 'e'. window={e:1,c:1,b:1} still invalid
  shrink L: remove 'c'. window={e:1,b:1} valid. L=2
R=4 'a'    window={e:1,b:1,a:1} INVALID
  shrink L: remove 'e'. window={b:1,a:1} valid. best=3

Signal: Contiguous subarray/substring with max/min length, sum, or distinct count Template: sliding_window_variable() in templates.py

When to Use

  • "Longest/shortest subarray with condition"
  • "Subarray of size K" (fixed window)
  • "At most K distinct elements"
  • "Permutation/anagram in string"

Re-solve from Phase 1-2 (TIMED)

ProblemSourceTarget TimeDone?
Longest Substring Without RepeatsPhase 2.315 min[ ]
Minimum Window SubstringPhase 2.325 min[ ]
Find All Anagrams in a StringPhase 2.320 min[ ]

New Practice Problems

Add problems to solutions/ and enrich as needed.

First-time Recognition Signals

When you read a brand-new problem statement, this pattern is the right tool if you see:

  • "Longest / shortest contiguous subarray or substring satisfying X" — variable-window: expand right, shrink left while the predicate is violated.
  • "Subarray of fixed size K with maximum / minimum / average Y" — fixed window of size K, slid one step at a time.
  • "All anagrams of P in S" or "smallest window in S containing all chars of T" — frequency-map sliding window.
  • "At most K distinct elements / at most K of any one element" — the predicate is monotonic in window size, which is exactly what makes shrinking valid.
  • "Maximum number of consecutive Xs you can get by flipping at most K of them" — classic at-most-K window.

Anti-signals (looks like this pattern, isn't)

  • "Maximum subarray sum" of any size with negatives allowed — sliding window does not apply because there is no monotonic shrink predicate. Use Kadane's / DP.
  • "Pairs / triplets summing to T" — answers are not necessarily contiguous; use Two Pointers or HashMap.
  • "Subarray sum equals K" with negatives — looks like a window problem but the window cannot shrink monotonically; use Prefix Sum + HashMap.