Number of Islands
Matrix & Grid: lesson 4 of 5
Count a blob once, then erase it so it cannot count twice.
Lesson 4 of 5 · 5 min
Number of Islands
Step 1 of 10
Every 1 is land and every 0 is water. How many separate islands are on the board?
The Idea
Sweep the grid row by row. The first land cell you meet belongs to an island nobody has counted, so add one to the total.
Then flood it: visit every connected land cell and mark it, with a queue or plain recursion. When the flood finishes the island is gone from the board, and the sweep carries on past cells it can safely ignore.
Real-World Example
This is how a paint program counts separate shapes, how a chip-testing pass counts clusters of dead pixels, and how a map service groups nearby search hits into one marker. Any "how many blobs are in this bitmap" question is this algorithm.
The Code
def count_islands(g):
rows, cols, total = len(g), len(g[0]), 0
def sink(r, c):
if not (0 <= r < rows and 0 <= c < cols) or g[r][c] != 1:
return # off-grid or water
g[r][c] = 0 # erase as you go
for n in ((r-1, c), (r+1, c), (r, c-1), (r, c+1)):
sink(*n)
for r in range(rows):
for c in range(cols):
if g[r][c] == 1:
total += 1 # a blob nobody has seen
sink(r, c)
return total
print(count_islands([[1, 1, 0, 0, 1],
[1, 0, 0, 1, 1],
[0, 0, 1, 0, 0],
[0, 0, 1, 0, 0]])) # 3Your turn
Put the steps in the right order.
- Flood every connected land cell, erasing each one
- Sweep to the next cell that is still land
- Add one to the island count
- Report the total once the sweep leaves the grid
Mini quiz
1 / 3