Algorithms Cheatsheet

Big-O Reference

Sorting

Complexity Table

Merge Sort

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid  = arr.length >> 1;
  const L    = mergeSort(arr.slice(0, mid));
  const R    = mergeSort(arr.slice(mid));
  const res  = [];
  let l = 0, r = 0;
  while (l < L.length && r < R.length)
    res.push(L[l] <= R[r] ? L[l++] : R[r++]);
  return res.concat(L.slice(l), R.slice(r));
}

Quick Sort (in-place)

function quickSort(a, lo=0, hi=a.length-1) {
  if (lo >= hi) return;
  const p = partition(a, lo, hi);
  quickSort(a, lo, p-1);
  quickSort(a, p+1, hi);
}
function partition(a, lo, hi) {
  let i = lo - 1;
  for (let j = lo; j < hi; j++) if (a[j] <= a[hi]) [a[++i],a[j]]=[a[j],a[i]];
  [a[i+1],a[hi]] = [a[hi],a[i+1]]; return i+1;
}

Binary Search

Templates

// Exact match
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = (lo + hi) >> 1;
    if      (arr[mid] === target) return mid;
    else if (arr[mid] < target)   lo = mid + 1;
    else                          hi = mid - 1;
  }
  return -1;
}

// Left boundary (first index where arr[i] >= target)
function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = (lo + hi) >> 1;
    arr[mid] < target ? (lo = mid + 1) : (hi = mid);
  }
  return lo;
}

// Binary search on answer space
let lo = MIN_ANSWER, hi = MAX_ANSWER;
while (lo < hi) {
  const mid = (lo + hi) >> 1;
  isPossible(mid) ? (hi = mid) : (lo = mid + 1);
}
// lo is the minimum feasible answer

Graph Algorithms

BFS (shortest path)

function bfs(graph, start) {
  const dist    = new Map([[start, 0]]);
  const queue   = [start];
  while (queue.length) {
    const node = queue.shift();
    for (const nb of graph[node] || []) {
      if (!dist.has(nb)) {
        dist.set(nb, dist.get(node) + 1);
        queue.push(nb);
      }
    }
  }
  return dist;
}

DFS (recursive)

function dfs(graph, node, visited = new Set()) {
  if (visited.has(node)) return;
  visited.add(node);
  for (const nb of graph[node] || []) dfs(graph, nb, visited);
}

Dijkstra (weighted shortest path)

// Requires a min-heap. Using sorted array here for clarity (use real heap in interviews)
function dijkstra(graph, start) {
  const dist = new Map([[start, 0]]);
  const pq   = [[0, start]]; // [cost, node]
  while (pq.length) {
    pq.sort((a,b) => a[0]-b[0]);          // replace with heap
    const [cost, node] = pq.shift();
    if (cost > (dist.get(node) ?? Infinity)) continue;
    for (const [nb, w] of graph[node] || []) {
      const newCost = cost + w;
      if (newCost < (dist.get(nb) ?? Infinity)) {
        dist.set(nb, newCost);
        pq.push([newCost, nb]);
      }
    }
  }
  return dist;
}

Dynamic Programming

Top-Down (Memoisation)

function dp(state, memo = new Map()) {
  if (isBase(state)) return baseValue(state);
  if (memo.has(state)) return memo.get(state);
  const result = /* combine sub-results */;
  memo.set(state, result);
  return result;
}

Bottom-Up (Tabulation)

// 1D — coin change
const dp = new Array(amount + 1).fill(Infinity);
dp[0] = 0;
for (let i = 1; i <= amount; i++)
  for (const coin of coins)
    if (coin <= i) dp[i] = Math.min(dp[i], dp[i - coin] + 1);

// 2D — LCS
const dp2 = 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++)
    dp2[i][j] = s1[i-1]===s2[j-1] ? dp2[i-1][j-1]+1 : Math.max(dp2[i-1][j],dp2[i][j-1]);

Common DP Problems

Pattern Recognition