Number of Islands
MediumSink each connected blob of land
When you find land, flood-fill all the connected land so you count each island only once.
The idea
Every time you find unvisited land, recursively sink the entire connected region and count one island. DFS naturally follows each landmass to its edges.
1
1
0
1
1
0
0
0
0
0
1
1
Step 1 of 8. Scan for land (1). Each new blob is one island — DFS sinks its whole region.
1/8
Optimal
timeO(rows·cols)spaceO(rows·cols)
Depth-first sink.
1function sink(r, c) {2 if (oob(r,c) || grid[r][c] !== '1') return;3 grid[r][c] = '0';4 sink(r+1,c); sink(r-1,c); sink(r,c+1); sink(r,c-1);5}Input
- grid
- 3 × 4
Memory
- at
- —
- cells marked
- 0
Output
- islands
- —
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.