Graph Traversal: How to Conquer Grid Problems (Number of Islands, Clone Graph, Pacific Atlantic)

You're in the interview. The problem says: "Given an m x n grid of '1's and '0's, return the number of islands." Your first instinct might be to just loop through the grid. That loop part is right — the key is knowing what to do when you find a '1'.

Graph traversal on a grid is one of those patterns where once it clicks, you'll see it everywhere. Number of Islands. Pacific Atlantic Water Flow. Surrounded Regions. Word Search. Flood Fill. They all reduce to the same mechanic: you're at a cell, and you need to explore everything reachable from it.

The Core Pattern

Before touching a single problem, get the mental model straight.

Every 2D grid is just a graph in disguise. Each cell is a node. Adjacent cells (up, down, left, right) are the edges. The moment you accept that, grid problems become graph problems — and you already know how to solve graph problems: DFS or BFS.

DFS on a grid uses recursion (or an explicit stack). You go deep into one path before backtracking.

BFS on a grid uses a queue. You explore level by level — all immediate neighbors first, then their neighbors.

For "how many connected components" style problems, DFS is the easier implementation. For shortest path or minimum steps, BFS is what you want. Keep that rule of thumb handy.

The sink-and-mark approach is key: when you find unvisited land, mark the entire island as visited (flip it to '0' or add to a visited set) so you don't count it again.

Problem 1: Number of Islands (LeetCode 200)

The problem: Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is a group of adjacent '1's (connected horizontally or vertically) surrounded by water.

The Brute Force Reality

There's no simpler approach here that avoids traversal. You have to explore each island fully to avoid double-counting. The "brute force" and the optimal are both DFS/BFS — the difference is just whether you use a separate visited array or mark the grid in-place.

Optimal: DFS with In-Place Marking

// Time: O(m * n), Space: O(m * n) worst case for recursion stack
const numIslands = (grid) => {
  let count = 0;
 
  const dfs = (r, c) => {
    if (r < 0 || r >= grid.length) return;
    if (c < 0 || c >= grid[0].length) return;
    if (grid[r][c] !== '1') return;
 
    grid[r][c] = '0'; // sink the land so we don't revisit
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  };
 
  for (let r = 0; r < grid.length; r++) {
    for (let c = 0; c < grid[0].length; c++) {
      if (grid[r][c] === '1') {
        count++;
        dfs(r, c); // flood-fill the entire island
      }
    }
  }
 
  return count;
};

The trick: modifying the input grid in-place avoids a separate visited array. If the interviewer doesn't want you to mutate the input, use a Set with string keys like `${r},${c}`.

BFS Version (Stack-Safe)

// Time: O(m * n) — each cell read once, and reading by index is O(1)
// Space: O(min(m, n)) average — two adjacent BFS frontiers
const numIslandsBFS = (grid) => {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;
 
  const dirs = [[1,0], [-1,0], [0,1], [0,-1]];
 
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] !== '1') continue;
 
      count++;
      let queue = [[r, c]];
      grid[r][c] = '0';
 
      while (queue.length) {
        const next = []; // the next frontier — no queue.shift(), see the note below
 
        for (const [row, col] of queue) {
          for (const [dr, dc] of dirs) {
            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';
              next.push([nr, nc]);
            }
          }
        }
 
        queue = next;
      }
    }
  }
 
  return count;
};

Both versions visit each cell at most once — that's O(m×n) time guaranteed.

Problem 2: Clone Graph (LeetCode 133)

The problem: Given a reference to a node in a connected undirected graph where each node has a value and a neighbors list, return a deep copy of the entire graph.

This one trips people up because it's not a grid — it's a real adjacency-list graph. But the traversal pattern is the same: explore every node exactly once and build the copy as you go.

The catch: graphs can have cycles. A node can be a neighbor of one of its own neighbors. If you don't track what you've already cloned, you'll recurse forever.

Brute Force: Naively Recurse

Just DFS into each node and clone it. Problem: when you hit a cycle, you revisit a node you've already cloned and try to clone it again. Infinite loop.

Optimal: DFS with a Clone Map

// Time: O(V + E), Space: O(V) for the clone map
const cloneGraph = (node) => {
  if (!node) return null;
 
  const cloneMap = new Map(); // original node -> its clone
 
  const dfs = (curr) => {
    if (cloneMap.has(curr)) return cloneMap.get(curr);
 
    const clone = { val: curr.val, neighbors: [] };
    cloneMap.set(curr, clone); // register BEFORE recursing into neighbors
 
    for (const neighbor of curr.neighbors) {
      clone.neighbors.push(dfs(neighbor));
    }
 
    return clone;
  };
 
  return dfs(node);
};

The cloneMap does double duty: it's the visited tracker (prevents infinite recursion on cycles) AND the lookup for already-cloned nodes. When you see a node already in the map, return the existing clone instead of making a new one.

Problem 3: Pacific Atlantic Water Flow (LeetCode 417)

The problem: Given a grid of heights, water can flow to adjacent cells with equal or lower height. Cells on the top and left edges drain to the Pacific ocean. Cells on the bottom and right edges drain to the Atlantic. Find all cells from which water can reach both oceans.

This is a harder grid problem that showcases a classic inversion trick.

Brute Force: Forward Simulation

For every cell, DFS downhill and check if you reach both oceans. Time: O(m²n²) — one DFS per cell, each DFS potentially traversing the whole grid. On a 200×200 grid, that's 1.6 billion operations.

Optimal: Reverse DFS from Ocean Edges

Instead of simulating water flowing down from every cell, reverse the question: start from the ocean edges and find all cells the ocean can "reach" going uphill. Any cell reachable by both oceans is in your answer.

// Time: O(m * n), Space: O(m * n)
const pacificAtlantic = (heights) => {
  const rows = heights.length;
  const cols = heights[0].length;
  const pacific = new Set();
  const atlantic = new Set();
 
  const dfs = (r, c, visited, prevHeight) => {
    const key = `${r},${c}`;
    if (r < 0 || r >= rows || c < 0 || c >= cols) return;
    if (visited.has(key)) return;
    if (heights[r][c] < prevHeight) return; // water can't flow uphill (in the reversed direction)
 
    visited.add(key);
    dfs(r + 1, c, visited, heights[r][c]);
    dfs(r - 1, c, visited, heights[r][c]);
    dfs(r, c + 1, visited, heights[r][c]);
    dfs(r, c - 1, visited, heights[r][c]);
  };
 
  // Seed from Pacific edges (top row + left column)
  for (let r = 0; r < rows; r++) {
    dfs(r, 0, pacific, heights[r][0]);
    dfs(r, cols - 1, atlantic, heights[r][cols - 1]);
  }
  for (let c = 0; c < cols; c++) {
    dfs(0, c, pacific, heights[0][c]);
    dfs(rows - 1, c, atlantic, heights[rows - 1][c]);
  }
 
  const result = [];
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const key = `${r},${c}`;
      if (pacific.has(key) && atlantic.has(key)) {
        result.push([r, c]);
      }
    }
  }
 
  return result;
};

Putting It Together

Here's the mental framework for grid DFS/BFS:

Interview Tips

Call out your approach before coding. Say "This is a graph traversal problem. I'll treat each cell as a node with up to 4 neighbors. I'll DFS from every unvisited land cell and mark it as visited to avoid double-counting." That signals pattern recognition before a single line of code.

Bounds check order matters. Check r < 0 || r >= rows BEFORE accessing grid[r]. Getting this order wrong causes undefined access or out-of-bounds errors that eat interview time.

In-place mutation: Just say "I'll flip visited cells to '0' in place — is that okay?" Most interviewers are fine with it. Some aren't, and they'll tell you to use a separate visited structure.

On complexity: Every cell is visited at most once (that's what marking visited guarantees), so time is O(m×n) for all these grid problems. Space is the same order because in the worst case your visited set or recursion stack holds every cell. You can't do better than O(mn) when you need to potentially look at every cell.

Pacific Atlantic as a follow-up test: If you nail Number of Islands quickly, the interviewer might throw this at you. The "reverse the direction" insight is the unlock — mention it before diving into code. "Instead of checking each cell individually, I'll do two DFS passes from the ocean edges and intersect the results." That's the kind of framing interviewers want to see.