64DSA Pro — Complete Reference

64.1 Complexity

Big-O / Θ / Ω

Growth scale

Amortised analysis

Average per operation over a sequence. Array push is O(1) amortised: occasional resize is O(n) but doubling means each element copied ~once over many pushes. Total cost / N = O(1).

Master Theorem (divide and conquer)

For T(n) = aT(n/b) + f(n):

• If f(n) = O(n^(log_b(a) − ε)): T(n) = Θ(n^log_b(a))
• If f(n) = Θ(n^log_b(a)): T(n) = Θ(n^log_b(a) · log n)
• If f(n) = Ω(n^(log_b(a) + ε)) and regularity: T(n) = Θ(f(n))

Mergesort: a=2, b=2, f=n → log₂(2)=1 → Θ(n log n). Binary search: a=1, b=2, f=1 → Θ(log n).

64.2 Data structures — implementations

Dynamic Array

class DynArray<T> {
  private buf: T[] = new Array(2);
  private len = 0;
  size() { return this.len; }
  get(i: number): T { if (i < 0 || i >= this.len) throw new Error(); return this.buf[i]; }
  set(i: number, v: T) { this.get(i); this.buf[i] = v; }
  push(v: T) {
    if (this.len === this.buf.length) this.resize(this.buf.length * 2);
    this.buf[this.len++] = v;
  }
  pop(): T | undefined {
    if (!this.len) return undefined;
    const v = this.buf[--this.len];
    this.buf[this.len] = undefined as any;
    if (this.len > 4 && this.len * 4 < this.buf.length) this.resize(this.buf.length / 2);
    return v;
  }
  private resize(cap: number) {
    const nb = new Array(cap);
    for (let i = 0; i < this.len; i++) nb[i] = this.buf[i];
    this.buf = nb;
  }
}

Doubly linked list

class DLL<T> {
  head: { val?: T; prev: any; next: any };
  tail: { val?: T; prev: any; next: any };
  size = 0;
  constructor() {
    this.head = { prev: null, next: null };
    this.tail = { prev: this.head, next: null };
    this.head.next = this.tail;
  }
  pushFront(val: T) { this.insertAfter(this.head, val); }
  pushBack(val: T)  { this.insertBefore(this.tail, val); }
  popFront(): T | undefined { return this.remove(this.head.next); }
  popBack():  T | undefined { return this.remove(this.tail.prev); }
  private insertAfter(node: any, val: T) {
    const n = { val, prev: node, next: node.next };
    node.next.prev = n; node.next = n; this.size++;
  }
  private insertBefore(node: any, val: T) { this.insertAfter(node.prev, val); }
  private remove(node: any): T | undefined {
    if (node === this.head || node === this.tail) return undefined;
    node.prev.next = node.next; node.next.prev = node.prev; this.size--;
    return node.val;
  }
}

Stack + Queue

class Stack<T> { private a: T[] = []; push(v:T){this.a.push(v)} pop(){return this.a.pop()} peek(){return this.a[this.a.length-1]} size(){return this.a.length} }

// Queue via two stacks (amortised O(1))
class Queue<T> {
  private inS: T[] = []; private outS: T[] = [];
  enqueue(v: T) { this.inS.push(v); }
  dequeue(): T | undefined {
    if (!this.outS.length) while (this.inS.length) this.outS.push(this.inS.pop()!);
    return this.outS.pop();
  }
  size() { return this.inS.length + this.outS.length; }
}

Min-Heap (binary heap)

class MinHeap<T> {
  private h: T[] = [];
  constructor(private cmp: (a: T, b: T) => number = (a: any, b: any) => a - b) {}
  size() { return this.h.length; }
  peek(): T | undefined { return this.h[0]; }
  push(v: T) {
    this.h.push(v);
    let i = this.h.length - 1;
    while (i > 0) {
      const p = (i - 1) >> 1;
      if (this.cmp(this.h[i], this.h[p]) < 0) { [this.h[i], this.h[p]] = [this.h[p], this.h[i]]; i = p; }
      else break;
    }
  }
  pop(): T | undefined {
    if (!this.h.length) return undefined;
    const top = this.h[0];
    const last = this.h.pop()!;
    if (this.h.length) {
      this.h[0] = last;
      let i = 0;
      const n = this.h.length;
      while (true) {
        const l = 2*i + 1, r = 2*i + 2;
        let s = i;
        if (l < n && this.cmp(this.h[l], this.h[s]) < 0) s = l;
        if (r < n && this.cmp(this.h[r], this.h[s]) < 0) s = r;
        if (s === i) break;
        [this.h[i], this.h[s]] = [this.h[s], this.h[i]]; i = s;
      }
    }
    return top;
  }
}
/* Max-heap: same but flip cmp sign. */

HashMap (separate chaining)

class HashMap<K, V> {
  private buckets: Array<Array<[K, V]>> = Array.from({ length: 16 }, () => []);
  private size = 0;
  private hash(k: K): number {
    const s = String(k);
    let h = 5381;
    for (let i = 0; i < s.length; i++) h = (h * 33) ^ s.charCodeAt(i);
    return (h >>> 0) % this.buckets.length;
  }
  set(k: K, v: V) {
    const b = this.buckets[this.hash(k)];
    for (const pair of b) if (pair[0] === k) { pair[1] = v; return; }
    b.push([k, v]); this.size++;
    if (this.size / this.buckets.length > 0.75) this.resize();
  }
  get(k: K): V | undefined {
    const b = this.buckets[this.hash(k)];
    for (const [kk, v] of b) if (kk === k) return v;
    return undefined;
  }
  delete(k: K): boolean {
    const b = this.buckets[this.hash(k)];
    for (let i = 0; i < b.length; i++) if (b[i][0] === k) { b.splice(i, 1); this.size--; return true; }
    return false;
  }
  private resize() {
    const old = this.buckets;
    this.buckets = Array.from({ length: old.length * 2 }, () => []);
    this.size = 0;
    for (const b of old) for (const [k, v] of b) this.set(k, v);
  }
}

Binary Search Tree

class BSTNode { constructor(public val: number, public left: BSTNode|null = null, public right: BSTNode|null = null) {} }

class BST {
  root: BSTNode | null = null;
  insert(v: number) { this.root = this.insertNode(this.root, v); }
  private insertNode(n: BSTNode|null, v: number): BSTNode {
    if (!n) return new BSTNode(v);
    if (v < n.val) n.left = this.insertNode(n.left, v);
    else if (v > n.val) n.right = this.insertNode(n.right, v);
    return n;
  }
  contains(v: number): boolean {
    let n = this.root;
    while (n) {
      if (v === n.val) return true;
      n = v < n.val ? n.left : n.right;
    }
    return false;
  }
  remove(v: number) { this.root = this.removeNode(this.root, v); }
  private removeNode(n: BSTNode|null, v: number): BSTNode|null {
    if (!n) return null;
    if (v < n.val) n.left = this.removeNode(n.left, v);
    else if (v > n.val) n.right = this.removeNode(n.right, v);
    else {
      if (!n.left) return n.right;
      if (!n.right) return n.left;
      let succ = n.right;
      while (succ.left) succ = succ.left;
      n.val = succ.val;
      n.right = this.removeNode(n.right, succ.val);
    }
    return n;
  }
}

Trie

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}
class Trie {
  root = new TrieNode();
  insert(word: string) {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) n.children.set(c, new TrieNode());
      n = n.children.get(c)!;
    }
    n.isEnd = true;
  }
  search(word: string, prefix = false): boolean {
    let n = this.root;
    for (const c of word) {
      if (!n.children.has(c)) return false;
      n = n.children.get(c)!;
    }
    return prefix ? true : n.isEnd;
  }
  startsWith(p: string): boolean { return this.search(p, true); }
}

Union-Find (full optimisations)

class DSU {
  parent: number[]; rank: number[]; components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(x: number, y: number): boolean {
    const rx = this.find(x), ry = this.find(y);
    if (rx === ry) return false;
    if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
    else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
    else { this.parent[ry] = rx; this.rank[rx]++; }
    this.components--;
    return true;
  }
}

Fenwick (Binary Indexed) Tree

class Fenwick {
  private bit: number[];
  constructor(n: number) { this.bit = new Array(n + 1).fill(0); }
  update(i: number, delta: number) {
    for (i++; i < this.bit.length; i += i & -i) this.bit[i] += delta;
  }
  query(i: number): number {
    let s = 0;
    for (i++; i > 0; i -= i & -i) s += this.bit[i];
    return s;
  }
  range(l: number, r: number): number { return this.query(r) - (l ? this.query(l - 1) : 0); }
}

Segment Tree (sum, with lazy propagation)

class SegTree {
  private n: number;
  private tree: number[];
  private lazy: number[];
  constructor(arr: number[]) {
    this.n = arr.length;
    this.tree = new Array(4 * this.n).fill(0);
    this.lazy = new Array(4 * this.n).fill(0);
    this.build(arr, 1, 0, this.n - 1);
  }
  private build(a: number[], v: number, l: number, r: number) {
    if (l === r) { this.tree[v] = a[l]; return; }
    const m = (l + r) >> 1;
    this.build(a, v*2, l, m); this.build(a, v*2+1, m+1, r);
    this.tree[v] = this.tree[v*2] + this.tree[v*2+1];
  }
  private push(v: number, l: number, r: number) {
    if (this.lazy[v]) {
      const m = (l + r) >> 1;
      this.tree[v*2]   += this.lazy[v] * (m - l + 1);
      this.tree[v*2+1] += this.lazy[v] * (r - m);
      this.lazy[v*2]   += this.lazy[v];
      this.lazy[v*2+1] += this.lazy[v];
      this.lazy[v] = 0;
    }
  }
  rangeAdd(ql: number, qr: number, delta: number, v=1, l=0, r=this.n-1) {
    if (qr < l || ql > r) return;
    if (ql <= l && r <= qr) { this.tree[v] += delta * (r - l + 1); this.lazy[v] += delta; return; }
    this.push(v, l, r);
    const m = (l + r) >> 1;
    this.rangeAdd(ql, qr, delta, v*2, l, m);
    this.rangeAdd(ql, qr, delta, v*2+1, m+1, r);
    this.tree[v] = this.tree[v*2] + this.tree[v*2+1];
  }
  rangeSum(ql: number, qr: number, v=1, l=0, r=this.n-1): number {
    if (qr < l || ql > r) return 0;
    if (ql <= l && r <= qr) return this.tree[v];
    this.push(v, l, r);
    const m = (l + r) >> 1;
    return this.rangeSum(ql, qr, v*2, l, m) + this.rangeSum(ql, qr, v*2+1, m+1, r);
  }
}

64.3 Sort algorithms (complete)

// Quicksort (Lomuto partition)
function quicksort(a: number[], lo = 0, hi = a.length - 1) {
  if (lo < hi) {
    const p = partition(a, lo, hi);
    quicksort(a, lo, p - 1);
    quicksort(a, p + 1, hi);
  }
}
function partition(a: number[], lo: number, hi: number): number {
  const pivot = a[hi]; let i = lo - 1;
  for (let j = lo; j < hi; j++) if (a[j] < pivot) { i++; [a[i], a[j]] = [a[j], a[i]]; }
  [a[i+1], a[hi]] = [a[hi], a[i+1]];
  return i + 1;
}
// O(n log n) avg, O(n²) worst (random pivot to avoid)

// Mergesort
function mergesort(a: number[]): number[] {
  if (a.length <= 1) return a;
  const m = a.length >> 1;
  return merge(mergesort(a.slice(0, m)), mergesort(a.slice(m)));
}
function merge(l: number[], r: number[]): number[] {
  const out: number[] = []; let i = 0, j = 0;
  while (i < l.length && j < r.length) out.push(l[i] <= r[j] ? l[i++] : r[j++]);
  return out.concat(l.slice(i)).concat(r.slice(j));
}
// O(n log n) guaranteed, stable, O(n) extra space

// Heapsort
function heapsort(a: number[]) {
  const n = a.length;
  for (let i = (n >> 1) - 1; i >= 0; i--) heapify(a, n, i);
  for (let i = n - 1; i > 0; i--) { [a[0], a[i]] = [a[i], a[0]]; heapify(a, i, 0); }
}
function heapify(a: number[], n: number, i: number) {
  let largest = i;
  const l = 2*i + 1, r = 2*i + 2;
  if (l < n && a[l] > a[largest]) largest = l;
  if (r < n && a[r] > a[largest]) largest = r;
  if (largest !== i) { [a[i], a[largest]] = [a[largest], a[i]]; heapify(a, n, largest); }
}
// O(n log n), in-place, NOT stable

// Counting sort (k = max value)
function countingSort(a: number[], k: number): number[] {
  const count = new Array(k + 1).fill(0);
  for (const x of a) count[x]++;
  const out: number[] = [];
  for (let v = 0; v <= k; v++) for (let i = 0; i < count[v]; i++) out.push(v);
  return out;
}
// O(n + k); great when k = O(n)

64.4 Binary search (variants)

// Classic
function binSearch(a: number[], t: number): number {
  let lo = 0, hi = a.length - 1;
  while (lo <= hi) {
    const m = (lo + hi) >> 1;
    if (a[m] === t) return m;
    if (a[m] < t) lo = m + 1; else hi = m - 1;
  }
  return -1;
}

// Leftmost occurrence (first index where a[i] >= t)
function lowerBound(a: number[], t: number): number {
  let lo = 0, hi = a.length;
  while (lo < hi) {
    const m = (lo + hi) >> 1;
    if (a[m] < t) lo = m + 1; else hi = m;
  }
  return lo;
}

// Search on answer: find smallest k such that check(k) is true
function searchOnAnswer(lo: number, hi: number, check: (k: number) => boolean): number {
  while (lo < hi) {
    const m = lo + ((hi - lo) >> 1);
    if (check(m)) hi = m; else lo = m + 1;
  }
  return lo;
}

64.5 String algorithms

KMP (Knuth-Morris-Pratt) — O(n + m) substring

function buildLPS(p: string): number[] {
  const lps = new Array(p.length).fill(0);
  let len = 0, i = 1;
  while (i < p.length) {
    if (p[i] === p[len]) { lps[i++] = ++len; }
    else if (len) len = lps[len - 1];
    else lps[i++] = 0;
  }
  return lps;
}
function kmp(t: string, p: string): number[] {
  const lps = buildLPS(p);
  const out: number[] = [];
  let i = 0, j = 0;
  while (i < t.length) {
    if (t[i] === p[j]) { i++; j++; if (j === p.length) { out.push(i - j); j = lps[j - 1]; } }
    else if (j) j = lps[j - 1];
    else i++;
  }
  return out;
}

Rabin-Karp (rolling hash) — average O(n + m)

function rabinKarp(t: string, p: string): number[] {
  const B = 257n, M = 1_000_000_007n;
  const out: number[] = [];
  const m = p.length, n = t.length;
  if (m > n) return out;
  let pHash = 0n, tHash = 0n, Bm = 1n;
  for (let i = 0; i < m; i++) {
    pHash = (pHash * B + BigInt(p.charCodeAt(i))) % M;
    tHash = (tHash * B + BigInt(t.charCodeAt(i))) % M;
    if (i < m - 1) Bm = (Bm * B) % M;
  }
  for (let i = 0; i <= n - m; i++) {
    if (pHash === tHash && t.slice(i, i + m) === p) out.push(i);
    if (i < n - m) {
      tHash = ((tHash - BigInt(t.charCodeAt(i)) * Bm) * B + BigInt(t.charCodeAt(i + m))) % M;
      tHash = (tHash + M) % M;
    }
  }
  return out;
}

Z-algorithm — O(n) string preprocessing

function zArray(s: string): number[] {
  const n = s.length, z = new Array(n).fill(0);
  let l = 0, r = 0;
  for (let i = 1; i < n; i++) {
    if (i < r) z[i] = Math.min(r - i, z[i - l]);
    while (i + z[i] < n && s[z[i]] === s[i + z[i]]) z[i]++;
    if (i + z[i] > r) { l = i; r = i + z[i]; }
  }
  return z;
}
// Use for: pattern matching (concat pattern + sep + text, find z[i] = pattern length)

64.6 Graph algorithms (complete code)

BFS shortest path (unweighted)

function bfsShortest(adj: number[][], src: number): number[] {
  const dist = new Array(adj.length).fill(-1);
  dist[src] = 0;
  const q: number[] = [src];
  while (q.length) {
    const u = q.shift()!;
    for (const v of adj[u]) if (dist[v] === -1) { dist[v] = dist[u] + 1; q.push(v); }
  }
  return dist;
}

DFS + cycle detection (directed)

function hasCycle(adj: number[][]): boolean {
  const WHITE = 0, GREY = 1, BLACK = 2;
  const color = new Array(adj.length).fill(WHITE);
  function dfs(u: number): boolean {
    color[u] = GREY;
    for (const v of adj[u]) {
      if (color[v] === GREY) return true;
      if (color[v] === WHITE && dfs(v)) return true;
    }
    color[u] = BLACK;
    return false;
  }
  for (let u = 0; u < adj.length; u++) if (color[u] === WHITE && dfs(u)) return true;
  return false;
}

Dijkstra (priority queue)

function dijkstra(adj: Map<number, [number, number][]>, src: number, n: number): number[] {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  const pq = new MinHeap<[number, number]>((a, b) => a[0] - b[0]);
  pq.push([0, src]);
  while (pq.size()) {
    const [d, u] = pq.pop()!;
    if (d > dist[u]) continue;
    for (const [v, w] of (adj.get(u) || [])) {
      if (dist[u] + w < dist[v]) { dist[v] = dist[u] + w; pq.push([dist[v], v]); }
    }
  }
  return dist;
}
// O((V + E) log V)

Bellman-Ford (handles negative weights, detects negative cycle)

function bellmanFord(edges: [number, number, number][], n: number, src: number): number[] | null {
  const dist = new Array(n).fill(Infinity);
  dist[src] = 0;
  for (let i = 0; i < n - 1; i++) {
    for (const [u, v, w] of edges) if (dist[u] + w < dist[v]) dist[v] = dist[u] + w;
  }
  // Negative cycle check
  for (const [u, v, w] of edges) if (dist[u] + w < dist[v]) return null;
  return dist;
}
// O(V * E)

Floyd-Warshall (all-pairs)

function floydWarshall(n: number, edges: [number, number, number][]): number[][] {
  const dist = Array.from({length: n}, () => new Array(n).fill(Infinity));
  for (let i = 0; i < n; i++) dist[i][i] = 0;
  for (const [u, v, w] of edges) dist[u][v] = w;
  for (let k = 0; k < n; k++)
    for (let i = 0; i < n; i++)
      for (let j = 0; j < n; j++)
        if (dist[i][k] + dist[k][j] < dist[i][j]) dist[i][j] = dist[i][k] + dist[k][j];
  return dist;
}
// O(V³)

Topological sort (Kahn's)

function topoSort(adj: number[][], n: number): number[] | null {
  const indeg = new Array(n).fill(0);
  for (let u = 0; u < n; u++) for (const v of adj[u]) indeg[v]++;
  const q: number[] = [];
  for (let u = 0; u < n; u++) if (indeg[u] === 0) q.push(u);
  const out: number[] = [];
  while (q.length) {
    const u = q.shift()!; out.push(u);
    for (const v of adj[u]) if (--indeg[v] === 0) q.push(v);
  }
  return out.length === n ? out : null; // null = cycle
}

Kruskal (MST)

function kruskal(edges: [number, number, number][], n: number): [number, [number,number][]] {
  edges.sort((a, b) => a[2] - b[2]);
  const dsu = new DSU(n);
  const mst: [number, number][] = []; let total = 0;
  for (const [u, v, w] of edges) {
    if (dsu.union(u, v)) { mst.push([u, v]); total += w; if (mst.length === n - 1) break; }
  }
  return [total, mst];
}

Tarjan's SCC

function tarjanSCC(adj: number[][]): number[][] {
  const n = adj.length;
  const idx = new Array(n).fill(-1), low = new Array(n).fill(0), onStack = new Array(n).fill(false);
  const stack: number[] = [];
  const sccs: number[][] = [];
  let counter = 0;
  function dfs(u: number) {
    idx[u] = low[u] = counter++;
    stack.push(u); onStack[u] = true;
    for (const v of adj[u]) {
      if (idx[v] === -1) { dfs(v); low[u] = Math.min(low[u], low[v]); }
      else if (onStack[v]) low[u] = Math.min(low[u], idx[v]);
    }
    if (low[u] === idx[u]) {
      const scc: number[] = [];
      while (true) {
        const w = stack.pop()!; onStack[w] = false; scc.push(w);
        if (w === u) break;
      }
      sccs.push(scc);
    }
  }
  for (let u = 0; u < n; u++) if (idx[u] === -1) dfs(u);
  return sccs;
}

64.7 Dynamic Programming — complete catalogue with code

1D DP — climbing stairs / fib

function climb(n: number): number {
  if (n < 2) return n;
  let a = 1, b = 1;
  for (let i = 2; i <= n; i++) [a, b] = [b, a + b];
  return b;
}

House robber

function rob(nums: number[]): number {
  let prev = 0, curr = 0;
  for (const n of nums) [prev, curr] = [curr, Math.max(curr, prev + n)];
  return curr;
}

0/1 knapsack

function knapsack01(w: number[], v: number[], W: number): number {
  const dp = new Array(W + 1).fill(0);
  for (let i = 0; i < w.length; i++)
    for (let j = W; j >= w[i]; j--)
      dp[j] = Math.max(dp[j], dp[j - w[i]] + v[i]);
  return dp[W];
}

Unbounded knapsack (coin change ways)

function coinChangeWays(coins: number[], amount: number): number {
  const dp = new Array(amount + 1).fill(0);
  dp[0] = 1;
  for (const c of coins) for (let a = c; a <= amount; a++) dp[a] += dp[a - c];
  return dp[amount];
}

LCS (Longest Common Subsequence)

function lcs(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
  for (let i = 1; i <= m; i++) for (let j = 1; j <= n; j++) {
    dp[i][j] = s1[i-1] === s2[j-1] ? dp[i-1][j-1] + 1 : Math.max(dp[i-1][j], dp[i][j-1]);
  }
  return dp[m][n];
}

Edit distance (Levenshtein)

function editDist(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp = Array.from({length: m+1}, () => new Array(n+1).fill(0));
  for (let i = 0; i <= m; i++) dp[i][0] = i;
  for (let j = 0; j <= n; j++) dp[0][j] = j;
  for (let i = 1; i <= m; i++) for (let j = 1; j <= n; j++) {
    if (s1[i-1] === s2[j-1]) dp[i][j] = dp[i-1][j-1];
    else dp[i][j] = 1 + Math.min(dp[i-1][j], dp[i][j-1], dp[i-1][j-1]);
  }
  return dp[m][n];
}

LIS (Longest Increasing Subsequence) — O(n log n)

function lis(nums: number[]): number {
  const tails: number[] = [];
  for (const x of nums) {
    let lo = 0, hi = tails.length;
    while (lo < hi) { const m = (lo + hi) >> 1; if (tails[m] < x) lo = m + 1; else hi = m; }
    tails[lo] = x;
  }
  return tails.length;
}

Buy/sell stock (multiple transactions, with cooldown)

function maxProfitCooldown(prices: number[]): number {
  let hold = -Infinity, sold = 0, rest = 0;
  for (const p of prices) {
    const prevSold = sold;
    sold = hold + p;
    hold = Math.max(hold, rest - p);
    rest = Math.max(rest, prevSold);
  }
  return Math.max(sold, rest);
}

Matrix chain multiplication (interval DP)

function matChain(dims: number[]): number {
  const n = dims.length - 1;
  const dp = Array.from({length: n}, () => new Array(n).fill(0));
  for (let len = 2; len <= n; len++) {
    for (let i = 0; i + len - 1 < n; i++) {
      const j = i + len - 1;
      dp[i][j] = Infinity;
      for (let k = i; k < j; k++) {
        dp[i][j] = Math.min(dp[i][j], dp[i][k] + dp[k+1][j] + dims[i]*dims[k+1]*dims[j+1]);
      }
    }
  }
  return dp[0][n-1];
}

TSP (bitmask DP, N ≤ 20)

function tsp(dist: number[][]): number {
  const n = dist.length;
  const INF = Infinity;
  const dp = Array.from({length: 1 << n}, () => new Array(n).fill(INF));
  dp[1][0] = 0;
  for (let mask = 1; mask < (1 << n); mask++) {
    for (let u = 0; u < n; u++) {
      if (!(mask & (1 << u))) continue;
      for (let v = 0; v < n; v++) {
        if (mask & (1 << v)) continue;
        const nm = mask | (1 << v);
        dp[nm][v] = Math.min(dp[nm][v], dp[mask][u] + dist[u][v]);
      }
    }
  }
  const full = (1 << n) - 1;
  let best = INF;
  for (let u = 1; u < n; u++) best = Math.min(best, dp[full][u] + dist[u][0]);
  return best;
}

64.8 Backtracking template + 8 problems

// Template
function backtrack(state: any, choices: any[], result: any[]) {
  if (isSolution(state)) { result.push(cloneState(state)); return; }
  for (const c of choices) {
    if (!isValid(state, c)) continue;
    makeChoice(state, c);
    backtrack(state, getChoices(state), result);
    undoChoice(state, c);
  }
}

Permutations

function permutations(nums: number[]): number[][] {
  const out: number[][] = [], used = new Array(nums.length).fill(false), path: number[] = [];
  function bt() {
    if (path.length === nums.length) { out.push([...path]); return; }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue;
      used[i] = true; path.push(nums[i]);
      bt();
      path.pop(); used[i] = false;
    }
  }
  bt();
  return out;
}

Subsets (power set)

function subsets(nums: number[]): number[][] {
  const out: number[][] = [];
  function bt(start: number, path: number[]) {
    out.push([...path]);
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]); bt(i + 1, path); path.pop();
    }
  }
  bt(0, []);
  return out;
}

N-Queens count

function totalNQueens(n: number): number {
  const cols = new Set<number>(), diag1 = new Set<number>(), diag2 = new Set<number>();
  let count = 0;
  function bt(r: number) {
    if (r === n) { count++; return; }
    for (let c = 0; c < n; c++) {
      if (cols.has(c) || diag1.has(r - c) || diag2.has(r + c)) continue;
      cols.add(c); diag1.add(r - c); diag2.add(r + c);
      bt(r + 1);
      cols.delete(c); diag1.delete(r - c); diag2.delete(r + c);
    }
  }
  bt(0);
  return count;
}

Word search (DFS in grid)

function exist(board: string[][], word: string): boolean {
  const R = board.length, C = board[0].length;
  function dfs(i: number, j: number, k: number): boolean {
    if (k === word.length) return true;
    if (i < 0 || j < 0 || i >= R || j >= C || board[i][j] !== word[k]) return false;
    const save = board[i][j]; board[i][j] = '#';
    const found = dfs(i+1,j,k+1) || dfs(i-1,j,k+1) || dfs(i,j+1,k+1) || dfs(i,j-1,k+1);
    board[i][j] = save;
    return found;
  }
  for (let i = 0; i < R; i++) for (let j = 0; j < C; j++) if (dfs(i, j, 0)) return true;
  return false;
}

64.9 Greedy with correctness reasoning

Interval scheduling (max non-overlapping)

function maxIntervals(intervals: [number, number][]): number {
  intervals.sort((a, b) => a[1] - b[1]);  // by end time
  let count = 0, lastEnd = -Infinity;
  for (const [s, e] of intervals) {
    if (s >= lastEnd) { count++; lastEnd = e; }
  }
  return count;
}
// Proof sketch: exchange argument — any optimal solution can be transformed
// to choose the earliest-ending interval without losing count.

Huffman coding

Build a min-heap of (frequency, char). Repeatedly pop 2 smallest, merge into a parent with sum frequency, push back. Result tree gives prefix-free codes with minimum total length.

Jump game (can-reach)

function canJump(nums: number[]): boolean {
  let maxReach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > maxReach) return false;
    maxReach = Math.max(maxReach, i + nums[i]);
  }
  return true;
}

64.10 Bit manipulation catalogue

// Power of 2 check
const isPow2 = (x: number) => x > 0 && (x & (x - 1)) === 0;

// Count set bits (Brian Kernighan)
function popcount(x: number): number {
  let c = 0;
  while (x) { x &= x - 1; c++; }
  return c;
}

// Lowest set bit
const lowBit = (x: number) => x & -x;

// Reverse bits (32-bit)
function reverseBits(n: number): number {
  let result = 0;
  for (let i = 0; i < 32; i++) { result = (result << 1) | (n & 1); n >>>= 1; }
  return result >>> 0;
}

// Subsets via bitmask
function bitmaskSubsets<T>(arr: T[]): T[][] {
  const out: T[][] = [];
  const n = arr.length;
  for (let mask = 0; mask < (1 << n); mask++) {
    const subset: T[] = [];
    for (let i = 0; i < n; i++) if (mask & (1 << i)) subset.push(arr[i]);
    out.push(subset);
  }
  return out;
}

// XOR tricks
// a ^ a = 0; a ^ 0 = a → find single number in array of pairs:
function singleNumber(nums: number[]): number {
  return nums.reduce((acc, x) => acc ^ x, 0);
}

64.11 Math algorithms

GCD (Euclid)

function gcd(a: number, b: number): number { return b === 0 ? a : gcd(b, a % b); }
function lcm(a: number, b: number): number { return (a / gcd(a, b)) * b; }
// Extended Euclid (find x, y such that a*x + b*y = gcd)
function extGcd(a: number, b: number): [number, number, number] {
  if (b === 0) return [a, 1, 0];
  const [g, x1, y1] = extGcd(b, a % b);
  return [g, y1, x1 - Math.floor(a / b) * y1];
}

Modular exponentiation (a^b mod m)

function modPow(a: bigint, b: bigint, m: bigint): bigint {
  let result = 1n;
  a = a % m;
  while (b > 0n) {
    if (b & 1n) result = (result * a) % m;
    a = (a * a) % m;
    b >>= 1n;
  }
  return result;
}

Sieve of Eratosthenes

function sieve(n: number): number[] {
  const isPrime = new Array(n + 1).fill(true);
  isPrime[0] = isPrime[1] = false;
  for (let i = 2; i * i <= n; i++)
    if (isPrime[i]) for (let j = i * i; j <= n; j += i) isPrime[j] = false;
  const primes: number[] = [];
  for (let i = 2; i <= n; i++) if (isPrime[i]) primes.push(i);
  return primes;
}
// O(n log log n)

Combinatorics — nCr precomputed via Pascal

function pascalsTriangle(n: number): number[][] {
  const C = Array.from({length: n+1}, (_, i) => new Array(i+1).fill(1));
  for (let i = 2; i <= n; i++)
    for (let j = 1; j < i; j++)
      C[i][j] = C[i-1][j-1] + C[i-1][j];
  return C;
}

64.12 Geometry

Line segment intersection (CCW test)

function ccw(a: [number,number], b: [number,number], c: [number,number]): number {
  return (b[0]-a[0])*(c[1]-a[1]) - (b[1]-a[1])*(c[0]-a[0]);
}
function segmentsIntersect(a: any, b: any, c: any, d: any): boolean {
  return ccw(a,b,c) * ccw(a,b,d) < 0 && ccw(c,d,a) * ccw(c,d,b) < 0;
}

Convex hull (Graham scan)

function convexHull(points: [number,number][]): [number,number][] {
  points.sort((a, b) => a[0] - b[0] || a[1] - b[1]);
  const n = points.length;
  if (n < 3) return points;
  const lower: any[] = [];
  for (const p of points) {
    while (lower.length >= 2 && ccw(lower[lower.length-2], lower[lower.length-1], p) <= 0) lower.pop();
    lower.push(p);
  }
  const upper: any[] = [];
  for (let i = n - 1; i >= 0; i--) {
    const p = points[i];
    while (upper.length >= 2 && ccw(upper[upper.length-2], upper[upper.length-1], p) <= 0) upper.pop();
    upper.push(p);
  }
  return lower.slice(0, -1).concat(upper.slice(0, -1));
}

64.13 50+ Problems by Pattern (quick reference)

Two pointers

1. Two Sum II (sorted) — left/right converge
2. 3Sum — fix one, two-pointer rest
3. Trapping Rain Water — left/right max
4. Container With Most Water — area = (r-l) × min(h[l],h[r])
5. Remove Duplicates (in-place)
6. Palindrome — left/right
7. Move Zeros to end

Sliding window

1. Longest substring without repeats
2. Longest substring K distinct chars
3. Minimum window substring
4. Maximum sum subarray size K
5. Permutation in string (anagram window)
6. Longest repeating char replacement

HashMap / Set

1. Two Sum
2. Group Anagrams
3. Top K frequent
4. Subarray sum equals K (prefix sums in map)
5. Longest consecutive sequence
6. First non-repeating character

Stack

1. Valid Parentheses
2. Daily Temperatures (monotonic)
3. Largest Rectangle in Histogram (monotonic)
4. Evaluate Reverse Polish Notation
5. Basic Calculator (I, II, III)
6. Next greater element

Linked list

1. Reverse
2. Detect cycle (Floyd)
3. Find middle
4. Merge two sorted
5. Merge K sorted (heap)
6. LRU Cache
7. Add two numbers (digits as list)

Tree

1. Maximum depth
2. Level order traversal
3. Validate BST
4. LCA (BST + binary tree)
5. Serialize / Deserialize
6. Diameter
7. Path sum (I, II, III)
8. Symmetric tree

Graph

1. Number of islands (DFS/BFS/UF)
2. Course schedule (topo sort)
3. Clone graph
4. Pacific Atlantic water flow
5. Word ladder
6. Network delay time (Dijkstra)
7. Cheapest flights K stops

DP

1. Climbing stairs
2. House robber I/II/III
3. Coin change (min coins, ways)
4. Longest increasing subsequence
5. Edit distance
6. Word break
7. Decode ways
8. Best time to buy/sell stock (all variants)
9. Maximum product subarray
10. Partition equal subset sum

Backtracking

1. Permutations / Combinations
2. Subsets
3. Combination sum
4. Generate parentheses
5. Word search
6. N-Queens
7. Sudoku solver
8. Palindrome partitioning