Sorting & Searching Algorithms

Complexity Cheatsheet

Algorithm        Best      Average   Worst     Space
─────────────────────────────────────────────────────
Bubble Sort      O(n)      O(n²)     O(n²)     O(1)
Insertion Sort   O(n)      O(n²)     O(n²)     O(1)
Selection Sort   O(n²)     O(n²)     O(n²)     O(1)
Merge Sort       O(n log n) O(n log n) O(n log n) O(n)
Quick Sort       O(n log n) O(n log n) O(n²)   O(log n)
Heap Sort        O(n log n) O(n log n) O(n log n) O(1)
Counting Sort    O(n+k)    O(n+k)    O(n+k)    O(k)
Radix Sort       O(nk)     O(nk)     O(nk)     O(n+k)
─────────────────────────────────────────────────────
Binary Search    O(1)      O(log n)  O(log n)  O(1)
Linear Search    O(1)      O(n)      O(n)      O(1)

Pick:
- General sort       → Quick Sort (in-place) or Merge Sort (stable)
- Nearly sorted      → Insertion Sort
- External sort      → Merge Sort
- Integer range      → Counting Sort / Radix Sort
- Priority queue     → Heap Sort

Key Implementations

// Binary Search — O(log n)
function binarySearch(arr: number[], target: number): number {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if (arr[mid] === target) return mid;
    if (arr[mid] < target) lo = mid + 1;
    else hi = mid - 1;
  }
  return -1;
}

// Merge Sort — O(n log n), stable
function mergeSort(arr: number[]): number[] {
  if (arr.length <= 1) return arr;
  const mid = arr.length >> 1;
  const left = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}
function merge(a: number[], b: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;
  while (i < a.length && j < b.length) {
    result.push(a[i] <= b[j] ? a[i++] : b[j++]);
  }
  return [...result, ...a.slice(i), ...b.slice(j)];
}

// Quick Sort — O(n log n) avg, in-place
function quickSort(arr: number[], lo = 0, hi = arr.length - 1): void {
  if (lo >= hi) return;
  const p = partition(arr, lo, hi);
  quickSort(arr, lo, p - 1);
  quickSort(arr, p + 1, hi);
}
function partition(arr: number[], lo: number, hi: number): number {
  const pivot = arr[hi];
  let i = lo - 1;
  for (let j = lo; j < hi; j++) {
    if (arr[j] <= pivot) { i++; [arr[i], arr[j]] = [arr[j], arr[i]]; }
  }
  [arr[i + 1], arr[hi]] = [arr[hi], arr[i + 1]];
  return i + 1;
}

Dynamic Programming Patterns

// DP template: define state, recurrence, base case, order

// 1D DP — Fibonacci / Climbing Stairs
function climbStairs(n: number): number {
  if (n <= 2) return n;
  let prev = 1, curr = 2;
  for (let i = 3; i <= n; i++) [prev, curr] = [curr, prev + curr];
  return curr;
}

// Coin Change — min coins to make amount
function coinChange(coins: number[], amount: number): number {
  const dp = Array(amount + 1).fill(Infinity);
  dp[0] = 0;
  for (let i = 1; i <= amount; i++) {
    for (const c of coins) {
      if (c <= i) dp[i] = Math.min(dp[i], dp[i - c] + 1);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// Longest Common Subsequence (2D DP)
function lcs(s1: string, s2: string): number {
  const m = s1.length, n = s2.length;
  const dp = Array.from({ length: m + 1 }, () => 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];
}

// 0/1 Knapsack
function knapsack(weights: number[], values: number[], cap: number): number {
  const n = weights.length;
  const dp = Array(cap + 1).fill(0);
  for (let i = 0; i < n; i++) {
    for (let w = cap; w >= weights[i]; w--) {  // iterate backwards
      dp[w] = Math.max(dp[w], dp[w - weights[i]] + values[i]);
    }
  }
  return dp[cap];
}