Number of Islands

MediumGraphsArrayDFSBFSUnion FindMatrix

Problem

You are given a grid where each cell is either land or water. An island is a group of land cells connected to each other horizontally or vertically (not diagonally), surrounded by water or the edge of the grid. Count how many separate islands the grid contains.

Example. In a grid where land cells form one L-shaped cluster in the top-left and a single isolated land cell in the bottom-right, the answer is 2.

Key idea

Scanning cell by cell does not by itself say where one island ends and another begins: you need to track which land cells a cluster you already counted has claimed. The fix is a flood fill: whenever the scan lands on an unvisited land cell, that is a new island, so increment the count and explore outward from it, visiting every land cell reachable through a chain of up-down-left-right neighbors and marking each one visited along the way. Because every reachable cell gets marked, the scan never recounts it as the seed of another island. Depth-first search (often recursive) or breadth-first search (with a queue) both work for the exploration; Union-Find is a third option, joining adjacent land cells into sets and counting the distinct sets left.

Solution

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

  function explore(row: number, col: number): void {
    // out of bounds or not unvisited land: nothing to explore
    if (row < 0 || row >= rows || col < 0 || col >= cols || grid[row][col] !== '1') {
      return;
    }
    grid[row][col] = '0'; // mark visited before recursing so it is not revisited
    explore(row + 1, col);
    explore(row - 1, col);
    explore(row, col + 1);
    explore(row, col - 1);
  }

  for (let row = 0; row < rows; row++) {
    for (let col = 0; col < cols; col++) {
      if (grid[row][col] === '1') {
        islands++; // unvisited land found: start of a new island
        explore(row, col);
      }
    }
  }

  return islands;
}

Complexity

  • Time: O(rows × cols). Every cell is visited and marked exactly once across all flood fills combined.
  • Space: O(rows × cols). Visited marks (or the recursion stack, for an all-land grid) can grow to the size of the grid.

Watch out for

  • Only orthogonal neighbors count as connected; diagonal land cells belong to different islands.
  • Mark a cell visited the moment you enqueue or recurse into it, not after processing it, or it can be explored twice.
  • Bounds-check before looking at a neighbor to avoid reading outside the grid.

Pattern

This is the classic flood-fill and connected-components pattern applied to an implicit grid graph. The same scan-and-flood-fill idea reappears in Max Area of Island, Surrounded Regions, and Pacific Atlantic Water Flow.

Related questions