#200 - Number of Islands

MediumGraphs - BFS

Given an m × n 2D grid of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.

Input	Output
grid = [["1","1","1","1","0"],["1","1","0","1","0"],["1","1","0","0","0"],["0","0","0","0","0"]]	1
grid = [["1","1","0","0","0"],["1","1","0","0","0"],["0","0","1","0","0"],["0","0","0","1","1"]]	3

Solution Space

Try it

/**
 * Counts the number of islands (connected components of '1's).
 * BFS flood-fill: for each unvisited land cell, enqueue it and expand
 * in all 4 directions, marking cells visited as we go.
 *
 * @param grid m×n grid of '1' (land) and '0' (water)
 * @returns Number of islands
 */
export function numIslands(grid: string[][]): number {
  const m = grid.length;
  const n = grid[0].length;
  let count = 0;
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  for (let r = 0; r < m; r++) {
    for (let c = 0; c < n; c++) {
      if (grid[r][c] !== "1") continue;

      count++;
      grid[r][c] = "0"; // mark visited before enqueuing
      const queue: [number, number][] = [[r, c]];

      while (queue.length > 0) {
        const [row, col] = queue.shift()!;
        for (const [dr, dc] of dirs) {
          const nr = row + dr;
          const nc = col + dc;
          if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc] === "1") {
            grid[nr][nc] = "0"; // mark visited
            queue.push([nr, nc]);
          }
        }
      }
    }
  }

  return count;
}

Approach: BFS flood-fill – for each unvisited land cell, increment the island count and BFS to mark all connected land as visited.

Time: O(m · n) – each cell enqueued at most once.

Space: O(min(m, n)) – the BFS queue holds at most one full diagonal of the grid at peak.

Alternative approaches:

Approach	Idea	Time	Space
DFS	Same flood-fill but recursive; simpler code, deeper stack	O(m · n)	O(m · n) call stack worst case
Union-Find	Union adjacent land cells, count distinct components	O(m · n · α(m · n))	O(m · n)

Why BFS is preferred here: avoids worst-case O(m · n) recursion stack depth (large all-land grids can overflow the call stack with DFS); BFS queue depth is bounded by O(min(m, n)).

#1466 Reorder Routes to Make All Paths Lead to the City Zero

#994 Rotting Oranges