# Number of Islands

> How to solve Number of Islands: count connected land clusters in a grid by flood filling each cluster with depth-first or breadth-first search.

- Difficulty: Medium
- Category: Graphs
- Topics: Array, DFS, BFS, Union Find, Matrix
- Published 2026-08-21

## 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

```typescript
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.

---

Canonical URL: https://www.marauderbot.com/questions/number-of-islands
