Sorting, Searching & Recursion

TL;DR

• Merge Sort O(n log n): Divide-and-conquer, stable, guaranteed performance.
• Quick Sort O(n log n) avg: In-place, fast in practice, partition-based.
• Binary Search: Halve search space each step → O(log n). Learn the template.
• Backtracking: Systematic exploration with undo — subsets, permutations, combinations.

Step 1: Sorting Algorithms

Sorting is the most-studied problem in computer science because so many other algorithms depend on sorted data — binary search, merge operations, duplicate detection, and interval scheduling all require sorting as a prerequisite. Understanding merge sort and quick sort isn't just academic: JavaScript's Array.sort() uses TimSort (a merge sort variant), and databases use external merge sort for large datasets. Interviewers test sorting knowledge to assess whether you understand divide-and-conquer, stability (preserving order of equal elements), and time-space tradeoffs.

Merge Sort — O(n log n) time, O(n) space

function mergeSort(arr: number[]): number[] {
  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: number[], right: number[]): number[] {
  const result: number[] = [];
  let i = 0, j = 0;

  while (i < left.length && j < right.length) {
    if (left[i] <= right[j]) {
      result.push(left[i++]);
    } else {
      result.push(right[j++]);
    }
  }

  return [...result, ...left.slice(i), ...right.slice(j)];
}

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

function quickSort(arr: number[], low = 0, high = arr.length - 1): number[] {
  if (low < high) {
    const pivotIndex = partition(arr, low, high);
    quickSort(arr, low, pivotIndex - 1);
    quickSort(arr, pivotIndex + 1, high);
  }
  return arr;
}

function partition(arr: number[], low: number, high: number): number {
  const pivot = arr[high]; // Choose last element as pivot
  let i = low - 1;        // Pointer for smaller elements

  for (let j = low; j < high; j++) {
    if (arr[j] < pivot) {
      i++;
      [arr[i], arr[j]] = [arr[j], arr[i]]; // Swap
    }
  }

  [arr[i + 1], arr[high]] = [arr[high], arr[i + 1]]; // Place pivot
  return i + 1;
}

Sorting Comparison

Step 2: Binary Search Templates

Binary search templates exist because despite being a "simple" algorithm, it has notoriously tricky edge cases — off-by-one errors, infinite loops from wrong mid calculation, and boundary conditions. Jon Bentley found that 90% of professional programmers couldn't write a correct binary search in 2 hours. These three templates (find exact, find boundary, search on answer) cover every binary search variant you'll encounter. Memorize them and you'll never get stuck on the boundary conditions again.

Template 1: Find exact target

function binarySearch(nums: number[], target: number): number {
  let left = 0, right = nums.length - 1;

  while (left <= right) {
    const mid = Math.floor((left + right) / 2);
    if (nums[mid] === target) return mid;
    if (nums[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;
}

Template 2: Find boundary (first true)

// Find first index where condition(nums[i]) is true
function findFirst(nums: number[], condition: (val: number) => boolean): number {
  let left = 0, right = nums.length;

  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (condition(nums[mid])) {
      right = mid;    // Mid might be the answer, search left
    } else {
      left = mid + 1; // Mid is not valid, search right
    }
  }

  return left; // First index where condition is true
}

// Example: First Bad Version
function firstBadVersion(n: number, isBad: (v: number) => boolean): number {
  let left = 1, right = n;
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    if (isBad(mid)) right = mid;
    else left = mid + 1;
  }
  return left;
}

Binary Search on Answer

// Koko eating bananas: minimum eating speed to finish in h hours
function minEatingSpeed(piles: number[], h: number): number {
  let left = 1;
  let right = Math.max(...piles);

  // Binary search on the answer (speed)
  while (left < right) {
    const mid = Math.floor((left + right) / 2);
    const hoursNeeded = piles.reduce((sum, pile) => sum + Math.ceil(pile / mid), 0);

    if (hoursNeeded <= h) {
      right = mid;    // Can eat slower
    } else {
      left = mid + 1; // Need to eat faster
    }
  }

  return left;
}

// Split array largest sum: minimize the largest subarray sum with k splits
function splitArray(nums: number[], k: number): number {
  let left = Math.max(...nums);
  let right = nums.reduce((a, b) => a + b);

  while (left < right) {
    const mid = Math.floor((left + right) / 2);

    // Can we split into ≤ k groups where each sum ≤ mid?
    let groups = 1, currentSum = 0;
    for (const num of nums) {
      if (currentSum + num > mid) {
        groups++;
        currentSum = num;
      } else {
        currentSum += num;
      }
    }

    if (groups <= k) right = mid;
    else left = mid + 1;
  }

  return left;
}

Step 3: Recursion & Backtracking

Backtracking was formalized for constraint-satisfaction problems — placing N queens on a chessboard, solving Sudoku, generating all valid parentheses combinations. The key insight: instead of generating all 2^n or n! possibilities and filtering, you build the solution incrementally and abandon a path the moment it violates a constraint ("pruning"). This transforms problems from "generate everything" to "explore intelligently". Backtracking is behind every "generate all combinations/permutations/subsets" problem and appears in ~20% of medium/hard LeetCode problems.

Backtracking Template

function backtrack(
  result: any[],
  current: any[],
  choices: any[],
  start: number
) {
  // 1. Base case: found a valid solution
  if (/* condition */) {
    result.push([...current]); // Add copy of current state
    return;
  }

  // 2. Explore each choice
  for (let i = start; i < choices.length; i++) {
    // 3. Make choice
    current.push(choices[i]);

    // 4. Recurse (explore further)
    backtrack(result, current, choices, i + 1);

    // 5. Undo choice (backtrack)
    current.pop();
  }
}

Subsets (Power Set)

function subsets(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, current: number[]) {
    result.push([...current]); // Every state is a valid subset

    for (let i = start; i < nums.length; i++) {
      current.push(nums[i]);
      backtrack(i + 1, current);
      current.pop(); // Undo
    }
  }

  backtrack(0, []);
  return result;
}
// [1, 2, 3] → [[], [1], [1,2], [1,2,3], [1,3], [2], [2,3], [3]]

Permutations

function permute(nums: number[]): number[][] {
  const result: number[][] = [];

  function backtrack(current: number[], remaining: number[]) {
    if (remaining.length === 0) {
      result.push([...current]);
      return;
    }

    for (let i = 0; i < remaining.length; i++) {
      current.push(remaining[i]);
      backtrack(current, [...remaining.slice(0, i), ...remaining.slice(i + 1)]);
      current.pop();
    }
  }

  backtrack([], nums);
  return result;
}
// [1, 2, 3] → [[1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]]

Combinations

function combine(n: number, k: number): number[][] {
  const result: number[][] = [];

  function backtrack(start: number, current: number[]) {
    if (current.length === k) {
      result.push([...current]);
      return;
    }

    // Pruning: need (k - current.length) more, so stop early if not enough left
    for (let i = start; i <= n - (k - current.length) + 1; i++) {
      current.push(i);
      backtrack(i + 1, current);
      current.pop();
    }
  }

  backtrack(1, []);
  return result;
}
// combine(4, 2) → [[1,2], [1,3], [1,4], [2,3], [2,4], [3,4]]

N-Queens

function solveNQueens(n: number): string[][] {
  const result: string[][] = [];
  const board: string[][] = Array.from({ length: n }, () => new Array(n).fill('.'));

  const cols = new Set<number>();
  const diag1 = new Set<number>(); // row - col
  const diag2 = new Set<number>(); // row + col

  function backtrack(row: number) {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }

    for (let col = 0; col < n; col++) {
      if (cols.has(col) || diag1.has(row - col) || diag2.has(row + col)) continue;

      board[row][col] = 'Q';
      cols.add(col);
      diag1.add(row - col);
      diag2.add(row + col);

      backtrack(row + 1);

      board[row][col] = '.'; // Undo
      cols.delete(col);
      diag1.delete(row - col);
      diag2.delete(row + col);
    }
  }

  backtrack(0);
  return result;
}

Step 4: Important Data Structures

These three data structures (heap, trie, union-find) appear constantly in interviews because they each solve a category of problems that basic arrays/maps can't handle efficiently. Heaps give you O(1) access to min/max with O(log n) insertion — essential for "top K", priority scheduling, and Dijkstra's algorithm. Tries store strings with shared prefixes for autocomplete and spell-checking. Union-Find tracks dynamic connectivity ("are these two nodes connected?") with near-O(1) operations. Knowing when to reach for each one is what separates senior from junior problem-solvers.

Heap / Priority Queue

// JavaScript doesn't have a built-in heap, but here's a min-heap implementation
class MinHeap {
  private heap: number[] = [];

  push(val: number) {
    this.heap.push(val);
    this.bubbleUp(this.heap.length - 1);
  }

  pop(): number | undefined {
    if (this.heap.length === 0) return undefined;
    const min = this.heap[0];
    const last = this.heap.pop()!;
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.bubbleDown(0);
    }
    return min;
  }

  peek(): number | undefined {
    return this.heap[0];
  }

  get size(): number {
    return this.heap.length;
  }

  private bubbleUp(i: number) {
    while (i > 0) {
      const parent = Math.floor((i - 1) / 2);
      if (this.heap[parent] <= this.heap[i]) break;
      [this.heap[parent], this.heap[i]] = [this.heap[i], this.heap[parent]];
      i = parent;
    }
  }

  private bubbleDown(i: number) {
    while (true) {
      let smallest = i;
      const left = 2 * i + 1, right = 2 * i + 2;
      if (left < this.heap.length && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < this.heap.length && this.heap[right] < this.heap[smallest]) smallest = right;
      if (smallest === i) break;
      [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
      i = smallest;
    }
  }
}

// K-th Largest Element using min-heap of size k
function findKthLargest(nums: number[], k: number): number {
  const heap = new MinHeap();
  for (const num of nums) {
    heap.push(num);
    if (heap.size > k) heap.pop(); // Remove smallest, keep k largest
  }
  return heap.peek()!;
}

Trie (Prefix Tree)

class TrieNode {
  children = new Map<string, TrieNode>();
  isEnd = false;
}

class Trie {
  private root = new TrieNode();

  insert(word: string) {
    let node = this.root;
    for (const char of word) {
      if (!node.children.has(char)) {
        node.children.set(char, new TrieNode());
      }
      node = node.children.get(char)!;
    }
    node.isEnd = true;
  }

  search(word: string): boolean {
    const node = this.traverse(word);
    return node !== null && node.isEnd;
  }

  startsWith(prefix: string): boolean {
    return this.traverse(prefix) !== null;
  }

  private traverse(str: string): TrieNode | null {
    let node = this.root;
    for (const char of str) {
      if (!node.children.has(char)) return null;
      node = node.children.get(char)!;
    }
    return node;
  }
}

Union-Find (Disjoint Set)

class UnionFind {
  private parent: number[];
  private rank: number[];
  count: number; // Number of connected components

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n;
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // Path compression
    }
    return this.parent[x];
  }

  union(x: number, y: number): boolean {
    const rootX = this.find(x), rootY = this.find(y);
    if (rootX === rootY) return false; // Already connected

    // Union by rank
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY;
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX]++;
    }

    this.count--;
    return true;
  }

  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y);
  }
}

Step 5: Linked List Patterns

Linked lists were one of the first dynamic data structures (invented 1955–56 at RAND Corporation). They solve the problem of insertions/deletions in the middle of a sequence without shifting elements. In modern interviews, they test pointer manipulation skills — can you reverse pointers without losing references? Can you detect a cycle with O(1) space? The fast/slow pointer technique (Floyd's algorithm, 1967) is especially elegant: two pointers moving at different speeds will meet in a cycle, and the slow pointer finds the middle in one pass. These patterns also apply to any iterator/stream-based problem.

class ListNode {
  val: number;
  next: ListNode | null;
  constructor(val: number, next: ListNode | null = null) {
    this.val = val;
    this.next = next;
  }
}

// Reverse linked list — O(n)
function reverseList(head: ListNode | null): ListNode | null {
  let prev: ListNode | null = null;
  let current = head;

  while (current) {
    const next = current.next;
    current.next = prev;
    prev = current;
    current = next;
  }

  return prev;
}

// Detect cycle (Floyd's algorithm)
function hasCycle(head: ListNode | null): boolean {
  let slow = head, fast = head;

  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
    if (slow === fast) return true;
  }

  return false;
}

// Find middle of linked list
function middleNode(head: ListNode | null): ListNode | null {
  let slow = head, fast = head;
  while (fast && fast.next) {
    slow = slow!.next;
    fast = fast.next.next;
  }
  return slow;
}

// Merge two sorted lists
function mergeTwoLists(l1: ListNode | null, l2: ListNode | null): ListNode | null {
  const dummy = new ListNode(0);
  let current = dummy;

  while (l1 && l2) {
    if (l1.val <= l2.val) {
      current.next = l1;
      l1 = l1.next;
    } else {
      current.next = l2;
      l2 = l2.next;
    }
    current = current.next;
  }

  current.next = l1 ?? l2;
  return dummy.next;
}

Complexity Cheat Sheet

*With pointer to node

Interview Questions

1. When would you use Merge Sort over Quick Sort?

   • Merge Sort: guaranteed O(n log n), stable (preserves order of equal elements), good for linked lists (no random access needed). Quick Sort: faster in practice (cache-friendly, less overhead), O(1) extra space (in-place), but O(n²) worst case.

2. Explain binary search on the answer.

   • When the answer is a number in a range and you can verify if a value works, binary search the answer space. Examples: minimum speed (Koko), maximum minimum distance, minimum days. Check: "Can I achieve this with value X?" If yes, try smaller. If no, try bigger.

3. How does backtracking differ from brute force?

   • Backtracking prunes invalid paths early (if current state can't lead to solution, stop exploring). Brute force generates all possibilities then filters. Backtracking is still exponential but much faster in practice due to pruning.

4. When to use Union-Find vs DFS for connectivity?

   • Union-Find: dynamic connectivity (edges added over time), quick connected queries. DFS: static graph, full traversal needed, path finding. Union-Find: near O(1) per operation with path compression. DFS: O(V+E) per traversal.