Number of Islands

Medium#200grid

You get a map of land and water cells. Land cells that touch by a side form one island; touching by a corner does not count. Count the islands. Our map has 4 rows: # . # ., # . # ., # # # ., . . . # (# is land) — the answer is 2: the first seven land cells make one U-shaped island, and the cell in the bottom right corner is alone.

200 Number of IslandsWalkthrough · 1×

Example: count the islands on a map where one island bends back up, and one cell touches it only by a corner.

01230123~~~~~~~~call stacktop on the right—
land, not seen yetwateron the call stackcurrent cellland next to it, explored nextseen, its island’s number inside

seen is empty: no cell visited yet

01/51
restart · back · play · step
Speed
1function numIslands(grid):
2 seen = empty set
3 islands = 0
4 for each cell (row, col), row by row:
5 if grid[row][col] is land and (row, col) not in seen:
6 islands = islands + 1
7 explore(row, col)
8 return islands
9
10function explore(r, c):
11 seen.add((r, c))
12 for each land neighbour (nr, nc) not in seen:
13 explore(nr, nc)
state
islands
–
row
–
col
–
r
–
c
–
nr
–
nc
–
click a step to go back

← → step · space play/pause

Why it works

  1. explore adds to seen every land cell it can reach by sides, in any direction, up included. So one call covers a whole island, however it bends.
  2. The scan starts a new island only at land that is not in seen yet, so each island is counted once: at its first cell in row-by-row order.
  3. Each land cell goes into seen once and explore runs on it once, so the walk never loops.

Complexity

Time O(rows × cols): each cell is scanned once and each land cell explored once. Memory O(rows × cols) for seen and, at worst, for a call stack as deep as one long island.

nextNow solve it yourself, no hints.

Solve on LeetCode ↗

The problem and its statement belong to LeetCode. Here are our own retelling, example and solution. Patterns Hero is not affiliated with LeetCode.