Graphs/Practice/Number of Islands
Number of Islands - Flood Fill Explained Visually
Scan the grid once. Every time you find land nobody has visited yet, that is a new island - count it, then flood from that cell, marking every connected piece of land as visited (in the grid itself) so it is never counted twice.
Why it works
Flood fill guarantees each cell is processed at most a constant number of times, so a grid of m×n cells costs O(m·n) total - you cannot do better since you must read every cell. Marking land as visited in the grid avoids a separate visited set.
The problem
Given a 2D grid of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically.
Hints
- Iterate through every cell. When you find a '1', start a DFS/BFS.
- Mark visited cells as '0' (or use a visited set) to avoid re-counting.
- Each DFS/BFS call from an unvisited '1' counts as one island.
- The 4 directions are up, down, left, right.
Test cases
| Input | Expected |
|---|---|
grid with 1 connected island | 1 |
grid with 3 separate islands | 3 |
Reference starter code
def num_islands(grid):
# DFS flood-fill approach
pass
grid1 = [
["1","1","1","1","0"],
["1","1","0","1","0"],
["1","1","0","0","0"],
["0","0","0","0","0"]
]
print(num_islands(grid1)) # 1
grid2 = [
["1","1","0","0","0"],
["1","1","0","0","0"],
["0","0","1","0","0"],
["0","0","0","1","1"]
]
print(num_islands(grid2)) # 3
More challenges in this topic
Try it yourself
Solve it in the browser editor with real test cases and instant feedback - free, no signup needed.
Next challenge in this topic: Course Schedule