Number of Islands

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is formed by horizontally or vertically adjacent land cells.

Why this is worth learning

Recognize a component-counting problem when the answer counts groups rather than cells. Four-neighbor adjacency is the graph; diagonal contact does not connect land. The outer scan chooses one representative per component, and a complete flood fill prevents any other cell in that component becoming a new representative.

Before coding: one-minute experiment

For rows 110 / 010 / 001, how many islands are there? Which cell would be counted twice if a component were only partly marked?

Function signature

func NumIslands(grid [][]byte) int

Inputs / outputs

• grid: matrix of bytes '0'/'1'.
• Return: number of islands.

Example

grid = [
  ["1","1","0","0"],
  ["1","1","0","0"],
  ["0","0","1","0"],
  ["0","0","0","1"],
]
Output: 3

Constraints

• 1 <= rows, cols <= 300

Core idea (near-solution)

Counting land cells overcounts a connected island, while counting only cells with water to the left fails for branching shapes. We need to claim an entire connected component at once. Scan for an unclaimed land cell, count one representative, then follow every legal four-direction land edge from it. Mark each cell before expanding its neighbors so cycles in the grid do not repeat work. When the scan resumes, every member of that island is already claimed. DFS and BFS implement the same component argument; changing to diagonal neighbors changes the graph.

Invariant: once a cell is visited, it will not be counted again.

Algorithm (step-by-step)

1. Initialize count = 0.
2. For each cell:
   • If it is land and unvisited, increment count and flood fill to mark the whole island.
3. Return count.

Correctness sketch

When the outer scan reaches an unmarked land cell, no previously counted component contains it: any such component would already have marked every cell reachable by a land path. The stack starts at this new representative. Every pushed cell is connected to it, and marking on push ensures a cell is pushed at most once. Conversely, induction along a land path shows every cell in its component is eventually reached. Thus one increment accounts for exactly one previously uncounted component. After the scan every original land cell belongs to exactly one counted component.

Trace (hand walkthrough)

Example input:
grid = [
  ["1","1","0","0"],
  ["1","1","0","0"],
  ["0","0","1","0"],
  ["0","0","0","1"],
]
Output: 3

Walk:
- start at (0,0) -> flood fills 4 cells (top-left block), count=1
- next unvisited 1 at (2,2) -> count=2
- next unvisited 1 at (3,3) -> count=3

Pitfalls to avoid

• Forgetting to mark visited before recursing (causes infinite loops).
• Treating diagonal adjacency as connected (it is not).

Debugging lens

Log each count increment and all cells it claims. Mark when pushing, not after popping; otherwise several neighbors can queue the same land cell. Copy the grid before calling when the caller needs the original map.

Complexity

• Time: O(rows * cols).
• Extra space: O(rows * cols) for visited or recursion stack.

Implementation notes (Go)

• You can mutate the grid in-place by flipping '1' to '0' to mark visited.

Contract precision

The reference intentionally mutates every visited land byte from 1 to 0 (character bytes). Input rows must be rectangular. This is a four-direction connectivity problem, not an eight-direction one.

Reconstruction checkpoint

For rows 101 / 010 / 101, count components under the published neighbor rule. Then change to eight-direction neighbors: what answer changes, and which part of the algorithm must change?

Return to Graph General · Module quiz