Number of Islands II

Number of Islands II

What is this problem about?

The Number of Islands II problem presents an initially all-water grid. A sequence of land-addition operations is given: each operation converts a water cell to land. After each operation, report the current number of islands. This hard coding problem requires dynamic connectivity updates — exactly what Union-Find is designed for.

Why is this asked in interviews?

Uber, Meta, Dropbox, Amazon, TikTok, and Google ask this because it's the canonical Union-Find dynamic connectivity problem. Unlike static island counting (DFS/BFS), additions require efficiently merging components. The array, union find, and hash table interview pattern is the core, and the problem demonstrates why Union-Find is superior to DFS for dynamic problems.

Algorithmic pattern used

Union-Find with online updates. Initialize all cells as water (no components). For each addition at (r,c): set cell as land, increment island count by 1 (new independent island). For each of the 4 neighbors: if the neighbor is land and in a different component, union them and decrement the island count by 1. Use path compression and union-by-rank for efficiency.

Example explanation

Grid 3×3. Operations: [(0,0),(0,1),(1,2),(2,1),(1,1)].

• Add (0,0): islands=1. Neighbors: none land.
• Add (0,1): islands=2. Neighbor (0,0) is land → union. islands=1.
• Add (1,2): islands=2. No land neighbors.
• Add (2,1): islands=3. No land neighbors.
• Add (1,1): islands=4. Neighbors: (0,1) land, (1,2) land, (2,1) land. Union each → islands=4-3=1. Result per step: [1,1,2,3,1].

Common mistakes candidates make

• Reconnecting cells in the same component multiple times (each union only counts if roots differ).
• Not handling the 2D grid-to-1D Union-Find index correctly: r * cols + c.
• Using DFS for each operation (O(n*m) per operation vs O(α) per operation with UF).
• Forgetting that operations can be on already-land cells (check and skip).

Interview preparation tip

Number of Islands II is the prototypical Union-Find problem for dynamic graph problems. The pattern: initialize, add node, check neighbors, union if in different components, track component count. This pattern generalizes to "count connected components after adding edges," "friend circle problem with dynamic additions," and "network connectivity monitoring." Master the 2D→1D index mapping and Union-Find with path compression — these are the two technical building blocks needed.