Number of Islands

The problem

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

Example:

1 1 0 0 0
1 1 0 0 0
0 0 1 0 0
0 0 0 1 1

The answer is 3: the 2×2 block top-left, the lone 1 in the middle, and the pair bottom-right.

Reframe it as a graph problem: cells are nodes, adjacent land cells share an edge, and islands are connected components. Counting components = starting a traversal from every not-yet-visited node and counting the starts.

Approach — DFS flood fill

Scan every cell. On finding land, increment the count and "sink" the whole island with DFS (mark every reachable land cell as water) so it's never counted again.

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

  function sink(r, c) {
    if (r < 0 || r >= rows || c < 0 || c >= cols) return
    if (grid[r][c] !== '1') return
    grid[r][c] = '0' // mark visited by sinking
    sink(r + 1, c)
    sink(r - 1, c)
    sink(r, c + 1)
    sink(r, c - 1)
  }

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '1') {
        count++
        sink(r, c)
      }
    }
  }
  return count
}

Time: O(rows × cols) — each cell is visited a constant number of times. Space: O(rows × cols) worst-case recursion depth (one giant snake-shaped island).

Approach 2 — BFS with a queue

Same idea, but sink iteratively — useful when recursion depth is a concern.

function numIslands(grid) {
  const rows = grid.length
  const cols = grid[0].length
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]]
  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 [cr, cc] = queue.shift()
        for (const [dr, dc] of dirs) {
          const nr = cr + dr
          const nc = cc + dc
          if (
            nr >= 0 && nr < rows &&
            nc >= 0 && nc < cols &&
            grid[nr][nc] === '1'
          ) {
            grid[nr][nc] = '0' // mark when ENQUEUING, not when popping
            queue.push([nr, nc])
          }
        }
      }
    }
  }
  return count
}

Same complexity. Marking cells when they're enqueued (not when popped) prevents the same cell from entering the queue twice.

(A third route worth naming: Union-Find — union every adjacent land pair, then count roots. Overkill here, but it's the tool when islands must merge dynamically, as in Number of Islands II.)

Dry run

DFS on the example grid. The outer scan walks row by row:

Every land cell is touched exactly once by a sink, so no island is double-counted.

Edge cases

• All water → 0; all land → 1 (one big flood fill).
• The grid holds strings '1'/'0' on LeetCode — comparing against the number 1 silently fails.
• Mutating the input grid is the O(1)-extra-space visited marker; if mutation isn't allowed, carry a separate visited set.
• Diagonals don't connect — only 4 directions in dirs.