AI Hints
Home›DSA in Python Tutorial›Graph Searches
DSA in Python · Lesson 81 of 132

Practice: Counting Islands

Graphs in a grid.

⏱ 2 min read▶ Video at 1:35:57🎓 Free
Watch this lesson in the DSA in Python courseWatch on YouTube ↗Full DSA in Python course

Here's a map, made of ones for land and zeros for water. How many islands are there? An island is land connected up, down, left, or right. Pause. Where's the graph?

Practice: Counting Islands
From the video: Practice: Counting Islands
  • A map of 1s and 0s
  • How many islands?
  • Where's the graph?

Sinking each island

Each land cell is a node, connected to its land neighbours. We scan the grid. When we find unvisited land, that's a new island, so we count it, and flood fill it with depth first search, marking every connected land cell as seen. Run it. Three islands.

islands.pypython
from grid import grid

def count_islands(grid):
    rows, cols, seen = len(grid), len(grid[0]), set()
    def sink(r, c):
        if not (0 <= r < rows and 0 <= c < cols): return
        if grid[r][c] == "0" or (r, c) in seen: return
        seen.add((r, c))
        for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
            sink(r + dr, c + dc)
    islands = 0
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == "1" and (r, c) not in seen:
                islands += 1
                sink(r, c)
    return islands

print(count_islands(grid))
Output
3
Also uses grid.py
grid = [
    "11000",
    "11010",
    "00011",
    "10000",
]

Grids are graphs

Many puzzles hide a graph inside a grid. Mazes, flood fill in paint programs, and game maps. Each cell is a node, and its neighbours are the cells around it. Once you see the graph, breadth first and depth first search solve them all. This takes O of rows times columns.

keyvalue
Cella node
Neighboursup, down, left, right
Flood fillDFS or BFS
CostO(rows × cols)

Summary

Treat each land cell as a node, and flood fill each new island with depth first search. Next, graphs where edges have weights.

Key takeaways
  • Scan for land
  • New land? Count it
  • Flood fill to mark it
Next up: Weighted Graphs — when steps aren't equal