p21 — Number of Islands

Source: LeetCode 200 · Medium · Topics: DFS, BFS, Union-Find, Matrix Companies (2024–2025 frequency): Amazon (very high), Meta (very high), Google (high), Microsoft (high), Bloomberg (high), Apple (high), LinkedIn (medium), Salesforce (medium), Goldman Sachs (medium) Loop position: absolutely standard phone screen or first onsite round. Possibly the most-asked graph question on the planet.

1. Quick Context

A 2D grid of '1's (land) and '0's (water). Count connected components of land cells (4-connectivity).

This is the canonical grid-as-implicit-graph problem. Three things make it interview-defining:

1. It looks trivial. Anyone can hack a working solution. But the interview signal lives in how cleanly you handle: visited marking, recursion-depth blow-up on large grids, the iterative-vs-recursive trade-off, and whether you mutate the input or not (and announce it).
2. It’s the entry point to an entire family. Max Area of Island (LC 695), Island Perimeter (LC 463), Surrounded Regions (LC 130), Number of Closed Islands (LC 1254), Number of Enclaves (LC 1020), Number of Distinct Islands (LC 694) — all variants of this template.
3. Three correct solutions exist (DFS, BFS, Union-Find), each with different trade-offs. Senior+ candidates know all three and can argue when to use which.

What it looks like it tests: can you code DFS on a grid. What it actually tests: (a) do you reach for visited reflexively, (b) do you handle recursion depth like a professional, (c) can you sketch all three approaches without panicking, (d) do you ask “may I mutate the grid?” before you do.

2. LeetCode Link + Attempt Gate

🔗 https://leetcode.com/problems/number-of-islands/

STOP. 15-min timer. Try DFS first; if you finish, try BFS. Don’t peek.

3. Prerequisite Concepts

• p20 — BFS with deque and level-snapshot pattern
• phase-04-graphs/labs/lab-02-dfs-connected-components.md
• phase-04-graphs/labs/lab-01-bfs-shortest-path.md
• phase-04-graphs/labs/lab-07-union-find-applications.md — for the third solution

4. How to Approach (FRAMEWORK Steps 1–9)

Step 1 — Restate: “Given a 2D grid of '1' (land) and '0' (water) chars, count the number of connected components of '1's under 4-directional connectivity (up/down/left/right; diagonals do NOT connect).”

Step 2 — Clarify:

• “4-directional or 8-directional connectivity?” (LC: 4-directional.)
• “May I mutate the input grid?” (LC: doesn’t say; ASK in interview. Mutation as visited-marker saves O(MN) memory.)
• “Are values guaranteed '1'/'0' chars, or integers?” (LC: chars. Easy bug source.)
• “Empty grid?” (Return 0.)
• “What’s the max grid size?” (LC: 300×300. Small enough that recursion is safe — but state this.)

Step 3 — Constraints: M, N up to 300 → 90k cells max. O(MN) time and O(MN) space (visited + recursion stack worst case). Recursion depth could be MN = 90k in a path-shaped island — borderline; switch to iterative if M or N > ~500.

Step 4 — Examples:

• [["1","1","0"],["1","0","0"],["0","0","1"]] → 2 (top-left blob + bottom-right cell).
• All water → 0.
• All land → 1.
• Single cell [["1"]] → 1.

Step 5 — Brute Force: There isn’t really a “brute force” here that’s distinct from the canonical solution. The canonical DFS/BFS is O(MN), which is optimal. Mention this.

Step 6 — Complexity: O(MN) time (each cell visited at most twice — once by outer loop, once by DFS/BFS). O(MN) space worst case for visited set + recursion stack.

Step 7 — Pattern Recognition: “Grid + connected regions” → connected components on an implicit graph. The grid IS the graph; cells are nodes, 4-neighbor adjacency is the edge relation. Same template you’ll use for flood-fill, region-coloring, image-segmentation.

Step 8 — Develop: Outer loop over every cell. If land + unvisited → increment count + flood-fill (DFS or BFS) marking all connected cells visited.

DIRS = ((1, 0), (-1, 0), (0, 1), (0, -1))

def num_islands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    visited = [[False]*n for _ in range(m)]
    count = 0
    for r in range(m):
        for c in range(n):
            if grid[r][c] == '1' and not visited[r][c]:
                count += 1
                dfs(r, c)  # marks all connected as visited
    return count

Step 9 — Test: All-water, all-land, single cell, large path-shaped island (recursion depth stress), the canonical 3×3 example.

5. Progressive Hints

If stuck for 5 min, open hints.md.

6. Deeper Insight — The Three Solutions Compared

For static LC 200: DFS or BFS — either correct. The Union-Find variant is over-engineered for the base problem but the correct answer for the dynamic follow-up.

Why “visited when enqueuing” beats “visited when dequeuing”: If you mark visited at dequeue, a single cell can be enqueued many times by multiple neighbors before any of them dequeues it. The queue grows to O(MN) in the worst case. Mark visited immediately on enqueue (and on the source before BFS starts) to keep the queue bounded by the frontier size.

The mutation trick: Many top solutions flip grid[r][c] = '0' to mark visited, saving O(MN) memory for the visited array. In an interview, always announce this: “I’m going to use the grid itself as the visited marker by flipping '1' to '0' — this destroys the input but saves O(MN) memory. Is that acceptable?” That sentence is a Senior+ signal.

7. Anti-Pattern Analysis

1. Forgetting to mark visited at the source. q = deque([(r, c)]) without visited[r][c] = True. The source gets re-enqueued by its neighbors. Causes duplicate counts and infinite loops.
2. Mark-on-dequeue instead of mark-on-enqueue. Queue grows to O(MN). Works but wasteful and a bug-prone pattern.
3. Recursive DFS on a 500×500 grid in Python. RecursionError on path-shaped islands. Either bump sys.setrecursionlimit (with explanation) or switch to iterative.
4. Checking grid[r][c] == 1 instead of == '1'. Chars vs ints. The interviewer is watching for this.
5. Iterating for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)] inside the inner loop. Allocates a fresh list every call. Hoist DIRS to module level.
6. Mutating the grid without announcing it. Marks you as “didn’t think about ownership of caller state.” Even one sentence — “I’ll mutate; let me know if I should clone first” — recovers the signal.

8. Skills & Takeaways

• The grid-as-implicit-graph reframe — recognize “2D grid + connectivity” as a graph problem in 5 seconds.
• Mark-visited-on-enqueue discipline — applies to every BFS you’ll ever write.
• DFS vs BFS choice on grids — recursion depth vs frontier memory; pick by grid shape.
• The mutation announcement — “may I mutate the input?” before doing it.
• DIRS as a module constant — a small habit that signals professionalism.
• The three-solution map — DFS / BFS / Union-Find; when to use each.

9. When to Move On

Move on when:

• You can write recursive DFS, iterative BFS, AND Union-Find for this in under 5 minutes each.
• You correctly handle: empty grid, single-cell grid, all-water, all-land, the canonical example.
• You can articulate when Union-Find is the right answer (dynamic follow-up; LC 305).
• You can sketch LC 695 (Max Area of Island), LC 463 (Island Perimeter), LC 1254 (Closed Islands) as 30-second variations.
• Your stress test runs BFS and DFS on 1000 random grids and confirms they return the same count.

10. Company Context

Amazon:

• Default SDE-I / SDE-II first-round question. Bar Raisers pivot to “what if the grid is too big to fit in memory?” → answer: stream row-by-row, maintain row above + Union-Find merging across rows.
• Watch for: “now compute the area of each island, sorted descending.” Quick mod of the DFS to count and collect.
• Scorecard phrase: “Coding Excellence — clean DFS, announced visited strategy, handled recursion-depth concern.”

Meta:

• Asks LC 200 then immediately LC 305 (Number of Islands II — dynamic land additions). This is THE Union-Find showcase. Have it ready.
• Often asks LC 694 (Distinct Islands) as the harder follow-up — count shape-distinct islands via canonical-form hashing of DFS paths.
• Scorecard phrase: “Strong — handled both static and dynamic variants; recognized Union-Find applicability.”

Google:

• May skip 200 and start at LC 130 (Surrounded Regions — flip enclosed 'O's) or LC 1254 (Closed Islands). Both require the boundary-BFS-inversion trick from this week’s p24.
• Will ask correctness proof for the visited strategy. Be ready to argue “every cell is visited exactly once” formally.
• Scorecard phrase: “Algorithm — clean, correct, with clear complexity argument.”

Microsoft:

• Standard first round. May ask the 8-connectivity variant. Trivial change to DIRS (add 4 diagonals) but explicitly ask before assuming.
• Scorecard phrase: “Solid — clarified connectivity model upfront; correct solution.”

Bloomberg:

• Frames as “region detection in tick data” or “grouping connected trades.” Often paired with a follow-up about finding the largest island or computing per-island statistics.
• Scorecard phrase: “Pragmatic — adapted template to domain framing.”

Apple:

• May ask the streaming variant: cells arrive one at a time; after each, report the current number of islands. This is the dynamic Union-Find variant in disguise (LC 305).
• Scorecard phrase: “Strong — pivoted to Union-Find for the streaming case.”

11. Interviewer’s Lens

12. Level Delta

Mid (L4):

• Writes DFS with a visited array.
• Counts components correctly.
• Knows BFS exists; can switch if asked.

Senior (L5):

• Announces “may I mutate?” before flipping '1' to '0'.
• Hoists DIRS to module constant.
• Discusses recursion-depth trade-off.
• Solves LC 695 (Max Area) as a 30-second variant.

Staff (L6):

• Articulates DFS/BFS/Union-Find trade-off matrix upfront.
• Implements LC 305 (dynamic islands) with Union-Find on demand.
• Mentions LC 694 (distinct islands) and the canonical-form hashing for shape comparison.
• Discusses how the algorithm parallelizes (per-tile DFS + cross-tile Union-Find merge).

Principal (L7+):

• Reframes as “labeled image connected component analysis” — same algorithm shipped in OpenCV / scikit-image.
• Discusses the streaming variant memory bound: only need one row of state for row-by-row Union-Find.
• Notes that the algorithm is the same as 2-pass connected component labeling in image processing (Hoshen-Kopelman algorithm).
• Discusses cache-locality of row-major DFS vs BFS on giant grids.

13. Follow-up Q&A

Q1: What if the grid doesn’t fit in memory? A: Stream row-by-row. Maintain the previous row’s label assignments. When processing a new row, union new land cells with land cells directly above (same column) via Union-Find. After the last row, count distinct roots. Memory: O(N) (single row) + O(MN) for the Union-Find structure — or better, evict resolved labels as soon as a row passes out of scope, dropping to O(N).

Q2: What if cells are added dynamically (LC 305 — Number of Islands II)? A: Use Union-Find. Initialize: 0 islands, all cells unmarked. For each new land cell (r, c):

• Mark it land, increment count.
• For each of the 4 neighbors that’s also land: if its root ≠ current cell’s root, union them, decrement count.
• Append current count to result. Time: O(K · α(MN)) for K additions. Standard Union-Find variant; very common follow-up at Meta.

Q3: How would you count distinct island shapes (LC 694)? A: Run DFS for each island, but record the relative path of moves (e.g., “RDLU” for right/down/left/up). Canonicalize (e.g., start from top-left-most cell of the island, fix traversal order). Insert canonical-form strings into a set; answer = len(set). This converts shape comparison into string hashing.

Q4: Parallelize this — say, across 8 CPU cores. A: Tile the grid (e.g., 8 horizontal strips). Run DFS independently in each tile, assigning local component IDs. Then sweep the strip boundaries: for each pair of adjacent land cells across a boundary, Union-Find merge their local IDs. Final count = distinct roots. Speedup is bounded by the boundary length to area ratio.

Q5: Why is 4-connectivity vs 8-connectivity not just a constant factor? A: For counting, the difference is a constant 2× in DIRS size — same O(MN). But the resulting graph can be very different: a checkerboard pattern has all cells disconnected under 4-conn but fully connected under 8-conn. Always clarify connectivity in the first 30 seconds.

14. Solution Walkthrough

See solution.py:

• num_islands_dfs(grid) — recursive DFS with visited array (canonical, recommended for small grids).
• num_islands_bfs(grid) — iterative BFS with deque and mark-on-enqueue (canonical, safer for large grids).
• num_islands_uf(grid) — Union-Find with path compression + union by rank (overengineered for static, but the right base for LC 305).
• num_islands_mutate(grid) — DFS that mutates the grid as visited marker (the “I asked, you said OK” version).
• UnionFind class — find with path compression, union with rank.
• stress_test() — 1000 random grids; all four solutions return the same count.
• edge_cases() — empty, all-water, all-land, single cell, the canonical LC examples, a “spiral” grid that stresses recursion depth.

Run: python3 solution.py → “ALL TESTS PASSED”.

15. Beyond the Problem

Principal-engineer code review comment:

“Three things. First: please hoist DIRS to module scope; allocating a 4-tuple per cell visit is exactly the kind of microcost that compounds when this runs on 100M-cell images in our pipeline. Second: the recursive variant is fine for LC, but ship the iterative one — we’ve had production incidents where this exact algorithm hit RecursionError on adversarial inputs (carefully shaped to maximize path length). Iterative-with-explicit-stack is defensively correct. Third: if you ever do the streaming variant for our row-by-row image processor, please use the two-pass connected component labeling algorithm (Hoshen-Kopelman), not naive Union-Find — it’s the published-since-1976 right answer and our image team will recognize it. The fact that LeetCode never mentions this name doesn’t mean we shouldn’t use it.”

Connections forward:

• p24 (Pacific Atlantic) uses the same grid-BFS template with the boundary-inversion trick.
• Phase 4 — phase-04-graphs/labs/lab-07-union-find-applications.md deepens the Union-Find variant.
• Production: image segmentation, satellite map parsing, terrain analysis, GIS connected-region detection, game-of-life region tracking, percolation theory simulations.
• The Hoshen-Kopelman algorithm (the streaming/row-by-row version) is THE algorithm used in computational physics for percolation cluster analysis.
• LC 305 is the canonical dynamic follow-up; have it warm.