Number of Islands

Examples

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

The top-left block of four 1s is one island, the single 1 in the middle is a second island, and the two 1s in the bottom-right corner (connected to each other) form a third.

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

Every land cell is reachable from every other land cell through horizontal/vertical neighbors, so it's all one island.

Input: grid = [["0","0"],["0","0"]]
Output: 0

There's no land at all.

Constraints

• 1 <= rows, cols <= 300

• grid[i][j] is either "0" or "1"

Approach

The key idea behind this whole problem is traversal: starting from one cell and visiting every cell connected to it before moving on. Think of it like flood-filling a region in a paint program - you click one land cell, and the "spread" touches every land cell reachable from it through up/down/left/right steps.

Scan the grid in order. Whenever you land on an unvisited "1", you've found a new island: increase your count by one, then spread out from that cell to visit (and mark) every connected land cell so you never count it again. Once the spread finishes, keep scanning for the next unvisited "1".

The spreading step can be done two ways, and both give the same correct answer:

- Depth-first search (DFS) - dive down one direction as far as possible (recursively visiting a neighbor's neighbor's neighbor...) before backtracking to try other directions. - Breadth-first search (BFS) - visit all of a cell's direct neighbors first, using a queue, before moving one step further out.

Either one correctly visits "every land cell connected to this one" - they just differ in the order they visit cells and in whether you use the call stack (DFS) or an explicit queue (BFS).

Solutions

DFS - Recursive Flood Fill

Scan every cell. When an unvisited "1" is found, that's a new island - count it, then recursively visit every land cell reachable from it, marking each one as water ("0") the moment it's visited so it's never revisited. The recursion naturally stops at water cells, grid edges, and already-visited cells.

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== "1") {
      return;
    }

    grid[r][c] = "0"; // mark this land cell as visited

    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") {
        count++;
        dfs(r, c);
      }
    }
  }

  return count;
}

Time: O(rows × cols) · Space: O(rows × cols)

BFS - Iterative Flood Fill

Same idea, but instead of recursion, use a queue: when a new island is found, push its cell onto a queue, then repeatedly pop a cell, mark it visited, and push its unvisited land neighbors, until the queue is empty. This avoids deep recursion on very large grids.

function numIslands(grid) {
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

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

      count++;
      grid[r][c] = "0";
      const queue = [[r, c]];

      while (queue.length > 0) {
        const [row, col] = queue.shift();
        const neighbors = [[row + 1, col], [row - 1, col], [row, col + 1], [row, col - 1]];

        for (const [nr, nc] of neighbors) {
          if (nr >= 0 && nr < rows && nc >= 0 && nc < cols && grid[nr][nc] === "1") {
            grid[nr][nc] = "0";
            queue.push([nr, nc]);
          }
        }
      }
    }
  }

  return count;
}

Time: O(rows × cols) · Space: O(rows × cols)