IntermediateGraphs
A grid is a graph: counting islands with DFS
Each cell is a node joined to its 4 neighbours. Every time you find unvisited land, flood it with DFS and count one island.
The idea
You don't need to build a graph for a grid: a cell's neighbours are just up, down, left and right. Walk every cell; when you hit land you haven't visited, that's a new island. Flood-fill from it so the rest of that island is marked and never counted again.
Marking can be done in place (turn '1' into '0'), so no extra visited set is needed.
Worked example
Grid rows: 1 1 0 / 0 1 0 / 0 0 1
- (0,0) is land → island 1 → flood (0,0), (0,1), (1,1)
- (2,2) is land and unvisited → island 2
- Answer 2.
In code (Python)
def num_islands(grid):
rows, cols = len(grid), len(grid[0])
def flood(r, c):
if r < 0 or c < 0 or r >= rows or c >= cols or grid[r][c] != "1":
return
grid[r][c] = "0" # visited
flood(r + 1, c); flood(r - 1, c); flood(r, c + 1); flood(r, c - 1)
islands = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
islands += 1
flood(r, c)
return islandsO(rows × cols) time; recursion depth up to the island size.
How to spot it
- “islands”, “regions”, “connected areas”, “flood fill”, anything over a 2-D grid of cells.
Common mistakes
- Checking bounds after indexing, which crashes at the edges.
- Forgetting to mark cells, so DFS loops forever between two neighbours.
Practise it
Go further
Up next for you · Beginner
“Have I seen this?” is a set →