AlgoViz
HomeGraphs

Number of Islands

Medium

Flood-fill each unvisited land cell

In simple words

Count clumps of connected land by flooding each clump the first time you touch it.

The idea

Scan the grid; each time you hit unvisited land, flood-fill (DFS/BFS) its whole connected blob and count one island. Marking cells visited prevents double counting.

1
1
0
0
1
0
0
1
0
0
1
1
0
0
0
1

Step 1 of 9. Scan for land. Each unvisited '1' starts a new island; flood-fill its whole blob so it isn't counted twice.

1/9
Optimal
timeO(rows·cols)spaceO(rows·cols)

Sink each island you find.

1for (r, c) if (grid[r][c] === '1') {2  islands++;3  sink(r, c); // DFS marks the blob as water4}5function sink(r, c) {6  if (out of bounds || grid[r][c] !== '1') return;7  grid[r][c] = '0';8  for (const [dr, dc] of DIRS) sink(r+dr, c+dc);9}

Input

grid
4 × 4

Memory

at
—
cells marked
0

Output

islands
—
answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
grid = [[1,1,0],[0,1,0],[0,0,1]]
Output:
2
Explanation:
One connected blob of 1s plus a lone 1 → 2 islands.

Example 2

Input:
grid = [[1,1,1],[1,1,1]]
Output:
1
Explanation:
All land is connected → a single island.

Example 3

Input:
grid = [[0,0],[0,0]]
Output:
0
Explanation:
All water → no islands.

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.