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)
This problem has no “brute force worse than optimal” — the natural solution is already linear. The naive-but-correct idea is the answer.
The insight: an island is a connected component of '1's. Walk the grid; the first unvisited land cell you meet starts a new island, and a DFS from it sinks (marks) every land cell reachable through 4-directional moves, so nothing gets double-counted. DFS explores one direction fully before backtracking — natural to write recursively.
class Solution:
def numIslands(self, 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
The insight: identical component-counting, but flood-fill with an explicit queue instead of recursion. BFS is preferred here for large all-land grids (up to 300×300 = 90,000 cells) where recursive DFS could exceed Python’s recursion limit; DFS is preferred for its brevity when depth is safe.
from collections import deque
class Solution:
def numIslands(self, 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
The insight: treat each cell as a node; union each land cell with its right and down land neighbors (checking those two directions while scanning left-to-right, top-to-bottom, covers all adjacencies). 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 rank.
class Solution:
def numIslands(self, 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
“Count the groups” on a grid is connected-components counting: scan for an unvisited seed, flood-fill its whole component with DFS or BFS, and increment. Overwrite-to-mark keeps it O(1) extra space per cell. Choose BFS over DFS when depth could exhaust the stack, and reach for union-find when connections arrive incrementally or you must merge components on the fly.