Number of IslandsMedium

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is land connected horizontally or vertically (not diagonally).

Examples

A 4×5 grid with three separate blobs of connected '1's → Output: 3

Approach

Scan every cell. The moment you find an unvisited '1', that's a brand new island — flood-fill outward from it (DFS or BFS, both work) marking every connected land cell as visited so it's never counted again. The flood-fill is what turns 'a blob of connected land' into 'one island' instead of counting each land cell separately.

Complexity — best & worst case

Time O(rows × cols), best and worst case are the same — every cell is visited exactly once total, across all flood-fills combined

Space (DFS) O(rows × cols) worst case — recursion depth if the whole grid is one island

Space (BFS) O(min(rows, cols)) — the queue holds one frontier layer at a time

Code

// Given a 2D grid of '1' (land) and '0' (water), count the number of
// islands. An island is land connected horizontally/vertically
// (not diagonally).

// --- Approach: for each unvisited land cell, flood-fill (DFS) every
// connected land cell and mark it visited — that flood-fill counts
// as exactly one island. Repeat for the whole grid. ---
function numIslands(grid) {
  if (!grid || grid.length === 0) return 0;

  const rows = grid.length;
  const cols = grid[0].length;
  const visited = new Set();

  function dfs(r, c) {
    const key = `${r},${c}`;
    if (
      r < 0 || r >= rows ||
      c < 0 || c >= cols ||
      grid[r][c] === "0" ||
      visited.has(key)
    ) {
      return;
    }
    visited.add(key);
    dfs(r + 1, c);
    dfs(r - 1, c);
    dfs(r, c + 1);
    dfs(r, c - 1);
  }

  let islands = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === "1" && !visited.has(`${r},${c}`)) {
        islands++;
        dfs(r, c); // mark this entire island as visited
      }
    }
  }
  return islands;
}

// --- Same idea with BFS instead of DFS (iterative, avoids recursion depth
// limits on very large grids) ---
function numIslandsBFS(grid) {
  if (!grid || grid.length === 0) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  const visited = new Set();
  let islands = 0;

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      const key = `${r},${c}`;
      if (grid[r][c] !== "1" || visited.has(key)) continue;

      islands++;
      const queue = [[r, c]];
      visited.add(key);

      while (queue.length) {
        const [row, col] = queue.shift();
        for (const [dr, dc] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
          const nr = row + dr;
          const nc = col + dc;
          const nKey = `${nr},${nc}`;
          if (
            nr >= 0 && nr < rows &&
            nc >= 0 && nc < cols &&
            grid[nr][nc] === "1" &&
            !visited.has(nKey)
          ) {
            visited.add(nKey);
            queue.push([nr, nc]);
          }
        }
      }
    }
  }
  return islands;
}

// --- Example Usage ---
const grid = [
  ["1", "1", "0", "0", "0"],
  ["1", "1", "0", "0", "0"],
  ["0", "0", "1", "0", "0"],
  ["0", "0", "0", "1", "1"],
];
console.log(numIslands(grid));    // 3
console.log(numIslandsBFS(grid)); // 3