Frontend Beauty
ESC

Type to search the knowledge base.

Number of Islands

Count islands in a grid with DFS or BFS flood fill — graph framing, complexity, and common grid bugs.

intermediate4 min read
  • dsa
  • graph
  • dfs
  • bfs
  • matrix
  • interview
  • Google
  • Meta
  • Amazon
  • Microsoft
  • Uber

The problem

Given an m × n 2D binary grid grid where '1' is land and '0' is water, return the number of islands.

An island is land connected 4-directionally (up/down/left/right) — not diagonals unless the interviewer says so.

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

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

Mental model: each cell is a graph node; edges to 4-neighbors that are land. Count connected components.

Brute / naive thoughts

Scanning and “remembering shapes” without a visited structure fails on non-rectangles. You need flood fill or Union-Find.

Optimal: DFS flood fill

Scan every cell. On each unvisited land:

  1. islands++
  2. DFS/BFS mark the whole component as water (or visited)

Mutating the grid to '0' avoids a separate visited matrix (clarify if mutation is OK).

function numIslands(grid: string[][]): number {
  if (!grid.length) return 0;
  const rows = grid.length;
  const cols = grid[0].length;
  let count = 0;

  function dfs(r: number, c: number): void {
    if (r < 0 || c < 0 || r >= rows || c >= cols) return;
    if (grid[r][c] !== "1") return;
    grid[r][c] = "0";
    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(m · n) — each cell entered O(1) times
Space O(m · n) worst-case recursion depth (one big island)

BFS version (safer stack depth)

function numIslandsBfs(grid: string[][]): number {
  const rows = grid.length;
  if (!rows) return 0;
  const cols = grid[0].length;
  let count = 0;
  const dirs = [
    [1, 0],
    [-1, 0],
    [0, 1],
    [0, -1],
  ];

  function bfs(sr: number, sc: number): void {
    const q: [number, number][] = [[sr, sc]];
    grid[sr][sc] = "0";

    while (q.length) {
      const [r, c] = q.shift()!;
      for (const [dr, dc] of dirs) {
        const nr = r + dr;
        const nc = c + dc;
        if (nr < 0 || nc < 0 || nr >= rows || nc >= cols) continue;
        if (grid[nr][nc] !== "1") continue;
        grid[nr][nc] = "0";
        q.push([nr, nc]);
      }
    }
  }

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

Interview note: shift() is O(n) on arrays — for huge grids use an index pointer or deque. Fine for interview-scale grids if you mention it.

Union-Find (optional flex)

Union each land with right/down neighbors; count roots that are land. Good signal if you’ve practiced DSU; not required for the classic problem.

Edge cases

  • Empty grid / empty rows
  • All water → 0
  • All land → 1
  • Single cell
  • Checkerboard lands → many islands of size 1
  • Diagonal touch only — not same island under 4-connectivity

Common bugs

  • 8-directional accidental diagonals
  • Not marking visited before enqueue (BFS) → exponential blowup
  • Bounds checks after indexing
  • Counting cells instead of components
  • Deep DFS on large island → stack overflow in some runtimes; switch to BFS/iterative DFS

Follow-ups

  1. Max Area of Island — size of largest component
  2. Pacific Atlantic Water Flow — multi-source DFS
  3. Number of enclaves / closed islands
  4. Surrounded regions — flood from borders

Interview delivery

  1. Clarify 4- vs 8-connectivity and mutability.
  2. Frame as connected components.
  3. Implement DFS or BFS flood fill.
  4. Complexity O(mn).
  5. Mention stack depth / BFS if they probe.

Further reading