loading

Number of Islands — Step-by-Step Visualization

mediumLeetCode #200ArrayDFSBFSUnion FindMatrix

Given an `m x n` 2D binary grid `grid` which represents a map of '1's (land) and '0's (water), return the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Algorithm Pattern

Flood Fill (DFS/BFS)

Key Idea

We iterate through every cell in the grid. If we find a '1' (land), we increment our island count and immediately perform a DFS or BFS to visit all connected '1's. When we visit a land cell, we mark it as '0' (or 'visited') so it's not counted again. Each complete DFS/BFS trigger corresponds to one isolated island.

Step-by-Step Approach

  1. Initialize `islands = 0`.
  2. Loop through every row `r` and column `c`.
  3. If `grid[r][c] == '1'`:
  4. Increment `islands`.
  5. Trigger DFS starting at `(r, c)`.
  6. In DFS: Mark current cell as '0', recursively call DFS on neighbors (top, bottom, left, right).
  7. Return `islands`.

Common Gotchas

  • Be careful with boundary conditions (index out of bounds).
  • Make sure to treat the grid values as strings if the input format uses '1' and '0'.

Related Problems

← All problems