Chapter 6: Advanced DSA — Trees, Graphs, Dynamic Programming, Backtracking

Rahul walked out of the Google Bangalore office feeling electric. He had crushed the array section. Two Sum? Done in under five minutes. Sliding window maximum? Optimized to O(n) with a deque. The interviewer had nodded, smiled, and said, "Good, let's move to the next problem."

Then she drew a binary tree on the whiteboard.

"Find the lowest common ancestor of two nodes," she said. "But do it without storing parent pointers."

Rahul froze. He knew what a binary tree was. He had read about LCA on LeetCode. But reading a solution and reconstructing it from scratch under pressure — with someone watching, with the clock ticking, with a crore-rupee offer hanging in the balance — those are different things entirely.

He stumbled through a recursive approach, got the base case wrong, corrected it, then lost track of his return values. The interviewer's smile faded. Twenty minutes later, she said, "Let's try a different problem."

Rahul didn't get the callback.

Here's the thing Rahul didn't know then, and what most mid-level engineers in India don't know now: the gap between a ₹30 LPA offer and a ₹60 LPA offer is not "more LeetCode." It is a specific set of data structures and algorithms that array-only candidates never touch. Trees. Graphs. Dynamic programming. Backtracking. These four topics are the gatekeeper. Master them, and you unlock the top of the market. Skip them, and you stay in the ₹20-30 LPA band forever.

This chapter will teach you each of these four topics — not as abstract computer science, but as interview weapons. You will learn the patterns, the code, the complexity analysis, and the heuristics that tell you which tool to reach for when the clock is running. By the end, you will see these "advanced" topics for what they really are: the same core patterns you already know, composed in ways you haven't practiced yet.

Trees: The Hierarchy That Runs Everything

Before you write a single line of tree code, understand this: trees are not a separate data structure you learn for interviews and forget. Trees are the DOM. Trees are your file system. Trees are the dependency graph of every node_modules folder you have ever cursed at. Trees are the abstract syntax tree that Babel and TypeScript use to transform your code. You already work with trees every day. You just haven't learned to manipulate them consciously.

A binary tree is a structure where each node has at most two children: left and right. That is the entire definition. Everything else — BSTs, AVL trees, red-black trees, heaps — is just a binary tree with extra rules bolted on.

class TreeNode {
  constructor(val, left = null, right = null) {
    this.val = val;
    this.left = left;
    this.right = right;
  }
}

That class is your entire data model. Every tree problem you will ever solve starts with these four lines. Memorize them. Type them from scratch until they flow from your fingers without thought. In an interview, you do not want to spend thirty seconds deciding whether to use a class or a plain object.

Traversals: The Three Ways to Walk a Tree

There are exactly three depth-first traversals you need to know. They differ only in when you process the current node relative to its children.

Inorder (Left → Root → Right): Visit the left subtree, then the current node, then the right subtree. For a Binary Search Tree, inorder traversal produces values in sorted order. This is the traversal you use when a problem asks for "sorted order" from a BST.

Preorder (Root → Left → Right): Process the current node first, then left, then right. This is the traversal for serialization — you record the root before its children so you can reconstruct the tree later. It is also the natural traversal for "copy this tree" problems.

Postorder (Left → Right → Root): Process children first, then the current node. This is the traversal for deletion and for any problem where you need information from both subtrees before you can decide something about the current node. Height of a tree, diameter, whether a tree is balanced — all postorder.

// Recursive — clean, readable, the version you write first
function inorder(root) {
  if (!root) return;
  inorder(root.left);
  console.log(root.val);
  inorder(root.right);
}

function preorder(root) {
  if (!root) return;
  console.log(root.val);
  preorder(root.left);
  preorder(root.right);
}

function postorder(root) {
  if (!root) return;
  postorder(root.left);
  postorder(root.right);
  console.log(root.val);
}

Recursive traversals are elegant, but they have a problem: they use the call stack. For a tree with 100,000 nodes, you risk a stack overflow. Interviewers at top-tier companies will ask you to write the iterative version. Here is the pattern:

// Iterative inorder — the one interviewers love to ask
function inorderIterative(root) {
  const result = [];
  const stack = [];
  let curr = root;

  while (curr || stack.length) {
    // Go left as far as possible
    while (curr) {
      stack.push(curr);
      curr = curr.left;
    }
    // Process node, then go right
    curr = stack.pop();
    result.push(curr.val);
    curr = curr.right;
  }
  return result;
}

// Iterative preorder — simpler than inorder
function preorderIterative(root) {
  if (!root) return [];
  const result = [];
  const stack = [root];

  while (stack.length) {
    const node = stack.pop();
    result.push(node.val);
    // Push right first so left is processed first (LIFO)
    if (node.right) stack.push(node.right);
    if (node.left) stack.push(node.left);
  }
  return result;
}

// Iterative postorder — trickiest of the three
// Use two stacks, or one stack with a "visited" flag
function postorderIterative(root) {
  if (!root) return [];
  const result = [];
  const stack = [root];
  const output = [];

  while (stack.length) {
    const node = stack.pop();
    output.push(node.val);
    if (node.left) stack.push(node.left);
    if (node.right) stack.push(node.right);
  }
  // output is root-right-left; reverse gives left-right-root
  return output.reverse();
}

The iterative postorder trick — using two stacks to avoid the complexity of tracking visited state — is a pattern you should internalize. It is not cleverness for its own sake. It is the difference between solving the problem in five minutes and getting stuck for twenty.

Binary Search Trees: The Rule That Changes Everything

A BST adds one constraint: for every node, all values in the left subtree are smaller, and all values in the right subtree are larger. That single rule gives you O(log n) search, insert, and delete — if the tree is balanced. If it is not balanced, a BST degenerates into a linked list, and your O(log n) becomes O(n).

This is the trap. Interviewers will give you a BST problem and expect you to exploit the ordering property. If you treat a BST like a generic binary tree and do a full traversal, you fail the optimization check.

// Search in a BST — O(h) where h is height
function searchBST(root, target) {
  let curr = root;
  while (curr) {
    if (curr.val === target) return curr;
    curr = target < curr.val ? curr.left : curr.right;
  }
  return null;
}

// Validate BST — the classic interview problem
// The trap: checking only immediate children is wrong.
// Every node in the left subtree must be less than the root.
function isValidBST(root, min = -Infinity, max = Infinity) {
  if (!root) return true;
  if (root.val <= min || root.val >= max) return false;
  return isValidBST(root.left, min, root.val) &&
         isValidBST(root.right, root.val, max);
}

The BST validation problem has destroyed more interviews than any other tree question. The naive approach — checking root.left.val < root.val < root.right.val — passes the sample test case and fails on the hidden one where a grandchild violates the constraint. The correct solution passes bounds down the recursion. This is the pattern: when a constraint must hold across the entire subtree, not just the immediate parent-child relationship, you pass bounds as parameters.

Lowest Common Ancestor: The Problem That Exposes Your Thinking

LCA is the problem Rahul failed. It is also the single best tree problem for demonstrating structured thinking. Here is the thought process an interviewer wants to see:

Step 1: Clarify. "Is this a binary tree or a BST? Do nodes have parent pointers? Can a node be an ancestor of itself?" These questions take ten seconds and show you are not jumping to code.

Step 2: State the approach before writing it. "I will use a recursive postorder traversal. At each node, I check if it matches either target. Then I check if the left and right subtrees contain the targets. If both subtrees return a non-null value, the current node is the LCA."

Step 3: Write clean code.

function lowestCommonAncestor(root, p, q) {
  // Base case: hit null, or found one of the targets
  if (!root || root === p || root === q) return root;

  const left = lowestCommonAncestor(root.left, p, q);
  const right = lowestCommonAncestor(root.right, p, q);

  // If both sides returned a node, this is the LCA
  if (left && right) return root;

  // Otherwise, propagate the non-null result upward
  return left || right;
}

Step 4: Analyze complexity. O(n) time — we visit each node once. O(h) space on the call stack, where h is the height of the tree. In the worst case of a skewed tree, O(n).

Step 5: Discuss the BST variant. "If this were a BST, I could do it in O(h) time by exploiting the ordering property — traverse down from the root, going left if both targets are smaller, right if both are larger, and stopping when they diverge."

That five-step structure — clarify, state approach, write code, analyze, discuss variants — is what separates a ₹60 LPA answer from a ₹30 LPA answer. The code itself is four lines. The thinking around it is what you are being paid for.

Serialization: Turning Trees Into Strings (and Back)

Serialization is the bridge between trees and everything else. You need it to send a tree over a network, store it in a database, or cache it in Redis. The standard approach is preorder traversal with a sentinel for null nodes.

function serialize(root) {
  const vals = [];
  function dfs(node) {
    if (!node) {
      vals.push('null');
      return;
    }
    vals.push(node.val);
    dfs(node.left);
    dfs(node.right);
  }
  dfs(root);
  return vals.join(',');
}

function deserialize(data) {
  const vals = data.split(',');
  let i = 0;
  function dfs() {
    if (vals[i] === 'null') {
      i++;
      return null;
    }
    const node = new TreeNode(Number(vals[i]));
    i++;
    node.left = dfs();
    node.right = dfs();
    return node;
  }
  return dfs();
}

The key insight: preorder serialization records the root before its children, which means you can reconstruct the tree in the same order you read the data. The null sentinels are not optional — without them, you cannot distinguish between different tree shapes that produce the same traversal.

BFS Serialization: The Level-Order Approach

The DFS approach above is the most common, but there is a second approach you must know: BFS-based serialization, also called level-order serialization. This is what LeetCode's "Serialize and Deserialize Binary Tree" (LC 297) expects in many solutions, and it is the format used by many online judges to represent trees as arrays.

The idea: traverse the tree level by level using a queue. For each node you process, write its value (or null if it is a null sentinel). For non-null nodes, enqueue both children — even if they are null. This produces a complete representation where the position in the array encodes the structure.

function serializeBFS(root) {
  if (!root) return 'null';
  const result = [];
  const queue = [root];

  while (queue.length) {
    const node = queue.shift();
    if (!node) {
      result.push('null');
      continue;
    }
    result.push(node.val);
    // Enqueue both children — even nulls — to preserve structure
    queue.push(node.left);
    queue.push(node.right);
  }
  return result.join(',');
}

function deserializeBFS(data) {
  const vals = data.split(',');
  if (vals[0] === 'null') return null;

  const root = new TreeNode(Number(vals[0]));
  const queue = [root];
  let i = 1;

  while (queue.length && i < vals.length) {
    const node = queue.shift();

    // Left child
    if (vals[i] !== 'null') {
      node.left = new TreeNode(Number(vals[i]));
      queue.push(node.left);
    }
    i++;

    // Right child
    if (i < vals.length && vals[i] !== 'null') {
      node.right = new TreeNode(Number(vals[i]));
      queue.push(node.right);
    }
    i++;
  }
  return root;
}

The BFS approach has one advantage over DFS: it naturally produces a compact representation for balanced trees. The disadvantage: for skewed trees, it writes many null sentinels — up to 2^h of them. In an interview, mention both approaches and explain the tradeoff. It shows you understand serialization as a concept, not just a memorized solution.

Binary Tree Maximum Path Sum: The Postorder Power Move

This problem — LeetCode 124 — is the tree problem that separates candidates who understand recursion from those who have only memorized traversal patterns. The question: "Given a binary tree, find the maximum path sum. A path is any sequence of nodes from some starting node to any node in the tree along parent-child connections. The path must contain at least one node."

The trap: the maximum path might not pass through the root. It could be entirely inside the left subtree, or the right subtree, or it could span across the root connecting the best path from the left with the best path from the right.

The insight: at each node, you need to compute two things. First, the maximum path sum that passes through this node and can continue upward to its parent — this is node.val + max(leftGain, rightGain, 0). Second, the maximum path sum that has this node as its highest point — this is node.val + leftGain + rightGain. You track the global maximum of the second value across all nodes.

This is a postorder problem because you need results from both children before you can compute the answer for the current node.

function maxPathSum(root) {
  let globalMax = -Infinity;

  function maxGain(node) {
    if (!node) return 0;

    // Postorder: compute gains from left and right subtrees first
    // If a subtree's gain is negative, we ignore it (take 0 instead)
    const leftGain = Math.max(maxGain(node.left), 0);
    const rightGain = Math.max(maxGain(node.right), 0);

    // The path that has this node as its highest point
    const pathSum = node.val + leftGain + rightGain;
    globalMax = Math.max(globalMax, pathSum);

    // The gain this node can contribute to its parent
    // Can only take one branch (left or right) plus the node itself
    return node.val + Math.max(leftGain, rightGain);
  }

  maxGain(root);
  return globalMax;
}

Walk through this on a small example. Consider a tree where the root is -10, left child is 9, right child is 20 with children 15 and 7. The left subtree contributes gain 9. The right subtree: node 15 contributes 15, node 7 contributes 7, so node 20 contributes 20 + max(15, 7) = 35 upward. At the root, the path spanning across is -10 + 9 + 35 = 34. But the path entirely inside the right subtree is 15 + 20 + 7 = 42. The global max tracks 42.

The Math.max(gain, 0) is the critical detail. If a subtree's best contribution is negative, you are better off not including it at all. This is the kind of edge case that separates a working solution from one that fails on trees with all negative values.

Trie: The Tree That Powers Autocomplete

A trie (pronounced "try," short for retrieval) is a tree where each node represents a character, and paths from root to leaf spell out words. Tries power autocomplete, spell checkers, IP routing tables, and the "did you mean?" feature on every search engine.

class TrieNode {
  constructor() {
    this.children = {};
    this.isEnd = false;
  }
}

class Trie {
  constructor() {
    this.root = new TrieNode();
  }

  insert(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) {
        node.children[ch] = new TrieNode();
      }
      node = node.children[ch];
    }
    node.isEnd = true;
  }

  search(word) {
    let node = this.root;
    for (const ch of word) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return node.isEnd;
  }

  startsWith(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return false;
      node = node.children[ch];
    }
    return true;
  }

  // Find all words with a given prefix — the autocomplete method
  autocomplete(prefix) {
    let node = this.root;
    for (const ch of prefix) {
      if (!node.children[ch]) return [];
      node = node.children[ch];
    }
    const results = [];
    this._collect(node, prefix, results);
    return results;
  }

  _collect(node, prefix, results) {
    if (node.isEnd) results.push(prefix);
    for (const [ch, child] of Object.entries(node.children)) {
      this._collect(child, prefix + ch, results);
    }
  }
}

Trie operations run in O(L) time where L is the length of the word — independent of how many words are stored. This is the property that makes them irreplaceable for prefix-based operations. A hash table gives you O(1) lookup for exact matches but cannot answer "find all words starting with 'pre'" without scanning every key.

Word Search II: Trie Meets Backtracking on a Grid

Word Search II (LeetCode 212) is the problem that forces you to combine two data structures. The question: "Given an m x n board of characters and a list of words, return all words that exist in the grid. Words can be constructed from letters of sequentially adjacent cells, where adjacent cells are horizontally or vertically neighboring. The same letter cell may not be used more than once in a word."

The naive approach — for each word, run DFS on the entire grid — is O(W * M * N * 4^L) where W is the number of words and L is the max word length. This times out on any non-trivial input.

The optimized approach: build a Trie from all the words, then run a single DFS from each cell on the board. As you traverse the grid, you simultaneously walk the Trie. If the current path does not match any Trie prefix, you prune immediately. When you hit a Trie node with isEnd = true, you have found a word.

function findWords(board, words) {
  const result = [];
  const rows = board.length;
  const cols = board[0].length;

  // Build Trie from the word list
  const root = new TrieNode();
  for (const word of words) {
    let node = root;
    for (const ch of word) {
      if (!node.children[ch]) node.children[ch] = new TrieNode();
      node = node.children[ch];
    }
    node.isEnd = true;
    node.word = word; // store the complete word at the terminal node
  }

  // DFS + Backtracking on the grid
  function dfs(r, c, trieNode) {
    // Out of bounds or cell already visited
    if (r < 0 || r >= rows || c < 0 || c >= cols || board[r][c] === '#') return;

    const ch = board[r][c];
    const nextNode = trieNode.children[ch];
    if (!nextNode) return; // prune: no word in the Trie has this prefix

    // Found a word
    if (nextNode.isEnd) {
      result.push(nextNode.word);
      nextNode.isEnd = false; // avoid duplicates
    }

    // Mark visited
    board[r][c] = '#';

    // Explore all four directions
    dfs(r + 1, c, nextNode);
    dfs(r - 1, c, nextNode);
    dfs(r, c + 1, nextNode);
    dfs(r, c - 1, nextNode);

    // Unchoose (backtrack)
    board[r][c] = ch;
  }

  // Start DFS from every cell
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      dfs(r, c, root);
    }
  }

  return result;
}

Three details make this solution production-grade. First, storing the complete word at the terminal Trie node avoids reconstructing the word from the path — you grab it in O(1) when you hit isEnd. Second, setting isEnd = false after finding a word prevents pushing the same word twice (the same word might be found from multiple starting cells). Third, marking the board cell with # and restoring it is the classic backtracking "choose-unchoose" pattern applied to a 2D grid.

The time complexity drops from O(W * M * N * 4^L) to O(M * N * 4^L) — we removed the factor of W entirely. For a board with 200 cells, 12 words of length 10, and 4^10 possible paths, the naive approach does 12x the work. The Trie approach does it once. This is the power of combining data structures: the Trie prunes the search space, and the backtracking explores it efficiently.

When to Use Which Tree Structure

Here is the heuristic you need in an interview. When you see a problem with hierarchical data, ask yourself these questions in order:

1. Is there an ordering constraint? If smaller-left, larger-right → BST.
2. Do I need prefix matching or autocomplete? → Trie.
3. Do I need fast min/max extraction? → Heap (a specialized tree).
4. Is it just hierarchical with no special rules? → Generic binary or n-ary tree.

If you cannot answer these four questions in under ten seconds, you have not practiced enough. Drill them until they are reflex.

Graphs: The Web That Connects Everything

The Moment Trees Stop Being Enough

Priya was a backend engineer at a Bangalore fintech startup. Her team was building a payment routing system — find the cheapest path to route a transaction through a network of partner banks. She modeled it as a tree. It worked for the first three partners. Then partner four connected to partner two, creating a cycle. The tree model broke. Transactions looped infinitely. The production incident lasted four hours.

Trees are graphs without cycles. The moment your data has cycles — and real-world data almost always does — you need graph algorithms. Social networks, road maps, payment networks, dependency resolution, recommendation engines, network topology — all graphs.

A graph is a set of vertices (nodes) connected by edges. That is the entire definition. Everything else — directed vs undirected, weighted vs unweighted, cyclic vs acyclic — is a property you check, not a different data structure.

// Adjacency list — the representation you will use 90% of the time
// Space: O(V + E). Iterating over neighbors: O(degree(v)).
const graph = {
  A: ['B', 'C'],
  B: ['A', 'D', 'E'],
  C: ['A', 'F'],
  D: ['B'],
  E: ['B', 'F'],
  F: ['C', 'E']
};

// Adjacency matrix — use only for dense graphs (E ≈ V²)
// Space: O(V²). Checking if edge exists: O(1).
const matrix = [
// A  B  C  D  E  F
  [0, 1, 1, 0, 0, 0], // A
  [1, 0, 0, 1, 1, 0], // B
  [1, 0, 0, 0, 0, 1], // C
  [0, 1, 0, 0, 0, 0], // D
  [0, 1, 0, 0, 0, 1], // E
  [0, 0, 1, 0, 1, 0]  // F
];

Use an adjacency list unless the problem explicitly requires constant-time edge-existence checks. The adjacency matrix burns O(V²) memory regardless of how sparse your graph is. For a graph with 10,000 nodes and 15,000 edges, the adjacency list uses memory proportional to 25,000 entries. The matrix uses 100 million. That is not a micro-optimization. That is the difference between your code running and your process being killed by the OOM killer.

BFS and DFS: The Two Ways to Explore a Graph

BFS and DFS are the map and filter of graph algorithms — fundamental operations that everything else builds on. The difference is the data structure you use to track what to visit next.

BFS uses a queue. It explores level by level, radiating outward from the start node. BFS finds the shortest path in an unweighted graph. Use BFS for: shortest path in a grid, level-order tree traversal, finding the minimum number of steps, "word ladder" problems, and anything involving "closest" or "nearest."

DFS uses a stack (or recursion, which is the call stack). It goes deep before going wide. Use DFS for: cycle detection, topological sorting, finding connected components, maze solving, and any problem where you need to explore all possibilities before backtracking.

// BFS — shortest path in an unweighted graph
function bfs(graph, start) {
  const visited = new Set([start]);
  const queue = [start];
  const result = [];

  while (queue.length) {
    const node = queue.shift(); // O(n) with array; use a proper queue in practice
    result.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        visited.add(neighbor);
        queue.push(neighbor);
      }
    }
  }
  return result;
}

// DFS — recursive (cleaner, but risks stack overflow on deep graphs)
function dfs(graph, node, visited = new Set()) {
  visited.add(node);
  console.log(node);
  for (const neighbor of graph[node]) {
    if (!visited.has(neighbor)) {
      dfs(graph, neighbor, visited);
    }
  }
}

// DFS — iterative (safer for large graphs)
function dfsIterative(graph, start) {
  const visited = new Set();
  const stack = [start];
  const result = [];

  while (stack.length) {
    const node = stack.pop();
    if (visited.has(node)) continue;
    visited.add(node);
    result.push(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        stack.push(neighbor);
      }
    }
  }
  return result;
}

A note on queue.shift(): in JavaScript, Array.shift() is O(n) because it reindexes every element. For a real BFS on a large graph, use a linked-list-based queue or maintain a head pointer instead of shifting. In an interview, mention this. It shows you understand your language's performance characteristics beyond the algorithm.

Number of Islands: The Graph Problem Everyone Asks

Number of Islands (LeetCode 200) is the single most-asked graph problem in FAANG interviews. The question: "Given an m x n 2D binary grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and formed by connecting adjacent lands horizontally or vertically."

The grid is an implicit graph. Each cell is a node. Adjacent land cells (up, down, left, right) are connected by edges. Counting islands is counting connected components of land cells. You can solve this with DFS, BFS, or Union-Find. You must know all three — interviewers will ask you to compare them.

Approach 1: DFS (simplest, most common)

function numIslandsDFS(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    // Out of bounds or water — stop exploring
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] === '0') return;

    // Sink the land: mark as visited by changing to water
    grid[r][c] = '0';

    // Explore all four directions
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c); // sink the entire island
      }
    }
  }
  return count;
}

The "sink the island" pattern — mutating the grid to mark visited cells — is the cleanest way to avoid a separate visited set. It modifies the input, which you should flag to the interviewer. If they object, use a visited 2D array or a Set of encoded coordinates (r * cols + c).

Approach 2: BFS (queue-based, avoids recursion depth issues)

function numIslandsBFS(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
  const directions = [[1, 0], [-1, 0], [0, 1], [0, -1]];

  function bfs(r, c) {
    const queue = [[r, c]];
    grid[r][c] = '0'; // mark visited immediately when enqueuing

    while (queue.length) {
      const [row, col] = queue.shift();
      for (const [dr, dc] of directions) {
        const nr = row + dr;
        const nc = col + dc;
        if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === '1') {
          grid[nr][nc] = '0'; // mark visited
          queue.push([nr, nc]);
        }
      }
    }
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++;
        bfs(r, c);
      }
    }
  }
  return count;
}

The critical detail in BFS: mark a cell as visited when you enqueue it, not when you dequeue it. If you mark on dequeue, the same cell can be enqueued multiple times from different neighbors before it is processed, blowing up your queue and potentially causing TLE.

Approach 3: Union-Find (most impressive, shows data structure knowledge)

function numIslandsUnionFind(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;

  class UnionFind {
    constructor(n) {
      this.parent = Array.from({ length: n }, (_, i) => i);
      this.rank = Array(n).fill(1);
      this.count = n; // number of disjoint sets
    }
    find(x) {
      if (this.parent[x] !== x) {
        this.parent[x] = this.find(this.parent[x]);
      }
      return this.parent[x];
    }
    union(x, y) {
      const rootX = this.find(x);
      const rootY = this.find(y);
      if (rootX === rootY) return;
      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--; // two sets merged into one
    }
  }

  // Count land cells
  let landCount = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') landCount++;
    }
  }

  const uf = new UnionFind(rows * cols);
  // Initially, every land cell is its own island
  // We will union adjacent land cells

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '0') continue;
      const idx = r * cols + c;
      // Only check right and down to avoid double-processing
      if (r + 1 < rows && grid[r + 1][c] === '1') {
        uf.union(idx, (r + 1) * cols + c);
      }
      if (c + 1 < cols && grid[r][c + 1] === '1') {
        uf.union(idx, r * cols + (c + 1));
      }
    }
  }

  // Count unique roots among land cells
  const roots = new Set();
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        roots.add(uf.find(r * cols + c));
      }
    }
  }
  return roots.size;
}

Union-Find is overkill for a simple island count, but it is the only approach that works when islands are being dynamically added (the grid is streaming). Mention this in an interview. It shows you are thinking about the problem beyond the static test case.

All three approaches have the same time complexity — O(M * N) — because you visit each cell a constant number of times. The differences are in space (DFS uses the call stack, BFS uses a queue, Union-Find uses parent/rank arrays) and in what you can say about the problem during the discussion.

Clone Graph: Deep Copy a Connected Structure

Clone Graph (LeetCode 133) tests whether you truly understand graph traversal. The question: "Given a reference of a node in a connected undirected graph, return a deep copy of the graph." The trap: the graph may contain cycles. A naive recursive copy without tracking visited nodes will loop infinitely.

The solution uses a hash map to map original nodes to their clones. When you encounter a node you have already cloned, you return the existing clone instead of creating a new one. This is the same pattern as memoization in DP — you are caching results to avoid redundant (or infinite) work.

function cloneGraph(node) {
  if (!node) return null;

  const cloned = new Map(); // original -> clone

  // DFS approach
  function dfs(original) {
    if (cloned.has(original)) {
      return cloned.get(original); // already cloned — return the copy
    }

    // Create the clone and register it immediately
    const copy = new Node(original.val);
    cloned.set(original, copy);

    // Recursively clone all neighbors
    for (const neighbor of original.neighbors) {
      copy.neighbors.push(dfs(neighbor));
    }

    return copy;
  }

  return dfs(node);
}

The BFS version is equally valid and avoids recursion depth issues on large graphs:

function cloneGraphBFS(node) {
  if (!node) return null;

  const cloned = new Map();
  const queue = [node];

  // Clone the start node and register it
  cloned.set(node, new Node(node.val));

  while (queue.length) {
    const original = queue.shift();
    const copy = cloned.get(original);

    for (const neighbor of original.neighbors) {
      if (!cloned.has(neighbor)) {
        // First time seeing this neighbor — clone and enqueue
        cloned.set(neighbor, new Node(neighbor.val));
        queue.push(neighbor);
      }
      // Wire up the edge in the cloned graph
      copy.neighbors.push(cloned.get(neighbor));
    }
  }

  return cloned.get(node);
}

The key insight for both approaches: register the clone in the map before processing its neighbors. In DFS, you call cloned.set(original, copy) before the recursive loop. In BFS, you create and register the clone when you first enqueue the original. This is what breaks the cycle — when you encounter a node that points back to an already-visited node, the map returns the existing clone, and you wire up the edge without recursing further.

Time complexity: O(V + E). You visit each node once and process each edge once. Space complexity: O(V) for the map and the recursion stack (or queue).

Dijkstra's Algorithm: The Shortest Path When Edges Have Weights

BFS finds the shortest path in terms of number of edges. But when edges have weights — distances, costs, latencies — you need Dijkstra. The algorithm maintains a priority queue of nodes ordered by the shortest known distance from the start. At each step, it extracts the closest unvisited node and relaxes its edges.

// Dijkstra using a min-heap (priority queue)
// In an interview, you can use a sorted array as a simple PQ
function dijkstra(graph, start) {
  // graph is an adjacency list where each edge is [neighbor, weight]
  // graph: { A: [['B', 4], ['C', 2]], B: [['A', 4], ['D', 5]], ... }

  const distances = {};
  const pq = [[0, start]]; // [distance, node] — sorted manually for simplicity
  const visited = new Set();

  // Initialize all distances to Infinity
  for (const node of Object.keys(graph)) {
    distances[node] = Infinity;
  }
  distances[start] = 0;

  while (pq.length) {
    // Extract min — O(n) with array, O(log n) with real heap
    pq.sort((a, b) => a[0] - b[0]);
    const [dist, node] = pq.shift();

    if (visited.has(node)) continue;
    visited.add(node);

    for (const [neighbor, weight] of graph[node]) {
      const newDist = dist + weight;
      if (newDist < distances[neighbor]) {
        distances[neighbor] = newDist;
        pq.push([newDist, neighbor]);
      }
    }
  }
  return distances;
}

Dijkstra does not work with negative edge weights. If your graph has negative edges — rare outside of arbitrage and certain scheduling problems — you need Bellman-Ford. Mention this distinction in an interview. It is a one-sentence signal that you know the landscape.

Topological Sort: Ordering Tasks With Dependencies

You have a set of tasks, and some tasks must happen before others. Build systems, course prerequisites, data pipeline DAGs, package installation order — all topological sort problems. The algorithm works only on Directed Acyclic Graphs (DAGs). If your graph has a cycle, topological sort is impossible — and detecting that cycle is itself a valuable signal.

// Topological sort using DFS (Kahn's algorithm is the BFS alternative)
function topologicalSort(graph) {
  const visited = new Set();
  const visiting = new Set(); // nodes in current DFS path — for cycle detection
  const order = [];

  function dfs(node) {
    if (visiting.has(node)) {
      throw new Error('Cycle detected — topological sort impossible');
    }
    if (visited.has(node)) return;

    visiting.add(node);
    for (const neighbor of graph[node]) {
      dfs(neighbor);
    }
    visiting.delete(node);
    visited.add(node);
    order.push(node);
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) dfs(node);
  }

  return order.reverse(); // postorder reversed gives topological order
}

The visiting set is the cycle detector. If you encounter a node that is already in the current DFS path, you have found a back edge — a cycle. This is the standard pattern. Do not try to detect cycles by counting visited nodes or tracking path lengths. The three-color approach (white = unvisited, gray = visiting, black = visited) is the cleanest and the one interviewers expect.

Course Schedule: Topological Sort in the Wild

Course Schedule (LeetCode 207) is the most-asked graph problem at FAANG companies. The question: "There are numCourses courses labeled 0 to n-1. You are given an array prerequisites where prerequisites[i] = [a, b] means you must take course b before course a. Return true if you can finish all courses, false if there is a cycle."

This is topological sort with cycle detection, dressed up in an academic metaphor. The courses are nodes. The prerequisites are directed edges (b → a). You can finish all courses if and only if the graph is a DAG.

Approach 1: DFS with three-color cycle detection

function canFinish(numCourses, prerequisites) {
  // Build adjacency list
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course); // edge: prereq -> course
  }

  // 0 = unvisited, 1 = visiting (in current DFS path), 2 = visited
  const state = Array(numCourses).fill(0);

  function hasCycle(course) {
    if (state[course] === 1) return true;  // back edge — cycle found
    if (state[course] === 2) return false; // already fully processed

    state[course] = 1; // mark as visiting
    for (const next of graph[course]) {
      if (hasCycle(next)) return true;
    }
    state[course] = 2; // mark as visited
    return false;
  }

  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

Approach 2: BFS (Kahn's algorithm) with indegree counting

function canFinishBFS(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const indegree = Array(numCourses).fill(0);

  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    indegree[course]++;
  }

  // Start with all courses that have no prerequisites
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (indegree[i] === 0) queue.push(i);
  }

  let coursesTaken = 0;
  while (queue.length) {
    const course = queue.shift();
    coursesTaken++;

    for (const next of graph[course]) {
      indegree[next]--;
      if (indegree[next] === 0) {
        queue.push(next); // all prerequisites satisfied
      }
    }
  }

  return coursesTaken === numCourses;
}

Kahn's algorithm is elegant: you repeatedly remove nodes with zero indegree (no remaining prerequisites). If you can remove all nodes, the graph is a DAG. If some nodes remain with indegree > 0, they form a cycle. The BFS approach also naturally produces a valid topological order — the order in which nodes are dequeued.

The follow-up, Course Schedule II (LeetCode 210), asks you to return the actual order. The BFS approach gives it to you for free: push each dequeued course into a result array. The DFS approach requires you to build the order array and reverse it at the end.

Time complexity: O(V + E) for both approaches. Space: O(V + E) for the adjacency list. In an interview, present both approaches and explain the tradeoff: DFS is more intuitive for cycle detection, BFS naturally produces the order.

Union-Find (Disjoint Set Union): The Secret Weapon for Connected Components

Union-Find is the most underrated data structure in the interview canon. It solves a specific problem — "are these two elements in the same set?" — with near-constant time operations. It is the optimal solution for: connected components in an undirected graph, cycle detection in Kruskal's MST algorithm, and any problem where you dynamically merge groups.

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

  find(x) {
    // Path compression: flatten the tree as we traverse
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // already in same set

    // Union by rank: attach smaller tree under larger tree
    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]++;
    }
    return true;
  }

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

// Example: count connected components in an undirected graph
function countComponents(n, edges) {
  const uf = new UnionFind(n);
  for (const [u, v] of edges) {
    uf.union(u, v);
  }
  // Count unique roots
  const roots = new Set();
  for (let i = 0; i < n; i++) {
    roots.add(uf.find(i));
  }
  return roots.size;
}

Path compression and union by rank together give an amortized time complexity of O(α(n)) per operation, where α is the inverse Ackermann function — a number that is effectively constant for any practical input size. This is not a theoretical curiosity. It means you can process millions of union and find operations in milliseconds.

Cycle Detection: The Problem That Appears Everywhere

Cycle detection in a directed graph uses the three-color DFS approach from topological sort. In an undirected graph, it is simpler — if you encounter a visited neighbor that is not your parent, you have found a cycle.

// Cycle detection in an undirected graph
function hasCycle(graph) {
  const visited = new Set();

  function dfs(node, parent) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) {
        if (dfs(neighbor, node)) return true;
      } else if (neighbor !== parent) {
        return true; // back edge to a non-parent = cycle
      }
    }
    return false;
  }

  for (const node of Object.keys(graph)) {
    if (!visited.has(node)) {
      if (dfs(node, null)) return true;
    }
  }
  return false;
}

The Graph Heuristic: Which Algorithm When?

When you see a graph problem, run this decision tree:

1. Shortest path? Unweighted → BFS. Weighted (non-negative) → Dijkstra. Weighted (negative edges) → Bellman-Ford.
2. Ordering with dependencies? → Topological sort. If it fails, you have a cycle.
3. Connected components / dynamic grouping? → Union-Find.
4. All-pairs shortest path? → Floyd-Warshall (O(V³), but simple to code).
5. Minimum spanning tree? → Kruskal (with Union-Find) or Prim.

If you cannot articulate this decision tree in an interview, you will waste ten minutes trying BFS on a weighted graph before realizing your mistake. Practice the decision, not just the algorithms.

Dynamic Programming: The Art of Remembering

The Problem That Broke Vikram

Vikram was a senior engineer at a Hyderabad product company, applying for a staff role at Uber. The interviewer asked: "Given a set of items with weights and values, and a knapsack with capacity W, find the maximum value you can carry."

Vikram wrote a recursive solution. It worked for the small test case. The interviewer asked, "What is the time complexity?" Vikram said O(2^n). The interviewer asked, "Can you do better?"

Vikram could not. He had never learned to recognize when recursion is doing redundant work — and how to eliminate that redundancy with a table.

Dynamic programming is not a new algorithm. It is an optimization technique. When a recursive solution solves the same subproblem multiple times, DP stores the result and reuses it. That is the entire idea. Everything else — memoization, tabulation, state transitions, optimal substructure — is vocabulary for this one concept.

Memoization vs Tabulation: Top-Down vs Bottom-Up

Memoization is top-down: you write the recursive solution, then add a cache. Tabulation is bottom-up: you build a table from the base cases up. Both achieve the same time complexity. The choice is stylistic, but there are practical differences.

Memoization is easier to write from a recursive solution. It only computes the states you actually need. But it uses recursion, which risks stack overflow on large inputs.

Tabulation avoids recursion. It computes every state in order, which can be wasteful if many states are unreachable. But it is often more space-efficient because you can discard old rows.

// Fibonacci — the "hello world" of DP
// Naive recursion: O(2^n)
function fib(n) {
  if (n <= 1) return n;
  return fib(n - 1) + fib(n - 2);
}

// Memoization: O(n) time, O(n) space
function fibMemo(n, memo = {}) {
  if (n <= 1) return n;
  if (memo[n] !== undefined) return memo[n];
  memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
  return memo[n];
}

// Tabulation: O(n) time, O(1) space
function fibTab(n) {
  if (n <= 1) return n;
  let prev2 = 0, prev1 = 1;
  for (let i = 2; i <= n; i++) {
    const curr = prev1 + prev2;
    prev2 = prev1;
    prev1 = curr;
  }
  return prev1;
}

The Fibonacci tabulation with O(1) space is a pattern you will reuse: when each state depends only on the last k states, you only need to store the last k values, not the entire table.

0/1 Knapsack: The Problem That Teaches DP Thinking

The knapsack problem is the gateway drug to DP. Once you understand it, you see its pattern in: subset sum, partition equal subset sum, target sum, coin change, and a dozen other problems that are just knapsack with different window dressing.

The state: dp[i][w] = maximum value achievable using the first i items with capacity w.

The transition: for each item, you either include it (if it fits) or exclude it. Take the max.

function knapsack(weights, values, capacity) {
  const n = weights.length;
  // dp[i][w] = max value using first i items with capacity w
  const dp = Array.from({ length: n + 1 }, () => Array(capacity + 1).fill(0));

  for (let i = 1; i <= n; i++) {
    for (let w = 0; w <= capacity; w++) {
      if (weights[i - 1] <= w) {
        // Include item i-1: value[i-1] + best with remaining capacity
        // Exclude item i-1: best without this item
        dp[i][w] = Math.max(
          values[i - 1] + dp[i - 1][w - weights[i - 1]],
          dp[i - 1][w]
        );
      } else {
        dp[i][w] = dp[i - 1][w];
      }
    }
  }
  return dp[n][capacity];
}

// Space-optimized: O(capacity) instead of O(n * capacity)
function knapsackOptimized(weights, values, capacity) {
  const n = weights.length;
  const dp = Array(capacity + 1).fill(0);

  for (let i = 0; i < n; i++) {
    // Iterate backwards to avoid using the same item twice
    for (let w = capacity; w >= weights[i]; w--) {
      dp[w] = Math.max(dp[w], values[i] + dp[w - weights[i]]);
    }
  }
  return dp[capacity];
}

The backward iteration in the space-optimized version is critical. If you iterate forward, you can use the same item multiple times — which turns it into the unbounded knapsack problem. This is not a trick. It is a direct consequence of how the 1D array overwrites itself. Understand why it works, not just that it works.

Coin Change: The Two Faces of the Same Problem

Coin Change is the DP problem that teaches you to read the question carefully. There are two variants, and they have different DP formulations. Mix them up, and your solution is wrong before you write the first line.

Variant 1: Minimum Coins (LeetCode 322). "Given coins of different denominations and a total amount, find the fewest number of coins needed to make up that amount. Return -1 if it is impossible."

This is an unbounded knapsack problem — you can use each coin unlimited times. The state: dp[a] = minimum coins needed to make amount a. The transition: for each coin, dp[a] = min(dp[a], 1 + dp[a - coin]).

function coinChange(coins, amount) {
  // dp[a] = minimum coins to make amount a
  // Initialize with amount+1 (a value larger than any possible answer)
  const dp = Array(amount + 1).fill(amount + 1);
  dp[0] = 0; // zero coins to make amount 0

  for (let a = 1; a <= amount; a++) {
    for (const coin of coins) {
      if (coin <= a) {
        dp[a] = Math.min(dp[a], 1 + dp[a - coin]);
      }
    }
  }

  return dp[amount] > amount ? -1 : dp[amount];
}

Walk through coins = [1, 2, 5], amount = 11. The DP table builds like this:

Amount	0	1	2	3	4	5	6	7	8	9	10	11
dp[a]	0	1	1	2	2	1	2	2	3	3	2	3

For amount 6: you can use coin 5 (1 + dp[1] = 1 + 1 = 2), coin 2 (1 + dp[4] = 1 + 2 = 3), or coin 1 (1 + dp[5] = 1 + 1 = 2). Minimum is 2 coins (5 + 1). For amount 11: coin 5 gives 1 + dp[6] = 1 + 2 = 3, coin 2 gives 1 + dp[9] = 1 + 3 = 4, coin 1 gives 1 + dp[10] = 1 + 2 = 3. Answer: 3 coins (5 + 5 + 1).

The initialization to amount + 1 is a sentinel meaning "unreachable." Any valid answer uses at most amount coins (all 1s), so amount + 1 is safely larger than any real answer. This is cleaner than using Infinity because it avoids Infinity arithmetic edge cases.

Variant 2: Number of Ways (LeetCode 518). "Given coins of different denominations and a total amount, return the number of combinations that make up that amount."

This is a different DP entirely. The state: dp[a] = number of ways to make amount a. The transition: dp[a] += dp[a - coin]. But the loop order matters critically.

function change(amount, coins) {
  const dp = Array(amount + 1).fill(0);
  dp[0] = 1; // one way to make amount 0: use no coins

  // Coins in outer loop → combinations (order does not matter)
  for (const coin of coins) {
    for (let a = coin; a <= amount; a++) {
      dp[a] += dp[a - coin];
    }
  }

  return dp[amount];
}

The loop order is the entire problem. Coins in the outer loop produces combinations (2+2+1 is the same as 1+2+2). Amount in the outer loop produces permutations (2+2+1 and 1+2+2 are counted separately). If the problem asks for "number of combinations," coins go in the outer loop. If it asks for "number of permutations" (LeetCode 377, Combination Sum IV), amount goes in the outer loop. This single detail has caused more failed interviews than any other DP subtlety. Know it cold.

Longest Common Subsequence: The String DP Pattern

LCS is the template for string DP problems. The state: dp[i][j] = LCS length of text1[0..i-1] and text2[0..j-1]. The transition: if characters match, add 1 to the diagonal. If they do not match, take the max of the left and top cells.

function longestCommonSubsequence(text1, text2) {
  const m = text1.length, n = text2.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++) {
      if (text1[i - 1] === text2[j - 1]) {
        dp[i][j] = 1 + dp[i - 1][j - 1];
      } else {
        dp[i][j] = Math.max(dp[i - 1][j], dp[i][j - 1]);
      }
    }
  }
  return dp[m][n];
}

LCS is the parent pattern for: edit distance (Levenshtein), longest palindromic subsequence, shortest common supersequence, and the diff algorithm in Git. If you understand LCS deeply, you can derive all of these in an interview by modifying the transition.

Edit Distance: The DP Table You Must Draw

Edit Distance (LeetCode 72), also called Levenshtein distance, is the problem: "Given two strings word1 and word2, return the minimum number of operations required to convert word1 to word2. Operations: insert a character, delete a character, or replace a character."

This is LCS with three operations instead of one. The state: dp[i][j] = minimum operations to convert word1[0..i-1] to word2[0..j-1]. The transition has three cases:

• If word1[i-1] === word2[j-1]: no operation needed, dp[i][j] = dp[i-1][j-1].
• Otherwise, take the minimum of: delete from word1 (dp[i-1][j] + 1), insert into word1 (dp[i][j-1] + 1), or replace (dp[i-1][j-1] + 1).

function minDistance(word1, word2) {
  const m = word1.length, n = word2.length;
  const dp = Array.from({ length: m + 1 }, () => Array(n + 1).fill(0));

  // Base case: converting empty string to word2[0..j-1] requires j insertions
  for (let j = 0; j <= n; j++) dp[0][j] = j;

  // Base case: converting word1[0..i-1] to empty string requires i deletions
  for (let i = 0; i <= m; i++) dp[i][0] = i;

  for (let i = 1; i <= m; i++) {
    for (let j = 1; j <= n; j++) {
      if (word1[i - 1] === word2[j - 1]) {
        dp[i][j] = dp[i - 1][j - 1]; // characters match — no operation
      } else {
        dp[i][j] = 1 + Math.min(
          dp[i - 1][j],     // delete word1[i-1]
          dp[i][j - 1],     // insert word2[j-1] into word1
          dp[i - 1][j - 1]  // replace word1[i-1] with word2[j-1]
        );
      }
    }
  }
  return dp[m][n];
}

Draw the DP table for word1 = "horse", word2 = "ros". It is worth the two minutes:

	""	r	o	s
""	0	1	2	3
h	1	1	2	3
o	2	2	1	2
r	3	2	2	2
s	4	3	3	2
e	5	4	4	3

Cell (1,1): 'h' vs 'r' — mismatch. Min of delete(1+dp[0][1]=2), insert(1+dp[1][0]=2), replace(1+dp[0][0]=1) = 1. Cell (3,1): 'r' vs 'r' — match, dp[2][0] = 2. Cell (5,3): 'e' vs 's' — mismatch. Min of delete(1+dp[4][3]=5), insert(1+dp[5][2]=5), replace(1+dp[4][2]=4) = 3. Answer: 3 operations (horse → rorse → rose → ros).

The base cases are where most candidates stumble. Converting any string to an empty string requires deleting all its characters — hence dp[i][0] = i. Converting an empty string to any string requires inserting all its characters — hence dp[0][j] = j. If you forget these, your entire table is wrong.

Edit distance is the parent of a family of problems: one edit distance (LC 161), delete operation for two strings (LC 583), minimum ASCII delete sum (LC 712). All of them use the same table with a different cost function. Learn the pattern once, and you solve five problems.

Longest Increasing Subsequence: The DP + Binary Search Hybrid

LIS has a pure DP solution in O(n²) and a patience-sorting solution in O(n log n). The O(n²) version is straightforward: dp[i] = length of LIS ending at index i. The O(n log n) version is the one that impresses interviewers.

// O(n²) DP — good enough for most interviews
function lengthOfLIS(nums) {
  const dp = Array(nums.length).fill(1);
  let maxLen = 1;

  for (let i = 1; i < nums.length; i++) {
    for (let j = 0; j < i; j++) {
      if (nums[i] > nums[j]) {
        dp[i] = Math.max(dp[i], dp[j] + 1);
      }
    }
    maxLen = Math.max(maxLen, dp[i]);
  }
  return maxLen;
}

// O(n log n) — patience sorting with binary search
function lengthOfLISOptimized(nums) {
  const tails = []; // tails[i] = smallest tail of an increasing subsequence of length i+1

  for (const num of nums) {
    let left = 0, right = tails.length;
    while (left < right) {
      const mid = Math.floor((left + right) / 2);
      if (tails[mid] < num) left = mid + 1;
      else right = mid;
    }
    if (left === tails.length) tails.push(num);
    else tails[left] = num;
  }
  return tails.length;
}

The tails array does not store the actual LIS. It stores the smallest possible tail value for each subsequence length. This is the insight: to maximize the chance of extending a subsequence, you want the smallest possible tail. The binary search finds where the current number fits in this structure.

The DP Recognition Heuristic

DP problems share two properties. If both are present, DP is the answer:

1. Optimal substructure: The optimal solution to the problem contains optimal solutions to subproblems. If you can express the answer in terms of smaller versions of the same problem, you have optimal substructure.

2. Overlapping subproblems: The recursive solution solves the same subproblem multiple times. If you draw the recursion tree and see repeated nodes, you have overlapping subproblems.

When you suspect DP, ask yourself: "What is the state? What are the dimensions?" The state is the minimum information you need to describe a subproblem. For knapsack, it is (items considered, remaining capacity). For LCS, it is (position in string 1, position in string 2). For LIS, it is (last index considered). Once you have the state, the transition is usually one of three patterns: include/exclude, match/mismatch, or min/max over choices.

Backtracking: The Art of Exploring All Possibilities

Backtracking is brute force with pruning. You explore the entire state space, but you abandon a path the moment it cannot lead to a valid solution. The pattern is always the same: choose, explore, unchoose.

// The backtracking template
function backtrack(state, choices, start, result) {
  // Base case: state is a valid solution
  if (isSolution(state)) {
    result.push([...state]); // push a copy
    return;
  }

  for (let i = start; i < choices.length; i++) {
    // Prune: skip choices that cannot lead to a solution
    if (!isValid(state, choices[i])) continue;

    // Choose
    state.push(choices[i]);

    // Explore
    backtrack(state, choices, i + 1, result); // i+1 for combinations, 0 for permutations

    // Unchoose (backtrack)
    state.pop();
  }
}

That template solves 80% of backtracking problems. The variations are: whether you pass i + 1 (combinations — order does not matter) or 0 (permutations — order matters), whether you need a used array to avoid reusing elements, and what your pruning condition is.

Permutations: Order Matters

function permute(nums) {
  const result = [];
  const used = Array(nums.length).fill(false);

  function backtrack(path) {
    if (path.length === nums.length) {
      result.push([...path]);
      return;
    }
    for (let i = 0; i < nums.length; i++) {
      if (used[i]) continue; // cannot reuse
      used[i] = true;
      path.push(nums[i]);
      backtrack(path);
      path.pop();
      used[i] = false;
    }
  }

  backtrack([]);
  return result;
}

Time complexity: O(n! * n). There are n! permutations, and copying each one takes O(n). This is as good as it gets — you cannot generate n! things in less than O(n!) time. The key is pruning: if the problem has constraints that let you skip branches, use them.

Subsets: The Power Set Pattern

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

  function backtrack(start, path) {
    result.push([...path]); // every path is a valid subset
    for (let i = start; i < nums.length; i++) {
      path.push(nums[i]);
      backtrack(i + 1, path);
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

Subsets has 2^n solutions. The backtracking approach generates each one exactly once. The alternative — iterating over bitmasks from 0 to 2^n - 1 — is also valid and sometimes cleaner. Know both.

Combination Sum: The Backtracking Template With Deduplication

Combination Sum (LeetCode 39) is the problem that teaches you how to handle unlimited reuse and deduplication in backtracking. The question: "Given an array of distinct integers candidates and a target integer target, return all unique combinations of candidates where the chosen numbers sum to target. You may use the same number unlimited times."

The key decisions: (1) pass i not i + 1 to allow reusing the same element, (2) pass start to avoid generating duplicate combinations like [2,2,3] and [2,3,2] and [3,2,2], (3) prune when the remaining sum goes negative.

function combinationSum(candidates, target) {
  const result = [];

  function backtrack(start, remaining, path) {
    if (remaining === 0) {
      result.push([...path]);
      return;
    }
    if (remaining < 0) return; // prune: overshot the target

    for (let i = start; i < candidates.length; i++) {
      path.push(candidates[i]);
      // Pass i (not i+1) because we can reuse the same element
      backtrack(i, remaining - candidates[i], path);
      path.pop();
    }
  }

  backtrack(0, target, []);
  return result;
}

The start parameter is the deduplication mechanism. By only considering candidates at index start or later, you enforce that combinations are built in non-decreasing index order. This guarantees [2,2,3] is generated (indices 0,0,1) but [2,3,2] is not (indices 0,1,0 — index 0 appears after index 1, which violates the non-decreasing order).

The follow-up, Combination Sum II (LeetCode 40), adds the constraint that each candidate can be used at most once, and the candidates array may contain duplicates. The solution adds two modifications: pass i + 1 (no reuse), and skip duplicate values at the same recursion depth with if (i > start && candidates[i] === candidates[i-1]) continue.

Generate Parentheses: The Open-Close Count Approach

Generate Parentheses (LeetCode 22) is the backtracking problem that does not look like backtracking at first glance. The question: "Given n pairs of parentheses, generate all combinations of well-formed parentheses."

The insight: at each step, you have two choices — add an opening parenthesis or a closing parenthesis. But not all choices are valid. You can add an opening parenthesis if you have used fewer than n. You can add a closing parenthesis only if there is an unmatched opening parenthesis (i.e., close < open).

function generateParenthesis(n) {
  const result = [];

  function backtrack(open, close, str) {
    // Base case: used all n pairs
    if (str.length === 2 * n) {
      result.push(str);
      return;
    }

    // Can add '(' if we haven't used all n
    if (open < n) {
      backtrack(open + 1, close, str + '(');
    }

    // Can add ')' if there's an unmatched '(' to close
    if (close < open) {
      backtrack(open, close + 1, str + ')');
    }
  }

  backtrack(0, 0, '');
  return result;
}

The state is just two counters: open and close. No array, no used set, no start index. This is the cleanest backtracking problem in the canon — it strips away everything except the core choose-explore pattern. The pruning conditions (open < n, close < open) are the entire problem. Get them right, and the solution writes itself.

The number of valid combinations is the nth Catalan number: C(n) = (2n)! / ((n+1)! * n!). For n=3, that is 5. For n=4, it is 14. The time complexity is O(4^n / sqrt(n)) — exponential, as with all backtracking. There is no polynomial solution because the output itself is exponential in size.

N-Queens: The Classic Backtracking Problem

N-Queens is the problem that teaches pruning. Without pruning, you would place queens in all n² choose n positions and check each one. With pruning, you place one queen per row and skip columns and diagonals that are under attack.

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

  // Track attacked columns and diagonals for O(1) validity checks
  const cols = new Set();
  const posDiag = new Set(); // r + c
  const negDiag = new Set(); // r - c

  function backtrack(row) {
    if (row === n) {
      result.push(board.map(r => r.join('')));
      return;
    }
    for (let col = 0; col < n; col++) {
      if (cols.has(col) || posDiag.has(row + col) || negDiag.has(row - col)) {
        continue; // prune: this square is under attack
      }
      // Choose
      cols.add(col);
      posDiag.add(row + col);
      negDiag.add(row - col);
      board[row][col] = 'Q';

      backtrack(row + 1);

      // Unchoose
      cols.delete(col);
      posDiag.delete(row + col);
      negDiag.delete(row - col);
      board[row][col] = '.';
    }
  }

  backtrack(0);
  return result;
}

The diagonal tracking is the insight: two squares are on the same positive diagonal if row + col is equal. They are on the same negative diagonal if row - col is equal. This turns an O(n) attack check into O(1). In an interview, this is the difference between a solution that times out on n=12 and one that runs instantly.

Sudoku Solver: Backtracking in the Wild

Sudoku is N-Queens on a 9x9 grid with more constraints. The pattern is identical: choose an empty cell, try valid digits, recurse, backtrack on failure.

function solveSudoku(board) {
  const rows = Array.from({ length: 9 }, () => new Set());
  const cols = Array.from({ length: 9 }, () => new Set());
  const boxes = Array.from({ length: 9 }, () => new Set());

  // Initialize constraint sets from the given board
  for (let r = 0; r < 9; r++) {
    for (let c = 0; c < 9; c++) {
      if (board[r][c] !== '.') {
        const num = board[r][c];
        rows[r].add(num);
        cols[c].add(num);
        boxes[Math.floor(r / 3) * 3 + Math.floor(c / 3)].add(num);
      }
    }
  }

  function backtrack(r, c) {
    if (r === 9) return true; // solved all rows
    if (c === 9) return backtrack(r + 1, 0); // next row
    if (board[r][c] !== '.') return backtrack(r, c + 1); // skip filled cells

    const boxIdx = Math.floor(r / 3) * 3 + Math.floor(c / 3);
    for (let num = 1; num <= 9; num++) {
      const ch = String(num);
      if (rows[r].has(ch) || cols[c].has(ch) || boxes[boxIdx].has(ch)) continue;

      // Choose
      board[r][c] = ch;
      rows[r].add(ch);
      cols[c].add(ch);
      boxes[boxIdx].add(ch);

      if (backtrack(r, c + 1)) return true;

      // Unchoose
      board[r][c] = '.';
      rows[r].delete(ch);
      cols[c].delete(ch);
      boxes[boxIdx].delete(ch);
    }
    return false;
  }

  backtrack(0, 0);
}

The box index formula Math.floor(r / 3) * 3 + Math.floor(c / 3) maps a 9x9 grid to nine 3x3 boxes numbered 0 through 8. This is the kind of detail you want memorized, not derived on the spot.

Palindrome Partitioning: Backtracking Meets String Processing

Palindrome Partitioning (LeetCode 131) combines backtracking with a string property check. The question: "Given a string s, partition s such that every substring of the partition is a palindrome. Return all possible palindrome partitioning of s."

The pattern: at each step, you take a prefix of the remaining string. If the prefix is a palindrome, you add it to the current partition and recurse on the suffix. If it is not, you skip it. This is the same choose-explore-unchoose template, but the "choice" is a variable-length substring instead of a single element from an array.

function partition(s) {
  const result = [];

  function isPalindrome(str, left, right) {
    while (left < right) {
      if (str[left] !== str[right]) return false;
      left++;
      right--;
    }
    return true;
  }

  function backtrack(start, path) {
    if (start === s.length) {
      result.push([...path]);
      return;
    }

    for (let end = start; end < s.length; end++) {
      // Prune: only explore if the current substring is a palindrome
      if (!isPalindrome(s, start, end)) continue;

      // Choose: take s[start..end] as the next partition
      path.push(s.slice(start, end + 1));

      // Explore: partition the rest of the string
      backtrack(end + 1, path);

      // Unchoose
      path.pop();
    }
  }

  backtrack(0, []);
  return result;
}

For s = "aab", the recursion tree looks like this:

• start=0: try "a" (palindrome) → start=1: try "a" (palindrome) → start=2: try "b" (palindrome) → start=3: push ["a","a","b"]
• start=0: try "a" → start=1: try "ab" (not palindrome, skip)
• start=0: try "aa" (palindrome) → start=2: try "b" (palindrome) → start=3: push ["aa","b"]
• start=0: try "aab" (not palindrome, skip)

Result: [["a","a","b"], ["aa","b"]].

The palindrome check is O(n) per call, and you make it for each of the O(2^n) possible partitions. You can optimize this by precomputing a 2D palindrome table with DP — isPal[i][j] = true if s[i..j] is a palindrome — reducing the check to O(1). Mention this optimization in an interview. It shows you see the DP hiding inside the backtracking problem.

The Backtracking Heuristic

Backtracking is the answer when the problem asks for "all possible," "generate all," or "find a configuration that satisfies constraints." The time complexity is always exponential — you are exploring a combinatorial space. The skill is not avoiding exponential time. It is pruning enough branches that the exponential base becomes manageable.

Ask yourself: "What is the earliest point at which I can determine a path is invalid?" The earlier you prune, the fewer branches you explore. In N-Queens, you prune at placement time. In Sudoku, you prune at digit-selection time. In subset sum, you prune when the remaining sum exceeds the target. The best backtracking solutions prune aggressively.

Practice: The Problems That Will Make You Ready

Reading about these algorithms is not enough. You must solve problems until the patterns are automatic. Here is your training set, ordered by difficulty within each topic:

Trees (solve all 8):

1. Maximum Depth of Binary Tree (LC 104)
2. Invert Binary Tree (LC 226)
3. Same Tree (LC 100)
4. Validate Binary Search Tree (LC 98)
5. Binary Tree Level Order Traversal (LC 102)
6. Lowest Common Ancestor of a Binary Tree (LC 236)
7. Serialize and Deserialize Binary Tree (LC 297)
8. Implement Trie (LC 208)

Graphs (solve all 8):

1. Number of Islands (LC 200)
2. Clone Graph (LC 133)
3. Course Schedule (LC 207) — cycle detection + topological sort
4. Course Schedule II (LC 210) — topological sort with order
5. Network Delay Time (LC 743) — Dijkstra
6. Cheapest Flights Within K Stops (LC 787) — modified Dijkstra/Bellman-Ford
7. Redundant Connection (LC 684) — Union-Find
8. Word Ladder (LC 127) — BFS on implicit graph

Dynamic Programming (solve all 8):

1. Climbing Stairs (LC 70)
2. House Robber (LC 198)
3. Coin Change (LC 322)
4. Longest Increasing Subsequence (LC 300)
5. Longest Common Subsequence (LC 1143)
6. 0/1 Knapsack (standard, not on LC — implement from scratch)
7. Edit Distance (LC 72)
8. Partition Equal Subset Sum (LC 416)

Backtracking (solve all 6):

1. Subsets (LC 78)
2. Permutations (LC 46)
3. Combination Sum (LC 39)
4. Generate Parentheses (LC 22)
5. N-Queens (LC 51)
6. Word Search (LC 79)

That is 30 problems. If you solve two per day, you finish in two weeks. If you solve one per day, you finish in a month. Either way, you finish. The engineers who get ₹60 LPA offers are the ones who finish. The ones who stay at ₹20 LPA are the ones who read about these problems and never solve them.

For each problem, follow this protocol:

1. Read the problem. Set a 25-minute timer.
2. If you solve it within 25 minutes, analyze your solution's time and space complexity. Then read the editorial to see if there is a better approach.
3. If you do not solve it within 25 minutes, read the solution. Understand it. Then close the tab, wait an hour, and implement it from scratch without looking.
4. Revisit every problem you struggled with after three days. If you cannot solve it cold in 20 minutes, repeat step 3.

This protocol is uncomfortable. That is the point. Learning happens at the edge of your ability, not in the comfort of problems you already know how to solve.

The Revelation

Here is what nobody tells you about "advanced" DSA.

When you first encounter trees, graphs, DP, and backtracking, they feel like four separate mountains. Each has its own vocabulary, its own patterns, its own LeetCode problem set. You study them in isolation. You build mental silos. And for months, you feel like you are learning four different subjects.

Then something shifts. You are solving a graph problem — shortest path in a grid — and you realize you are using BFS, which is the same algorithm you used for level-order tree traversal. You are solving a DP problem — word break — and you realize the memoization table is just a DAG where each state is a node and each transition is an edge. You are solving a backtracking problem — word search — and you realize the grid is a graph and the search is DFS with pruning.

The walls between the topics dissolve.

Trees are just directed acyclic graphs where each node has at most one parent. Graph traversals are tree traversals with a visited set. DP is just DFS on an implicit DAG with memoization. Backtracking is DFS on a state-space tree with pruning. The "advanced" topics are not advanced at all. They are the same fundamental operations — traverse, search, remember, prune — composed in different configurations.

Once you see this, the interview landscape transforms. There are not 2,500 LeetCode problems. There are maybe 15 patterns. Every problem is a variation on a pattern you already know. The skill is not memorizing solutions. The skill is pattern recognition — seeing the tree inside the graph, the DP inside the backtracking, the BFS inside the Dijkstra.

Rahul, after his Google rejection, spent three months doing exactly this. He did not grind 500 problems. He solved the 30 problems listed above, plus another 20 for reinforcement. He focused on patterns, not problems. He practiced articulating his thought process out loud. Six months later, he walked into an interview at a different FAANG company. The interviewer drew a tree on the whiteboard. Rahul smiled. He asked clarifying questions. He stated his approach. He wrote clean code. He analyzed complexity. He discussed variants.

He got the offer. The package: ₹82 lakhs.

The gatekeeper did not change. Rahul did. And now you know exactly how.