Algorithms & LeetCode

Coding interviews test your ability to solve problems efficiently. The good news: there are roughly 15 patterns that cover ~90% of interview questions. Master these patterns and you can tackle almost any problem.

How to Approach Coding Problems

The UMPIRE Method

Step	Action
Understand	Restate the problem, ask clarifying questions
Match	Which pattern does this fit?
Plan	Write pseudocode before coding
Implement	Code the solution
Review	Test with examples, edge cases
Evaluate	Analyze time/space complexity

Time Complexity Cheat Sheet

Complexity	Name	Example	10⁶ ops at 10⁸/sec
O(1)	Constant	Hash table lookup	instant
O(log n)	Logarithmic	Binary search	~20 µs
O(n)	Linear	Single loop	~10 ms
O(n log n)	Linearithmic	Merge sort	~200 ms
O(n²)	Quadratic	Nested loops	~3 hours ❌
O(2ⁿ)	Exponential	Brute force subsets	centuries ❌

---

The 15 Core Patterns

1. Two Pointers

Use when: Array/string problem, looking for a pair with a condition, removing elements in-place

Template:

function twoPointers(arr) {
  let left = 0;
  let right = arr.length - 1;

  while (left < right) {
    // Process pair
    if (condition) {
      left++;
    } else {
      right--;
    }
  }
}

Classic problems: Two Sum (sorted), Valid Palindrome, 3Sum, Container With Most Water

---

2. Sliding Window

Use when: Subarray/substring of fixed or variable size, running sum/max/min

Template:

function slidingWindow(arr, k) {
  let windowSum = 0;
  let maxSum = -Infinity;

  for (let i = 0; i < arr.length; i++) {
    windowSum += arr[i];  // Add right element

    if (i >= k) {
      windowSum -= arr[i - k];  // Remove left element
    }

    if (i >= k - 1) {
      maxSum = Math.max(maxSum, windowSum);
    }
  }

  return maxSum;
}

Classic problems: Maximum Sum Subarray of Size K, Longest Substring Without Repeating Characters, Minimum Window Substring

---

3. Fast & Slow Pointers

Use when: Linked list cycle detection, finding the middle of a list, palindrome detection

Template:

function hasCycle(head) {
  let slow = head;
  let fast = head;

  while (fast && fast.next) {
    slow = slow.next;
    fast = fast.next.next;

    if (slow === fast) return true;  // Cycle detected
  }

  return false;
}

Classic problems: Linked List Cycle, Happy Number, Find the Duplicate Number, Middle of Linked List

---

4. Binary Search

Use when: Sorted array, searching for a boundary/target, answer can be binary-searched (feasibility check)

Template:

function binarySearch(arr, target) {
  let left = 0;
  let right = arr.length - 1;

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

    if (arr[mid] === target) return mid;
    if (arr[mid] < target) left = mid + 1;
    else right = mid - 1;
  }

  return -1;  // Not found
}

// Search for leftmost position (lower bound)
function lowerBound(arr, target) {
  let left = 0;
  let right = arr.length;

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

  return left;
}

Classic problems: Binary Search, Search in Rotated Sorted Array, Find First and Last Position, Koko Eating Bananas, Capacity to Ship Packages

---

5. BFS (Breadth-First Search)

Use when: Shortest path in unweighted graph, level-by-level traversal, "minimum number of steps"

Template:

function bfs(graph, start, end) {
  const queue = [start];
  const visited = new Set([start]);
  let distance = 0;

  while (queue.length > 0) {
    const levelSize = queue.length;

    for (let i = 0; i < levelSize; i++) {
      const node = queue.shift();

      if (node === end) return distance;

      for (const neighbor of graph[node]) {
        if (!visited.has(neighbor)) {
          visited.add(neighbor);
          queue.push(neighbor);
        }
      }
    }

    distance++;
  }

  return -1;  // Not reachable
}

Classic problems: Number of Islands, Word Ladder, Rotting Oranges, Shortest Path in Binary Matrix

---

6. DFS (Depth-First Search)

Use when: Explore all paths, tree traversal, connected components, permutations/combinations

Template (recursive):

function dfs(node, visited, graph) {
  if (!node || visited.has(node)) return;

  visited.add(node);

  // Process node
  console.log(node);

  for (const neighbor of graph[node]) {
    dfs(neighbor, visited, graph);
  }
}

// DFS with backtracking
function backtrack(result, current, choices) {
  if (/* base case */) {
    result.push([...current]);
    return;
  }

  for (const choice of choices) {
    current.push(choice);  // Make choice
    backtrack(result, current, remainingChoices);
    current.pop();  // Undo choice
  }
}

Classic problems: Number of Islands, Clone Graph, Course Schedule, All Permutations, Subsets, Combination Sum

---

7. Dynamic Programming

Use when: Problem has overlapping subproblems + optimal substructure. Usually "min/max/count" problems.

Steps:

1. Define the state (what does dp[i] mean?)
2. Define the transition (how does dp[i] relate to dp[i-1]?)
3. Base case
4. Final answer

Template (1D):

function dp1D(n) {
  const dp = new Array(n + 1).fill(0);
  dp[0] = 1;  // Base case

  for (let i = 1; i <= n; i++) {
    dp[i] = dp[i - 1] + dp[i - 2];  // Transition
  }

  return dp[n];
}

// Often, optimize to O(1) space:
function dp1D_optimized(n) {
  let prev2 = 0, prev1 = 1;

  for (let i = 1; i < n; i++) {
    [prev2, prev1] = [prev1, prev1 + prev2];
  }

  return prev1;
}

Template (2D):

function dp2D(matrix) {
  const m = matrix.length;
  const n = matrix[0].length;
  const dp = Array.from({ length: m }, () => new Array(n).fill(0));

  // Fill base cases (row 0, col 0)
  // Fill rest using transitions
  for (let i = 1; i < m; i++) {
    for (let j = 1; j < n; j++) {
      dp[i][j] = Math.min(dp[i-1][j], dp[i][j-1]) + matrix[i][j];
    }
  }

  return dp[m-1][n-1];
}

Classic problems: Climbing Stairs, House Robber, Coin Change, Longest Common Subsequence, 0/1 Knapsack, Edit Distance

---

8. Heap / Priority Queue

Use when: "Top K", "K closest", streaming data, merging sorted lists

Template:

// Min-heap using a sorted array (for interviews, use a library in practice)
class MinHeap {
  constructor() { this.heap = []; }

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

  pop() {
    const min = this.heap[0];
    const last = this.heap.pop();
    if (this.heap.length > 0) {
      this.heap[0] = last;
      this.sinkDown(0);
    }
    return min;
  }

  peek() { return this.heap[0]; }
  size() { return this.heap.length; }

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

  sinkDown(i) {
    const n = this.heap.length;
    while (true) {
      let smallest = i;
      const left = 2 * i + 1;
      const right = 2 * i + 2;

      if (left < n && this.heap[left] < this.heap[smallest]) smallest = left;
      if (right < n && this.heap[right] < this.heap[smallest]) smallest = right;

      if (smallest !== i) {
        [this.heap[smallest], this.heap[i]] = [this.heap[i], this.heap[smallest]];
        i = smallest;
      } else break;
    }
  }
}

// Top K frequent elements
function topKFrequent(nums, k) {
  const freq = new Map();
  for (const n of nums) freq.set(n, (freq.get(n) || 0) + 1);

  const heap = new MinHeap();  // Min-heap of size k
  for (const [num, count] of freq) {
    heap.push([count, num]);
    if (heap.size() > k) heap.pop();
  }

  return heap.heap.map(([count, num]) => num);
}

Classic problems: Kth Largest Element, Top K Frequent Elements, Find Median from Data Stream, Merge K Sorted Lists, Task Scheduler

---

9. Graph Algorithms

Topological Sort (for dependency ordering):

function topoSort(numNodes, edges) {
  // Build adjacency list and in-degree count
  const adj = Array.from({ length: numNodes }, () => []);
  const inDegree = new Array(numNodes).fill(0);

  for (const [from, to] of edges) {
    adj[from].push(to);
    inDegree[to]++;
  }

  // Start with nodes that have no dependencies
  const queue = [];
  for (let i = 0; i < numNodes; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }

  const result = [];
  while (queue.length > 0) {
    const node = queue.shift();
    result.push(node);

    for (const neighbor of adj[node]) {
      inDegree[neighbor]--;
      if (inDegree[neighbor] === 0) queue.push(neighbor);
    }
  }

  // If result.length !== numNodes, there's a cycle
  return result.length === numNodes ? result : [];
}

Union-Find (Disjoint Set Union):

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

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

  union(x, y) {
    const px = this.find(x);
    const py = this.find(y);
    if (px === py) return false;

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

    this.components--;
    return true;
  }

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

---

LeetCode Problem Map

Easy Problems (Build Foundation)

#	Problem	Pattern	Time	Space
1	Two Sum	Hash Table	O(n)	O(n)
21	Merge Two Sorted Lists	Two Pointers	O(n+m)	O(1)
121	Best Time to Buy/Sell Stock	Sliding Window	O(n)	O(1)
141	Linked List Cycle	Fast/Slow	O(n)	O(1)
206	Reverse Linked List	Iterative	O(n)	O(1)
242	Valid Anagram	Hash Table	O(n)	O(1)
344	Reverse String	Two Pointers	O(n)	O(1)
704	Binary Search	Binary Search	O(log n)	O(1)

Medium Problems (Core Patterns)

#	Problem	Pattern	Time	Space
3	Longest Substring Without Repeating Chars	Sliding Window	O(n)	O(k)
15	3Sum	Two Pointers	O(n²)	O(1)
33	Search in Rotated Sorted Array	Binary Search	O(log n)	O(1)
39	Combination Sum	Backtracking	O(2ⁿ)	O(n)
46	Permutations	Backtracking	O(n!)	O(n)
53	Maximum Subarray	Kadane's Algo	O(n)	O(1)
56	Merge Intervals	Sorting	O(n log n)	O(n)
98	Validate BST	DFS	O(n)	O(h)
102	Binary Tree Level Order	BFS	O(n)	O(n)
200	Number of Islands	DFS/BFS	O(m×n)	O(m×n)
207	Course Schedule	Topo Sort	O(V+E)	O(V+E)
300	Longest Increasing Subsequence	DP	O(n log n)	O(n)
322	Coin Change	DP	O(amount×n)	O(amount)
347	Top K Frequent Elements	Heap	O(n log k)	O(n)
417	Pacific Atlantic Water Flow	DFS	O(m×n)	O(m×n)
424	Longest Repeating Char Replacement	Sliding Window	O(n)	O(1)

Hard Problems (Advanced)

#	Problem	Pattern	Time	Space
4	Median of Two Sorted Arrays	Binary Search	O(log(m+n))	O(1)
23	Merge K Sorted Lists	Heap	O(n log k)	O(k)
42	Trapping Rain Water	Two Pointers	O(n)	O(1)
72	Edit Distance	DP (2D)	O(m×n)	O(m×n)
76	Minimum Window Substring	Sliding Window	O(n)	O(k)
295	Find Median from Data Stream	Two Heaps	O(log n)	O(n)
297	Serialize/Deserialize BST	DFS	O(n)	O(n)
312	Burst Balloons	DP	O(n³)	O(n²)

---

Quick Reference: When to Use What

Signal	Pattern
Sorted array + find pair/triplet	Two Pointers
Contiguous subarray/substring with condition	Sliding Window
Linked list cycle, middle element	Fast/Slow Pointers
Sorted input + search	Binary Search
Tree/graph traversal by level	BFS
Tree/graph traversal by depth, all paths	DFS
Min/max count/ways	Dynamic Programming
Top/smallest K elements	Heap
Dependency ordering	Topological Sort
Connected components	Union-Find

See the individual pattern pages for full explanations and practice problems.