Q19: Number of Islands (Graph DFS/BFS)

Count the number of distinct islands in a 2D grid of '1's (land) and '0's (water) using Depth-First Search (DFS).

Grid DFS Flood Fill Island Counter

function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;
  let count = 0;
  
  function dfs(r, c) {
    if (r < 0 || c < 0 || r >= grid.length || c >= grid[0].length || grid[r][c] === '0') {
      return;
    }
    grid[r][c] = '0'; // Mark as visited by sinking land
    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);
      }
    }
  }
  return count;
}

💡 Scans every cell. When encountering land ('1'), increments island count and starts DFS flood-fill to mark all connected land cells as visited ('0').

Key Takeaways

Treat grid as an undirected graph and sink visited land nodes by mutating '1' to '0'.
Increments island count on finding an unvisited '1' and triggers flood-fill DFS.

Knowledge Check

Why does the DFS function mutate grid[r][c] = '0' during flood fill?

Q19: Number of Islands (Graph DFS/BFS)

STAY UPDATED WITH BYTES!