Number of Islands

Given a grid of '1's (land) and '0's (water), count the islands — groups of land cells connected up/down/left/right. (LC 200)

This is the flagship of the grid family, and a live-interview favorite because it composes: solve it, and the follow-ups (bigger grids, shortest paths, multiple sources, closed islands) are all one twist away.

The recipe

Say before you type: "Scan every cell. Each time I touch land that hasn't been visited, that's one new island — and I flood-fill the entire island to water so I never count it again."

1. Double loop over the grid.
2. On a '1': increment the count, then sink — DFS in four directions, converting every connected '1' to '0'.
3. The sink's base case does all the guarding: out of bounds, or not land → return.
4. Mark the cell before recursing, not after — marking is the visited set.

The code

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

  const sink = (r: number, c: number): void => {
    if (r < 0 || r >= rows || c < 0 || c >= cols || grid[r][c] !== '1') return;
    grid[r][c] = '0'; // mark visited IMMEDIATELY (prevents infinite revisit)
    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;
}

Why this shape

An island is a connected component, and the grid is an implicit graph — each cell a node, each 4-direction adjacency an edge. Counting components is the classic scan-and-explore: every time the outer scan finds a node no previous exploration reached, that's a component nobody has claimed, so count it and claim all of it.

Overwriting the grid doubles as the visited set — O(1) extra space and no bookkeeping. If mutating the input is off-limits (worth asking, it's a good question), a visited set of "r,c" keys does the same job at O(m·n) space.

Complexity

	Cost	Because
Time	O(m·n)	Each cell is touched a constant number of times: once by the scan, at most once by a sink
Space	O(m·n)	Worst-case recursion depth — one giant serpentine island

Traps

• Read the bounds check out loud. The two classic slips both hide in that one line: a flipped comparison (r < rows where r >= rows belongs — infinite loop), and checking the column against rows — which silently passes on square grids and only bites on rectangular ones. Test on a non-square grid.
• Marking after the four recursive calls instead of before — two adjacent cells recurse into each other forever.
• The grid holds string '1'/'0' on LeetCode, not numbers. !== '1' vs !== 1 is a silent no-match bug.

The escalation: recursion blows the stack

The follow-up to expect on large inputs: a 1000×1000 grid with one snake-shaped island is a million-deep recursion — a real stack overflow. The fix is the same algorithm with an explicit stack:

function sinkIterative(sr: number, sc: number, grid: string[][]): void {
  const stack: [number, number][] = [[sr, sc]];
  grid[sr][sc] = '0';
  const dirs = [[1, 0], [-1, 0], [0, 1], [0, -1]];
  while (stack.length) {
    const [r, c] = stack.pop()!;
    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < grid.length && nc >= 0 && nc < grid[0].length && grid[nr][nc] === '1') {
        grid[nr][nc] = '0'; // mark on PUSH, not on pop — else duplicates pile into the stack
        stack.push([nr, nc]);
      }
    }
  }
}

The one subtlety: mark when pushing, not when popping. Mark-on-pop lets the same cell be pushed from two neighbors before either pops it, and the stack bloats with duplicates.

The pattern this trains

Grid DFS/BFS is a whole question family: Max Area of Island (695), Closed Islands (1254), Rotting Oranges (994, BFS for time), Shortest Path in Binary Matrix (1091, BFS for distance), Pacific Atlantic (417). The variant to know cold: "shortest" or "how long until" means switch the stack for a queue — DFS finds a path, only BFS finds the shortest one.