The tell: Count connected regions in a grid — a grid is just an implicit graph.
How you get there
1Each unvisited land cell starts a new island.
2Flood-fill from it, marking everything reachable so it is never counted again.
3The number of times you start a fill is the number of islands.
Solution
Python
from collections import deque
def num_islands(grid: list[list[str]]) -> int:
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":
continue
count += 1
queue = deque([(r, c)])
grid[r][c] = "0" # mark on push, not on pop
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 < rows and 0 <= nc < cols and grid[nr][nc] == "1":
grid[nr][nc] = "0"
queue.append((nr, nc))
return count
Time
O(rows · cols)
Space
O(rows · cols)
What goes wrong
Marking cells visited on pop rather than on push queues the same cell many times.