🧩

DSA Patterns

When to reach for each pattern, plus the bug-free templates worth memorizing.

Pattern → signal

Pattern	Reach for it when…
Sliding window	Contiguous subarray/substring, "longest/shortest/at most k"
Two pointers	Sorted array, pair/triplet sums, in-place dedup
Fast & slow	Cycle detection, middle of list, O(1) space on linked list
Binary search	Sorted input, or "minimize the max / maximize the min" (search the answer)
Hashing	"Have I seen this?", counts, complements (two-sum)
Prefix sum	Many range-sum queries, subarray-sum-equals-k
BFS	Shortest path in unweighted graph, level-order
DFS / backtracking	All paths, permutations/combinations, islands
Heap / top-K	"K largest/smallest", merge K lists, streaming median
Dynamic programming	Overlapping subproblems + optimal substructure ("count ways", "min cost")
Monotonic stack	Next greater/smaller element, histogram problems
Union-Find	Connectivity, number of components, cycle in undirected graph

Sliding window (variable)

let l = 0, best = 0;
for (let r = 0; r < n; r++) {
  add(arr[r]);
  while (invalid()) { remove(arr[l]); l++; }
  best = Math.max(best, r - l + 1);
}

Binary search (clean template)

let lo = 0, hi = n - 1;
while (lo <= hi) {
  const mid = lo + ((hi - lo) >> 1);
  if (a[mid] === t) return mid;
  if (a[mid] < t) lo = mid + 1;
  else hi = mid - 1;
}
return -1;

BFS (shortest path / levels)

const q = [start], seen = new Set([start]);
let steps = 0;
while (q.length) {
  for (let k = q.length; k > 0; k--) {
    const node = q.shift();
    for (const nx of neighbors(node))
      if (!seen.has(nx)) { seen.add(nx); q.push(nx); }
  }
  steps++;
}

Backtracking skeleton

function bt(path, choices) {
  if (done(path)) { res.push([...path]); return; }
  for (const c of choices) {
    path.push(c);
    bt(path, next(choices, c));
    path.pop();        // undo
  }
}

SDE-2 Launchpad · DSA Patterns cheat sheet