← Back to Python Examples

Number of Islands

Classic grid BFS/DFS — the flood-fill technique that appears in dozens of problems.

Contents

  1. The Problem
  2. The Flood-Fill Insight
  3. Solution 1 — DFS (Recursive)
  4. Solution 2 — BFS (Iterative)
  5. Trace Through an Example

1. The Problem

Given a 2D grid of '1' (land) and '0' (water), count the number of islands. An island is surrounded by water and formed by connecting adjacent (horizontal/vertical) land cells.

grid = [
    ["1","1","1","1","0"],
    ["1","1","0","1","0"],
    ["1","1","0","0","0"],
    ["0","0","0","0","0"],
]
# Answer: 1  (all connected land is one island)

grid2 = [
    ["1","1","0","0","0"],
    ["1","1","0","0","0"],
    ["0","0","1","0","0"],
    ["0","0","0","1","1"],
]
# Answer: 3

2. The Flood-Fill Insight

Walk every cell. When you find a '1' that hasn't been visited, you've found a new island — increment the count. Then flood-fill from that cell, marking all connected land as visited so you don't count any part of it again.

3. Solution 1 — DFS (Recursive)

def num_islands_dfs(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    def dfs(r, c):
        if r < 0 or r >= rows or c < 0 or c >= cols: return
        if grid[r][c] != '1': return
        grid[r][c] = '#'  # Mark visited by changing the cell
        dfs(r+1, c); dfs(r-1, c)
        dfs(r, c+1); dfs(r, c-1)

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                dfs(r, c)
                count += 1

    return count
We modify the grid in-place (marking '1' as '#') to track visited cells. If you cannot modify the input, use a separate visited set instead.

4. Solution 2 — BFS (Iterative)

Same idea but uses a queue instead of recursion — avoids Python's recursion limit on very large grids.

from collections import deque

def num_islands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    count = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                count += 1
                queue = deque([(r, c)])
                grid[r][c] = '#'
                while queue:
                    row, col = queue.popleft()
                    for dr, dc in [(1,0),(-1,0),(0,1),(0,-1)]:
                        nr, nc = row+dr, col+dc
                        if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                            queue.append((nr, nc))
                            grid[nr][nc] = '#'

    return count
PropertyValue
TimeO(rows × cols) — every cell visited at most once
SpaceO(min(rows, cols)) for BFS queue in the worst case

5. Trace — Finding 3 Islands

# Grid:          After island 1:     After island 2:    After island 3:
# 1 1 0 0 0      # # 0 0 0            # # 0 0 0          # # 0 0 0
# 1 1 0 0 0  →   # # 0 0 0    →       # # 0 0 0    →     # # 0 0 0
# 0 0 1 0 0      0 0 1 0 0            0 0 # 0 0          0 0 # 0 0
# 0 0 0 1 1      0 0 0 1 1            0 0 0 1 1          0 0 0 # #
#                count=1              count=2             count=3  ✓
The [(1,0),(-1,0),(0,1),(0,-1)] pattern for 4-directional movement is worth memorizing — it comes up in almost every grid traversal problem.