Hints — p21 Number of Islands

Read one at a time. Try to solve between each.

Hint 1 — Reframe. This is a grid, but it’s actually a graph. Each cell is a node. Each pair of orthogonally adjacent same-value cells is an edge. “Count islands” = “count connected components of '1'-cells.” Now you know which template to reach for.

Hint 2 — Outer + inner loop structure. Loop over every cell. If you find unvisited land, increment a counter and flood-fill everything reachable from it (marking visited as you go). Then resume the outer loop. The outer loop guarantees you don’t miss disconnected islands.

Hint 3 — Visited tracking. You need to know what you’ve seen. Options: a separate visited[m][n] matrix, OR mutate the grid in place (flip '1' → '0'). The latter saves memory but destroys input — always ask the interviewer first. If you go BFS, mark visited the instant you enqueue, never on dequeue, or your queue blows up.

Hint 4 — DFS or BFS? Both are O(MN) correct. DFS is shorter to write. BFS is safer for huge grids (no recursion-depth risk). For LC’s 300×300 max, recursive DFS is fine. For production, default to iterative BFS or iterative DFS-with-explicit-stack.

Hint 5 — Direction constant. Define DIRS = ((1,0),(-1,0),(0,1),(0,-1)) at module level. Inside the inner loop: for dr, dc in DIRS: nr, nc = r+dr, c+dc; if 0<=nr<m and 0<=nc<n and grid[nr][nc]=='1' and not visited[nr][nc]: .... This pattern is the same for every grid-graph problem you’ll ever solve (p24 Pacific Atlantic uses the identical scaffold).

If still stuck: look at num_islands_bfs in solution.py — it’s the clearest of the four for first-time understanding.