TL;DR
Count connected components of land: scan the grid and flood-fill (DFS or BFS) each new island once — O(m·n) time, O(m·n) space worst case.
Approach 1 — DFS flood fill (baseline and optimal)
The natural solution is already linear, so there is no slower brute force to improve on.
An island is a connected component of '1's. Scan the grid; the first unvisited land cell starts a new island, and a DFS from it marks every land cell reachable through 4-directional moves, so no cell is counted twice. DFS explores one direction fully before backtracking, so it is short to write recursively.
def numIslands(grid: list[list[str]]) -> int:
m, n = len(grid), len(grid[0])
def sink(r: int, c: int) -> None:
if r < 0 or r >= m or c < 0 or c >= n or grid[r][c] != "1":
return
grid[r][c] = "0" # mark visited by sinking to water
sink(r + 1, c)
sink(r - 1, c)
sink(r, c + 1)
sink(r, c - 1)
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] == "1":
count += 1
sink(r, c)
return count
Walkthrough (grid = [["1","1","0"],["1","0","0"],["0","0","1"]]): first '1' at (0,0) → count 1; sink spreads to (0,1) and (1,0), turning that L-shape to water. Scanning continues; next '1' is (2,2) → count 2; sink it. No more land. Result 2.
Complexity: every cell is visited a constant number of times → O(m·n) time. Space is O(m·n) in the worst case — a grid that is all land makes the recursion stack as deep as the number of cells (e.g. a single snaking island).
Approach 2 — BFS flood fill
Same component counting, but the flood-fill uses an explicit queue instead of recursion. Prefer BFS for large all-land grids (up to 300×300 = 90,000 cells), where recursive DFS could exceed Python’s recursion limit; prefer DFS for its brevity when the depth is safe.
from collections import deque
def numIslands(grid: list[list[str]]) -> int:
m, n = len(grid), len(grid[0])
count = 0
for r in range(m):
for c in range(n):
if grid[r][c] != "1":
continue
count += 1
grid[r][c] = "0"
queue = deque([(r, c)])
while queue:
cr, cc = queue.popleft()
for dr, dc in ((1, 0), (-1, 0), (0, 1), (0, -1)):
nr, nc = cr + dr, cc + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1":
grid[nr][nc] = "0" # mark on enqueue
queue.append((nr, nc))
return count
Complexity: O(m·n) time, O(min(m, n)) queue size in the worst case (the BFS frontier), O(m·n) overall including the grid.
Approach 3 — Union-Find
Treat each cell as a node and union each land cell with its already-scanned neighbors. Scanning top-to-bottom, left-to-right, it suffices to check the up and left neighbors; every adjacency is covered exactly once. The number of distinct roots among land cells is the island count. Union-find (disjoint-set union) tracks these merges in near-constant time per operation via path compression and union by size.
def numIslands(grid: list[list[str]]) -> int:
m, n = len(grid), len(grid[0])
parent = {}
rank = {}
count = 0
def find(x):
while parent[x] != x:
parent[x] = parent[parent[x]]
x = parent[x]
return x
def union(a, b) -> None:
nonlocal count
ra, rb = find(a), find(b)
if ra == rb:
return
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
rank[ra] += rank[rb]
count -= 1
for r in range(m):
for c in range(n):
if grid[r][c] != "1":
continue
parent[(r, c)] = (r, c)
rank[(r, c)] = 1
count += 1
for dr, dc in ((-1, 0), (0, -1)): # up and left neighbors already seen
nr, nc = r + dr, c + dc
if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == "1":
union((r, c), (nr, nc))
return count
Complexity: O(m·n·α(m·n)) time (α = inverse Ackermann ≈ constant), O(m·n) space for the parent map.
Common pitfalls
- Marking visited too late in BFS. Mark a cell the moment you enqueue it; marking on dequeue lets the same cell enter the queue multiple times and can overcount or blow up memory.
- Counting diagonals. Only the 4 orthogonal directions connect land here — never the 4 diagonals.
- Mutating the input when you must not. Sinking
'1'→'0' destroys the grid; if the caller needs it intact, use a separate visited set instead.
- Recursion depth. A near-full 300×300 grid can overflow recursive DFS — switch to BFS or union-find.
Pattern takeaway
Counting groups on a grid is connected-components counting: scan for an unvisited seed, flood-fill its whole component with DFS or BFS, and increment. Overwriting visited cells in place keeps the extra space per cell at O(1). Choose BFS over DFS when depth could exhaust the stack, and use union-find when connections arrive incrementally or components must merge on the fly.