Algorithms

What is an Algorithm?

An algorithm is a finite sequence of steps to solve a problem. Good algorithms are correct, efficient, and readable. Efficiency is measured with Big-O notation — a description of how time and space requirements grow as the input size n increases.

Big-O Analysis

Big-O captures the dominant term and drops constants. If an algorithm does 3n² + 5n + 100 operations, it's O(n²) — the lower-order terms and constant factor don't change how it scales.

Sorting Algorithms

Sorting is foundational — many problems become easier on sorted data. Know the O(n log n) algorithms deeply and understand when simpler O(n²) sorts are actually fine (small arrays, nearly-sorted data).

Merge Sort — O(n log n), Stable

Divide the array in half, recursively sort each half, then merge the two sorted halves. The merge step is the key — it compares the fronts of two sorted subarrays and picks the smaller element.

function mergeSort(arr) {
  if (arr.length <= 1) return arr;
  const mid   = Math.floor(arr.length / 2);
  const left  = mergeSort(arr.slice(0, mid));
  const right = mergeSort(arr.slice(mid));
  return merge(left, right);
}

function merge(left, right) {
  const result = [];
  let l = 0, r = 0;
  while (l < left.length && r < right.length) {
    result.push(left[l] <= right[r] ? left[l++] : right[r++]);
  }
  return result.concat(left.slice(l), right.slice(r));
}
// Time: O(n log n) always  Space: O(n)  Stable: yes

Quick Sort — O(n log n) avg, O(n²) worst

Pick a pivot, partition the array so everything less is to the left, everything greater to the right, then recursively sort each side. The partition step is in-place — quick sort uses O(log n) stack space.

function quickSort(arr, lo = 0, hi = arr.length - 1) {
  if (lo >= hi) return;
  const pivot = partition(arr, lo, hi);
  quickSort(arr, lo, pivot - 1);
  quickSort(arr, pivot + 1, hi);
}

function partition(arr, lo, hi) {
  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;
}
// Time: O(n log n) avg, O(n²) worst  Space: O(log n)  Not stable

Sorting Complexity Summary

Binary Search

Binary search finds an element in a sorted array in O(log n) by repeatedly halving the search space. The key invariant: the answer is always within [lo, hi] inclusive.

// Classic — find exact target
function binarySearch(arr, target) {
  let lo = 0, hi = arr.length - 1;
  while (lo <= hi) {
    const mid = lo + Math.floor((hi - lo) / 2);  // avoid integer overflow
    if      (arr[mid] === target) return mid;
    else if (arr[mid] < target)  lo = mid + 1;
    else                          hi = mid - 1;
  }
  return -1;
}

// Left boundary — first position where arr[i] >= target
function lowerBound(arr, target) {
  let lo = 0, hi = arr.length;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (arr[mid] < target) lo = mid + 1;
    else                   hi = mid;
  }
  return lo; // returns arr.length if all elements < target
}

// Binary search on the answer — when the search space is a range of values
// "Find minimum speed such that all packages arrive in time"
function minSpeed(packages, maxHours) {
  let lo = 1, hi = 1_000_000;
  while (lo < hi) {
    const mid = lo + Math.floor((hi - lo) / 2);
    if (canDeliver(packages, mid, maxHours)) hi = mid;
    else                                     lo = mid + 1;
  }
  return lo;
}

Recursion & Divide and Conquer

Recursion solves a problem by reducing it to one or more smaller instances of the same problem, with a base case that stops the recursion. Every recursive solution has an equivalent iterative one — but recursion is often clearer for tree and graph problems.

Divide and conquer is a specific pattern: split the input into independent subproblems, solve each recursively, and combine the results. Merge sort and quick sort are classic examples.

// Fibonacci — naive O(2ⁿ) vs memoised O(n)
function fib(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n]) return memo[n];
  return memo[n] = fib(n-1, memo) + fib(n-2, memo);
}

// Power — divide and conquer, O(log n)
function pow(base, exp) {
  if (exp === 0) return 1;
  const half = pow(base, Math.floor(exp / 2));
  return exp % 2 === 0 ? half * half : half * half * base;
}

// Generate all subsets (power set) — O(2ⁿ) subsets
function subsets(nums) {
  const result = [[]];
  for (const num of nums) {
    const newSubs = result.map(sub => [...sub, num]);
    result.push(...newSubs);
  }
  return result;
}

Graph Traversal — BFS & DFS

BFS (Breadth-First Search) explores level by level using a queue. It finds the shortest path in unweighted graphs. DFS (Depth-First Search) explores as deep as possible first using a stack (or recursion). It's better for detecting cycles, topological sorting, and connected components.

// BFS — shortest path from start to end in a grid
function shortestPath(grid, start, end) {
  const [R, C] = [grid.length, grid[0].length];
  const queue = [[...start, 0]]; // [row, col, distance]
  const visited = new Set([start.join(',')]);
  const dirs = [[0,1],[0,-1],[1,0],[-1,0]];

  while (queue.length) {
    const [r, c, dist] = queue.shift();
    if (r === end[0] && c === end[1]) return dist;
    for (const [dr, dc] of dirs) {
      const [nr, nc] = [r+dr, c+dc];
      const key = `${nr},${nc}`;
      if (nr>=0 && nr=0 && nc

// Classic DP: Longest Common Subsequence (LCS)
// dp[i][j] = LCS length of s1[0..i-1] and s2[0..j-1]
function lcs(s1, s2) {
  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];
}

// 0/1 Knapsack — can we achieve exactly target sum?
function canPartition(nums) {         // equal partition check
  const total = nums.reduce((a,b) => a+b, 0);
  if (total % 2 !== 0) return false;
  const target = total / 2;
  const dp = new Array(target + 1).fill(false);
  dp[0] = true;
  for (const num of nums) {
    for (let j = target; j >= num; j--) dp[j] = dp[j] || dp[j - num];
  }
  return dp[target];
}

// Coin change — minimum coins to make amount
function coinChange(coins, amount) {
  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);
    }
  }
  return dp[amount] === Infinity ? -1 : dp[amount];
}

// Activity selection — maximum non-overlapping intervals
function maxActivities(intervals) {
  intervals.sort((a, b) => a[1] - b[1]); // sort by end time
  let count = 0, end = -Infinity;
  for (const [start, finish] of intervals) {
    if (start >= end) { count++; end = finish; }
  }
  return count;
}

// Jump game — can you reach the last index?
function canJump(nums) {
  let reach = 0;
  for (let i = 0; i < nums.length; i++) {
    if (i > reach) return false;
    reach = Math.max(reach, i + nums[i]);
  }
  return true;
}

// Huffman coding, Dijkstra's shortest path, Prim's MST — all greedy