Chapter 12a — Graph Problems

Reading the Problem Shape

Before writing any code, answer:

What are the nodes? What are the edges?
Directed or undirected?
What are you looking for — path, connectivity, ordering, count?
Do I need BFS (shortest path, level order) or DFS (connectivity, cycles)?

Problem 1: Number of Islands

LeetCode 200 — asked at almost every company

Given a 2D binary grid of '1's (land) and '0's (water), return the number of islands (connected groups of '1's connected horizontally or vertically).

What do I have? 2D grid, characters '1' or '0'.
What do I want? Count of distinct islands.
What is the brute force? Visit every cell. If it's land and unvisited, start a flood-fill — mark all connected land as visited. Count how many times you start a flood-fill.
Where is the waste? None — we visit every cell at most twice (once to discover, once as neighbor). This is already O(rows × cols).

javascript

function numIslands(grid) {
  const rows = grid.length, cols = grid[0].length;
  let islands = 0;
  
  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (grid[r][c] !== '1') return;
    
    grid[r][c] = '#';  // mark visited (flood with '#')
    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') {
        dfs(r, c);
        islands++;
      }
    }
  }
  
  return islands;
}

Full dry run on:

code

grid = [
  ['1','1','0','0'],
  ['1','1','0','0'],
  ['0','0','1','0'],
  ['0','0','0','1']
]

code

r=0, c=0: grid[0][0]='1' → dfs(0,0)
  mark [0][0]='#'
  dfs(1,0): grid[1][0]='1' → mark, recurse
    dfs(2,0): '0' → return
    dfs(0,0): '#' → return
    dfs(1,1): '1' → mark
      dfs(2,1): '0' → return
      dfs(0,1): '1' → mark
        dfs(-1,1): out → return
        dfs(1,1): '#' → return
        dfs(0,2): '0' → return
        dfs(0,0): '#' → return
      dfs(1,2): '0' → return
      dfs(1,0): '#' → return
    dfs(1,-1): out → return
  dfs(0,0): '#' → return
  dfs(-1,0): out → return
  dfs(0,1): '#' → already marked
islands++ = 1

r=0, c=1: '#' → skip
r=0, c=2: '0' → skip
r=0, c=3: '0' → skip
r=1: all '#' or '0' → skip
r=2, c=2: '1' → dfs(2,2)
  mark '#', flood fills just this cell
islands++ = 2

r=3, c=3: '1' → dfs(3,3), single cell
islands++ = 3

Result: 3 islands. ✓

Why modify the grid instead of a separate visited array? Avoids allocating O(rows × cols) extra space. The grid is restored conceptually (or you can restore '#' to '1' after DFS if you need to preserve the input).

Time: O(rows × cols). Space: O(rows × cols) call stack in worst case (snake-shaped island).

Problem 2: Clone Graph

LeetCode 133

Given a reference to a node in a connected undirected graph, return a deep copy (clone) of the graph. Each node has a value and a list of neighbors.

What do I have? A node reference. The graph is connected.
What do I want? A new graph where every node is a new object but has the same structure.
Challenge? Each node might be referenced multiple times. If we naively recurse, we'll create duplicates.
Solution? Use a HashMap: original node → cloned node. Before recursing into a neighbor, check if we've already cloned it.

javascript

function cloneGraph(node) {
  if (!node) return null;
  
  const cloned = new Map();  // original node → its clone
  
  function dfs(n) {
    if (cloned.has(n)) return cloned.get(n);  // already cloned, return it
    
    const clone = { val: n.val, neighbors: [] };
    cloned.set(n, clone);  // register BEFORE recursing (handles cycles)
    
    for (const neighbor of n.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }
    
    return clone;
  }
  
  return dfs(node);
}

Why register the clone BEFORE recursing into neighbors? The graph can have cycles (A → B → A). If we registered after recursion, when DFS goes A→B→A, it wouldn't find A in the map (not registered yet), create a second clone of A, and loop forever. Registering before recursion breaks the cycle: when B sees A again, A is already in the map.

Dry run on: 1 — 2 — 3 — 4 — 1 (cycle)

code

dfs(1): not in map
  clone1 = {val:1, neighbors:[]}
  map: {1→clone1}
  for neighbor 2:
    dfs(2): not in map
      clone2 = {val:2, neighbors:[]}
      map: {1→clone1, 2→clone2}
      for neighbor 1:
        dfs(1): IN MAP → return clone1
        clone2.neighbors = [clone1]
      for neighbor 3:
        dfs(3): ... creates clone3, clone4, returns to clone3.neighbors=[clone2,clone4]
      clone2.neighbors = [clone1, clone3]
    return clone2
  clone1.neighbors = [clone2]
  for neighbor 4:
    dfs(4) → ... similarly resolved
  clone1.neighbors = [clone2, clone4]
return clone1

The key insight: the HashMap serves the same role as visited in regular DFS, but instead of just storing "visited", it stores the actual clone. This enables O(1) lookup AND prevents re-cloning.

Time: O(V + E). Space: O(V) for the HashMap.

Problem 3: Course Schedule

LeetCode 207 — cycle detection in directed graph

There are numCourses courses (0 to n-1). prerequisites[i] = [a, b] means you must take course b before course a. Return true if it's possible to finish all courses.

What do I have? n courses, list of prerequisite pairs.
What do I want? Can we complete all courses? i.e., is there any valid ordering?
Key insight? A valid ordering exists if and only if the prerequisite graph has no cycles. (A cycle means A requires B requires A — impossible.)
Algorithm? Detect cycle in directed graph. Either: DFS with recStack, or Kahn's topological sort.

Solution 1: Kahn's Algorithm (BFS)

javascript

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  const inDegree = new Array(numCourses).fill(0);
  
  for (const [course, prereq] of prerequisites) {
    graph[prereq].push(course);
    inDegree[course]++;
  }
  
  const queue = [];
  for (let i = 0; i < numCourses; i++) {
    if (inDegree[i] === 0) queue.push(i);
  }
  
  let completed = 0;
  while (queue.length > 0) {
    const course = queue.shift();
    completed++;
    
    for (const next of graph[course]) {
      inDegree[next]--;
      if (inDegree[next] === 0) queue.push(next);
    }
  }
  
  return completed === numCourses;
}

Full dry run on numCourses=4, prerequisites=[[1,0],[2,0],[3,1],[3,2]]:

code

Edge meaning: [a,b] = b→a (must take b before a)
graph[0]=[1,2], graph[1]=[3], graph[2]=[3]
inDegree: [0,1,1,2]

Queue (inDegree=0): [0]

Step 1: dequeue 0, completed=1
  neighbor 1: inDegree[1]-- = 0 → enqueue
  neighbor 2: inDegree[2]-- = 0 → enqueue
  queue=[1,2]

Step 2: dequeue 1, completed=2
  neighbor 3: inDegree[3]-- = 1
  queue=[2]

Step 3: dequeue 2, completed=3
  neighbor 3: inDegree[3]-- = 0 → enqueue
  queue=[3]

Step 4: dequeue 3, completed=4
  queue=[]

completed=4=numCourses → return true ✓

Solution 2: DFS with cycle detection

javascript

function canFinish(numCourses, prerequisites) {
  const graph = Array.from({ length: numCourses }, () => []);
  for (const [a, b] of prerequisites) graph[b].push(a);
  
  // States: 0=unvisited, 1=in current path, 2=fully done
  const state = new Array(numCourses).fill(0);
  
  function hasCycle(node) {
    if (state[node] === 1) return true;   // cycle!
    if (state[node] === 2) return false;  // already fully explored
    
    state[node] = 1;  // in progress
    for (const neighbor of graph[node]) {
      if (hasCycle(neighbor)) return true;
    }
    state[node] = 2;  // fully done
    return false;
  }
  
  for (let i = 0; i < numCourses; i++) {
    if (hasCycle(i)) return false;
  }
  return true;
}

The three-state approach (0/1/2) avoids the recStack set from Chapter 12. State 1 = "currently in DFS path." Finding state 1 again = back edge = cycle.

Follow-up LeetCode 210: return the actual topological order. Just return result from Kahn's instead of checking completed === numCourses.

Problem 4: Pacific Atlantic Water Flow

LeetCode 417

Given an m×n island height matrix, water flows from a cell to adjacent cells with equal or lower height. Pacific ocean touches top/left borders. Atlantic ocean touches bottom/right borders. Return all cells from which water can flow to BOTH oceans.

What do I have? Height matrix.
What do I want? Cells that can reach both Pacific and Atlantic.
Brute force? For every cell, BFS/DFS to check if it can reach Pacific AND Atlantic. O((m×n)² ).
Where is the waste? We're doing redundant work. Instead: start from the ocean borders and work backwards — find cells that can reach Pacific by flowing uphill from the Pacific border, and similarly for Atlantic. The intersection of these two sets is the answer.

The reversal insight: "Water flows from high to low" means "water FROM cell X can reach a border" is equivalent to "starting from the border and going uphill, we can reach cell X." Same connectivity, reversed direction of flow.

javascript

function pacificAtlantic(heights) {
  const rows = heights.length, cols = heights[0].length;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  
  function bfsFromBorder(starts) {
    const reachable = Array.from({ length: rows }, () => new Array(cols).fill(false));
    const queue = [...starts];
    starts.forEach(([r, c]) => reachable[r][c] = true);
    
    while (queue.length > 0) {
      const [r, c] = queue.shift();
      
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
        if (reachable[nr][nc]) continue;
        if (heights[nr][nc] < heights[r][c]) continue;  // going uphill only
        
        reachable[nr][nc] = true;
        queue.push([nr, nc]);
      }
    }
    
    return reachable;
  }
  
  // Pacific: top row + left column
  const pacStarts = [];
  for (let r = 0; r < rows; r++) pacStarts.push([r, 0]);
  for (let c = 0; c < cols; c++) pacStarts.push([0, c]);
  
  // Atlantic: bottom row + right column
  const atlStarts = [];
  for (let r = 0; r < rows; r++) atlStarts.push([r, cols - 1]);
  for (let c = 0; c < cols; c++) atlStarts.push([rows - 1, c]);
  
  const pacific = bfsFromBorder(pacStarts);
  const atlantic = bfsFromBorder(atlStarts);
  
  const result = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (pacific[r][c] && atlantic[r][c]) result.push([r, c]);
    }
  }
  return result;
}

Why BFS from borders instead of DFS from each cell?

DFS from each cell: O(m²n²) — m×n cells, each DFS is O(m×n).
BFS from borders: O(m×n) — each cell visited at most twice (once per BFS).

The reversal makes the problem tractable.

Dry run on:

code

heights = [
  [1, 2, 2, 3, 5],
  [3, 2, 3, 4, 4],
  [2, 4, 5, 3, 1],
  [6, 7, 1, 4, 5],
  [5, 1, 1, 2, 4]
]

Pacific BFS starts from top row and left column. It spreads to neighbors that are >= current height. The Pacific-reachable set would include cells from which water naturally drains toward top/left.

Atlantic BFS starts from bottom row and right column. Similarly.

The intersection (cells in both sets) is the answer.

Expected output: [[0,4],[1,3],[1,4],[2,2],[3,0],[3,1],[4,0]].

Problem 5: Number of Connected Components in an Undirected Graph

LeetCode 323

Given n nodes and a list of undirected edges, return the number of connected components.

Two solutions side by side:

DFS Solution

javascript

function countComponents(n, edges) {
  const graph = Array.from({ length: n }, () => []);
  for (const [u, v] of edges) {
    graph[u].push(v);
    graph[v].push(u);
  }
  
  const visited = new Set();
  let components = 0;
  
  function dfs(node) {
    visited.add(node);
    for (const neighbor of graph[node]) {
      if (!visited.has(neighbor)) dfs(neighbor);
    }
  }
  
  for (let i = 0; i < n; i++) {
    if (!visited.has(i)) {
      dfs(i);
      components++;
    }
  }
  
  return components;
}

Union-Find Solution

javascript

function countComponents(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = new Array(n).fill(0);
  let components = n;
  
  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);  // path compression
    return parent[x];
  }
  
  function union(x, y) {
    const px = find(x), py = find(y);
    if (px === py) return;
    if (rank[px] < rank[py]) parent[px] = py;
    else if (rank[px] > rank[py]) parent[py] = px;
    else { parent[py] = px; rank[px]++; }
    components--;
  }
  
  for (const [u, v] of edges) union(u, v);
  return components;
}

Which to use? If edges are given all at once, DFS is simpler. If edges arrive dynamically (one by one) and you need the component count after each addition, Union-Find is correct — you can't re-run DFS efficiently after each edge.

Problem 6: Alien Dictionary

LeetCode 269 — Hard, asked at Airbnb, Facebook

Given a list of words sorted in an alien language's alphabetical order, determine the order of characters in the alien alphabet.

Input: ["wrt", "wrf", "er", "ett", "rftt"]
Output: "wertf"

What do I have? Words in alien sorted order.
What do I want? Topological ordering of characters.
Key insight? Compare adjacent words to extract ordering constraints. If word A comes before word B and they differ at position i, then A[i] comes before B[i] in the alien alphabet. This gives directed edges in a graph. Topological sort gives the alphabet order.

Gotcha: If word A is a prefix of word B and A appears after B (e.g., ["abc", "ab"]), the input is invalid — return "".

javascript

function alienOrder(words) {
  // Initialize adjacency list with all unique characters
  const graph = new Map();
  for (const word of words) {
    for (const ch of word) {
      if (!graph.has(ch)) graph.set(ch, new Set());
    }
  }
  
  // Extract ordering constraints
  for (let i = 0; i < words.length - 1; i++) {
    const w1 = words[i], w2 = words[i + 1];
    const minLen = Math.min(w1.length, w2.length);
    
    // Check invalid case: w1 is longer and w2 is prefix of w1
    if (w1.length > w2.length && w1.startsWith(w2)) return "";
    
    for (let j = 0; j < minLen; j++) {
      if (w1[j] !== w2[j]) {
        graph.get(w1[j]).add(w2[j]);  // w1[j] comes before w2[j]
        break;  // only first difference matters
      }
    }
  }
  
  // Kahn's topological sort
  const inDegree = new Map();
  for (const ch of graph.keys()) inDegree.set(ch, 0);
  for (const [, neighbors] of graph) {
    for (const nb of neighbors) {
      inDegree.set(nb, (inDegree.get(nb) || 0) + 1);
    }
  }
  
  const queue = [];
  for (const [ch, deg] of inDegree) {
    if (deg === 0) queue.push(ch);
  }
  
  let result = '';
  while (queue.length > 0) {
    const ch = queue.shift();
    result += ch;
    for (const neighbor of graph.get(ch)) {
      inDegree.set(neighbor, inDegree.get(neighbor) - 1);
      if (inDegree.get(neighbor) === 0) queue.push(neighbor);
    }
  }
  
  return result.length === graph.size ? result : '';  // '' if cycle exists
}

Full dry run on ["wrt", "wrf", "er", "ett", "rftt"]:

code

Characters: w, r, t, f, e

Compare "wrt" vs "wrf": w=w, r=r, t≠f → edge t→f
Compare "wrf" vs "er":  w≠e → edge w→e
Compare "er"  vs "ett": e=e, r≠t → edge r→t
Compare "ett" vs "rftt": e≠r → edge e→r

Graph:
  t → [f]
  w → [e]
  r → [t]
  e → [r]
  f → []

inDegree: t:1, f:1, w:0, e:1, r:1

Queue (in-degree 0): [w]

Step 1: dequeue w, result="w"
  w→e: inDegree[e]-- = 0 → enqueue e
  queue=[e]

Step 2: dequeue e, result="we"
  e→r: inDegree[r]-- = 0 → enqueue r
  queue=[r]

Step 3: dequeue r, result="wer"
  r→t: inDegree[t]-- = 0 → enqueue t
  queue=[t]

Step 4: dequeue t, result="wert"
  t→f: inDegree[f]-- = 0 → enqueue f
  queue=[f]

Step 5: dequeue f, result="wertf"

result.length=5=graph.size → return "wertf" ✓

Time: O(C) where C = total characters across all words (for building the graph) + O(V + E) for topological sort = O(C).

Problem 7: Walls and Gates (Multi-source BFS)

LeetCode 286

Given a 2D grid with values:

-1: Wall (obstacle)
0: Gate
INF (2147483647): Empty room

Fill each empty room with the distance to its nearest gate. If impossible to reach a gate, leave as INF.

Key insight: Instead of BFS from every empty room to find the nearest gate (O(m²n²)), do multi-source BFS from ALL gates simultaneously. The first time each room is reached, that's the minimum distance.

javascript

function wallsAndGates(rooms) {
  const rows = rooms.length, cols = rooms[0].length;
  const INF = 2147483647;
  const dirs = [[1,0],[-1,0],[0,1],[0,-1]];
  const queue = [];
  
  // Enqueue all gates simultaneously as the initial frontier
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (rooms[r][c] === 0) queue.push([r, c, 0]);
    }
  }
  
  while (queue.length > 0) {
    const [r, c, dist] = queue.shift();
    
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
      if (rooms[nr][nc] !== INF) continue;  // wall (-1) or already set
      
      rooms[nr][nc] = dist + 1;
      queue.push([nr, nc, dist + 1]);
    }
  }
}

Multi-source BFS pattern: Start BFS from multiple sources simultaneously. The BFS level structure ensures each node is reached via the shortest path from any source. This is a recurring pattern: nearest exit in a maze, rotting oranges (LeetCode 994), etc.

Time: O(m×n) — each cell visited at most once.

Pattern Summary

Problem	Graph type	Algorithm	Key insight
Number of Islands	Undirected grid	DFS	Flood-fill, mark `'#'`
Clone Graph	Undirected, cyclic	DFS + HashMap	Register clone before recursing
Course Schedule	Directed	Kahn's BFS or DFS+state	No cycle = can finish
Pacific Atlantic	Undirected grid	Reverse BFS	Flow backward from borders
Connected Components	Undirected	DFS or Union-Find	Count DFS starts
Alien Dictionary	Directed DAG	Topo sort (Kahn's)	Diff adjacent words → edges
Walls and Gates	Undirected grid	Multi-source BFS	BFS from all gates at once

Interview Tips

"Should I use BFS or DFS?"
If they ask for shortest path or distance → BFS. If they ask for existence of path, count of components, or need topological order → either works; DFS is often simpler to code.

"How do you handle cycles?"
Undirected: visited set + parent check. Directed: three-state DFS (0/1/2) or detect when result.length < n in Kahn's.

"What if the graph is disconnected?"
Loop over all nodes, run DFS/BFS from each unvisited node. This is the for (let i = 0; i < n; i++) if (!visited.has(i)) dfs(i) pattern.

"What's the time complexity?"
Always O(V + E) for BFS/DFS. For grid problems, V = m×n, E = O(m×n) (at most 4 edges per cell), so O(m×n).

Common mistakes:

Forgetting to mark visited at enqueue time (BFS) → same node enqueued multiple times
Not handling the "w1 is longer than w2 but w2 is prefix of w1" invalid case in Alien Dictionary
In directed cycle detection, using visited instead of recStack → false negatives
In Clone Graph, registering clone after recursion → infinite loop on cycles