Number of Islands

Start from brute force

Without a shared visited set, the obvious method floods from every land cell: run a search from each 1, collect the set of cells it reaches, and count the distinct sets at the end. It is correct, because two cells produce the same set exactly when they are on the same island. But each flood can cost O(R · C) and there can be R · C land cells, so time is O((R · C)²), and storing the sets can take as much space. The tempting shortcut, counting land cells with no land above or to the left, is linear and wrong: the U-shaped [[1, 0, 1], [1, 1, 1]] is one island, and it counts two.

The approach

Scan every cell once and flood each island the first time you touch it. The reference num_islands returns 0 for an empty grid, copies it into g with [row[:] for row in grid] so the caller’s data survives, and walks r and c over every cell. When g[r][c] == 1 it has found an island nobody has counted: it adds 1 to count, sinks the cell to 0 and pushes it on stack. The inner loop pops a cell and checks the four offsets in ((1, 0), (-1, 0), (0, 1), (0, -1)); each in-bounds land neighbor is sunk at once and pushed.

Sinking at push time is the invariant that keeps it linear: a cell becomes 0 the moment it is discovered, so it is pushed at most once and can never start a second count. When the stack empties, the whole island is water in g and the scan moves on, so the number of floods started is the number of islands. The TypeScript numIslands is the same line for line.

Walk through an example

On the first example the scan starts one flood at the top-left corner, sinks the L-shaped island, and starts a second flood at the bottom-right cell.

Complexity

Time O(R · C): the scan reads each cell once, and each land cell is pushed and popped at most once with four neighbor checks. Space O(R · C) for the copy g plus the stack, which can also reach O(R · C): an all-land 100 × 100 grid peaks at 4,951 entries. Flooding from every land cell without a shared visited set is O((R · C)²) time.

Edge cases to test

• [[1, 0], [0, 1]] → 2. Diagonal cells do not touch; an eight-direction neighbor list returns 1.
• [] and [[]] → 0. The guard if not grid or not grid[0] covers both; without it, len(grid[0]) raises IndexError on the first.
• [[1, 0, 1], [1, 1, 1]] → 1. The U shape joins along the bottom row; counting land cells with no land above or to the left gives 2.
• A single row of 2,000 land cells → 1. A recursive flood fill goes about 2,000 calls deep and hits Python’s default recursion limit of 1,000; the explicit stack does not.
• [["1", "1"], ["0", "1"]] → 0 here. The best-known version of this problem stores land as the string "1"; this one uses the integer 1, so code written for one silently counts nothing on the other.
• After num_islands(grid) the caller’s grid is unchanged, because the reference sinks cells in the copy g. Sinking the input in place is quicker to write but destroys the caller’s data.

Common mistakes

• Re-counting cells of an island you already flooded — mark cells visited as you go (or mutate them to water).
• Deep recursion blowing the call stack on a large grid — prefer an iterative BFS/DFS.
• Using the wrong connectivity (4-directional vs 8-directional) for the problem.

Follow-ups an interviewer asks next

Return the area of the largest island.

Count cells inside each flood, adding one every time a cell is popped, and keep the maximum across floods. Nothing else changes: time stays O(R · C), and the extra state is two integers. The same hook yields every island’s size, which is the usual next question after counting them.

Land appears one cell at a time. Report the island count after each addition.

Rerunning the flood after every addition is O(R · C) per step. Use union-find instead: a new land cell is its own set and adds 1 to the count, then each union with a land neighbor that joins two different sets subtracts 1. With path compression and union by rank, each addition costs near-constant amortized time.

The grid is too large for memory and arrives row by row.

Label components with a row-by-row scan that keeps only the previous row’s labels and a union-find over those labels. Each land cell takes the label of a land neighbor above or to its left, uniting the two labels when both exist. A component with no cell in the current row is finished and can be counted, so memory is O(C) plus the live labels.

Count islands with distinct shapes.

During each flood, record every cell relative to the cell where the flood started, as (y - r, x - c), sort the offsets, and add the resulting tuple to a set. Islands with the same shape produce the same tuple, so the answer is the set’s size. Counting rotations and reflections as equal means generating all eight transformed copies, shifting each to the origin, and keeping the smallest.

Where this shows up

This is connected-components labeling on a grid, and the same flood-fill drives image segmentation and blob detection, the paint-bucket tool, region labeling, and any “count or size the clusters” task on a graph.

Reference solution

def num_islands(grid):
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    g = [row[:] for row in grid]
    count = 0
    for r in range(rows):
        for c in range(cols):
            if g[r][c] == 1:
                count += 1
                stack = [(r, c)]
                g[r][c] = 0
                while stack:
                    y, x = stack.pop()
                    for dy, dx in ((1, 0), (-1, 0), (0, 1), (0, -1)):
                        ny, nx = y + dy, x + dx
                        if 0 <= ny < rows and 0 <= nx < cols and g[ny][nx] == 1:
                            g[ny][nx] = 0
                            stack.append((ny, nx))
    return count


print(num_islands([[1, 1, 0], [0, 1, 0], [0, 0, 1]]))   # -> 2

function numIslands(grid: number[][]): number {
  if (grid.length === 0 || grid[0].length === 0) return 0;
  const rows = grid.length, cols = grid[0].length;
  const g = grid.map((row) => [...row]);
  let count = 0;
  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (g[r][c] === 1) {
        count++;
        const stack: [number, number][] = [[r, c]];
        g[r][c] = 0;
        while (stack.length) {
          const [y, x] = stack.pop() as [number, number];
          for (const [dy, dx] of [[1, 0], [-1, 0], [0, 1], [0, -1]]) {
            const ny = y + dy, nx = x + dx;
            if (ny >= 0 && ny < rows && nx >= 0 && nx < cols && g[ny][nx] === 1) {
              g[ny][nx] = 0;
              stack.push([ny, nx]);
            }
          }
        }
      }
    }
  }
  return count;
}

console.log(numIslands([[1, 1, 0], [0, 1, 0], [0, 0, 1]]));   // -> 2