Number of Islands II (LeetCode 305)
Picture an m x n grid that begins entirely underwater (every cell 0). A stream of positions then arrives, each one a [row, col] cell that gets converted to land.
Every time one cell converts, tally the current total island count and stash it; return the whole list of those running tallies, one entry per conversion.
An island here means a maximal cluster of land cells touching horizontally or vertically; anything past the grid's outer edge counts as water.
Worked Examples
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]][1,1,2,3](0,0) makes 1 island, and (0,1) joins it, still 1. (1,2) is not next to either, so there are 2 islands. (2,1) touches none of them, so there are 3.m = 1, n = 1, positions = [[0,0]][1]⚖️Formal Constraints & Bounds
1 <= m, n, positions.length <= 1041 <= m * n <= 104positions[i].length == 20 <= ri < m0 <= ci < n
Core Insight
A cell always starts as its own island (+1); every successful union() with an already-land neighbor proves two previously-separate islands just fused, so it always costs exactly -1 -- the opposite signal of Redundant Connection's union() returning False for a cycle.
Real-World Scenario & Production Applications
Live incremental connectivity tracking in infrastructure-as-it-is-built systems: counting connected power grid segments, network partitions, or land-parcel clusters as new nodes come online one at a time, without re-scanning the whole system after each addition.
Subproblems & Recurrence Decomposition3 Phases
For each incoming (r, c) in the stream, compute idx = r * n + c. If that cell is already land, the count is unchanged -- just re-report the current running total and move to the next operation.
idx = r * n + c
if is_land[idx]:
result.append(island_count)
continueStep-by-Step Execution Trace Table
| Operation | Cell (r,c) | idx | Land Neighbors Found | Union Merges | Running island_count |
|---|---|---|---|---|---|
| 1 | (0,0) | 0 | none | 0 | 1 |
| 2 | (0,1) | 1 | (0,0) | 1 (union(1,0)) | 1 |
| 3 | (1,2) | 5 | none | 0 | 2 |
| 4 | (2,1) | 7 | none | 0 | 3 |
| 1 | dsu = DSU(m * n) |
| 2 | is_land = [False] * (m*n) |
| 3 | island_count = 0 |
| 4 | result = [] |
| 5 | for r, c in positions: |
| 6 | idx = r*n + c |
| 7 | if is_land[idx]: |
| 8 | result.append(island_count) |
| 9 | continue |
| 10 | is_land[idx] = True |
| 11 | island_count += 1 |
| 12 | for each of the 4 neighbors: |
| 13 | if the neighbor is land and dsu.union(idx, neighbor): |
| 14 | island_count -= 1 |
| 15 | result.append(island_count) |
| 16 | return result |
Conceptual Narrative
The DSU Capstone: instead of re-flooding the entire grid after each land addition, an online Union-Find maintains running island counts incrementally in O(alpha(MN)) time per operation.
🧭 Conceptual Foundation & Pattern Intuition
Every other Number of Islands problem is offline: the full grid is provided up front, and one DFS/BFS pass counts connected components in time. Number of Islands II is online: the grid starts entirely as water, and land cells arrive sequentially as a stream of coordinates positions. After each individual addition, we must report the current total island count.
Re-running flood-fill after each land addition would cost , timing out instantly.
The online fix uses Disjoint Set Union:
- Flatten 2D coordinates to a 1D index:
idx = r * cols + c. - When a land cell arrives:
- If it is already land (duplicate operation), the island count does not change.
- Otherwise, mark it as land and increment
island_count += 1(it is initially its own new island).
- Inspect its 4 cardinal neighbors (North, South, East, West). If an adjacent neighbor is already land, attempt
dsu.union(idx, neighbor_idx). - If
dsu.union()returnsTrue(the neighbor belonged to a different island), those two islands have merged: decrementisland_count -= 1.
🏝️ The Analogy: Raising Volcanic Atolls and Connecting Inter-Island Bridges
Imagine an empty ocean. An undersea volcano pushes an atoll above water. At that instant, it is a brand new solitary island (+1 island). The construction crew immediately inspects the 4 adjacent coordinates: if an neighboring plot of land already exists, they pour concrete to bridge them together. If that neighboring land was part of a separate island, the bridge fuses the two landmasses into one continuous island (-1 island). If the neighbor was already connected through a back-atoll horseshoe, the bridge is redundant and the island count remains unchanged.
🔑 Why It Works
The beauty is the exact semantic duality with cycle detection: in Redundant Connection, union == False signals a cycle; here, union == True signals that two previously isolated components fused, dictating an exact -1 adjustment.
Adding already existing land cell: If an incoming position is already land (
grid[r][c] == 1), it is a duplicate operation and must NOT increment the island count.Flattening 2D coordinates to 1D index: Correctly mapping
(r, c)tor * n + cin the disjoint set parent array.Unifying with non-land neighbor cells: Only perform
union()with neighbor cells that are already initialized as land (grid[nr][nc] == 1).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Grid starts all-water + a STREAM of add-land operations + must report the running island count after EACH operation.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a newly-activated cell is its own island until proven otherwise; every union() that returns True (a real merge, not a self-loop) means two previously-distinct islands just became one, decrementing the count by exactly 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Re-running a full DFS/BFS flood-fill over the whole grid after each operation: this is the naive O(kmn) approach the online DSU exists to avoid.
Double-counting a merge: union() must only decrement the count when it returns True (roots were actually different), not on every neighbor check.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I maintain a DSU over all m*n grid cells plus a running island_count. For each incoming position, if it's already land I just re-report the current count. Otherwise I flip it to land, increment island_count by 1 (it starts as its own island), then check all 4 neighbors: for every neighbor that is already land, I call union() and decrement island_count by 1 for every successful (non-cycle) merge. I append island_count after every operation. This runs in O(k · alpha(mn)) amortized time instead of O(k · m · n) for k operations."
Complexity & Mathematical Proof
O(k · alpha(mn))
Look at the execution steps: For each of k positions, one union-find find/union call per operation and a constant 4-neighbor scan. Each find/union is O(alpha(mn)) amortized with path compression and union by rank. Total: O(k · alpha(mn)).
O(mn) Auxiliary
Look at memory allocations: parent, rank and is_land are each sized m*n, O(mn). find calls itself once per level of a tree, and union by rank keeps every tree at most log2(mn) + 1 levels tall, so the call stack is O(log(mn)). The result list holds one count per position.
T(k, m, n) = O(k · α(mn))
Derivation Progression
is_land[idx] = True; island_count += 1
O(1) constant-time activation and optimistic increment for each of the k operations.
4 × union(idx, neighbor) = O(α(mn))
Checking and unioning with up to 4 cardinal neighbors, each union costing O(alpha(mn)) amortized.
O(k · α(mn))
k operations, each O(alpha(mn)) amortized -- vastly cheaper than O(k · m · n) full re-scans.
Variable Definitions
Number of positions in the operation stream (positions.length)
Grid dimensions (rows, columns)
Inverse Ackermann function (α ≤ 4) from path compression + union by rank
Memory Architecture & Bounds
O(log(mn)) Recursive find, union by rank
O(mn) DSU parent + rank arrays and is_land boolean array
O(k) Result list, one entry per operation
Boundary Best / Worst Cases
if all positions are duplicates of already-land cells.
full incremental merging.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "online incremental positions", "number of islands after each addLand operation". Dynamic connectivity in a 2D grid: land cells are added sequentially over time. Running DFS/BFS per query takes ( ops, TLE). A Senior SWE uses DSU with 2D-to-1D Index Flattening: each new land starts as an island (+1), and merging with adjacent existing land decrements count (-1).
operations. Time budget: near-linear time (ms).
Duplicate operations: if the same position is added multiple times, do NOT increment count; append the current count directly.
Number of Islands II (LeetCode 305)
Picture an m x n grid that begins entirely underwater (every cell 0). A stream of positions then arrives, each one a [row, col] cell that gets converted to land.
Every time one cell converts, tally the current total island count and stash it; return the whole list of those running tallies, one entry per conversion.
An island here means a maximal cluster of land cells touching horizontally or vertically; anything past the grid's outer edge counts as water.
Worked Examples
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]][1,1,2,3](0,0) makes 1 island, and (0,1) joins it, still 1. (1,2) is not next to either, so there are 2 islands. (2,1) touches none of them, so there are 3.m = 1, n = 1, positions = [[0,0]][1]⚖️Formal Constraints & Bounds
1 <= m, n, positions.length <= 1041 <= m * n <= 104positions[i].length == 20 <= ri < m0 <= ci < n
Core Insight
A cell always starts as its own island (+1); every successful union() with an already-land neighbor proves two previously-separate islands just fused, so it always costs exactly -1 -- the opposite signal of Redundant Connection's union() returning False for a cycle.
Real-World Scenario & Production Applications
Live incremental connectivity tracking in infrastructure-as-it-is-built systems: counting connected power grid segments, network partitions, or land-parcel clusters as new nodes come online one at a time, without re-scanning the whole system after each addition.
Subproblems & Recurrence Decomposition3 Phases
For each incoming (r, c) in the stream, compute idx = r * n + c. If that cell is already land, the count is unchanged -- just re-report the current running total and move to the next operation.
idx = r * n + c
if is_land[idx]:
result.append(island_count)
continueStep-by-Step Execution Trace Table
| Operation | Cell (r,c) | idx | Land Neighbors Found | Union Merges | Running island_count |
|---|---|---|---|---|---|
| 1 | (0,0) | 0 | none | 0 | 1 |
| 2 | (0,1) | 1 | (0,0) | 1 (union(1,0)) | 1 |
| 3 | (1,2) | 5 | none | 0 | 2 |
| 4 | (2,1) | 7 | none | 0 | 3 |
| 1 | dsu = DSU(m * n) |
| 2 | is_land = [False] * (m*n) |
| 3 | island_count = 0 |
| 4 | result = [] |
| 5 | for r, c in positions: |
| 6 | idx = r*n + c |
| 7 | if is_land[idx]: |
| 8 | result.append(island_count) |
| 9 | continue |
| 10 | is_land[idx] = True |
| 11 | island_count += 1 |
| 12 | for each of the 4 neighbors: |
| 13 | if the neighbor is land and dsu.union(idx, neighbor): |
| 14 | island_count -= 1 |
| 15 | result.append(island_count) |
| 16 | return result |
Conceptual Narrative
The DSU Capstone: instead of re-flooding the entire grid after each land addition, an online Union-Find maintains running island counts incrementally in O(alpha(MN)) time per operation.
🧭 Conceptual Foundation & Pattern Intuition
Every other Number of Islands problem is offline: the full grid is provided up front, and one DFS/BFS pass counts connected components in time. Number of Islands II is online: the grid starts entirely as water, and land cells arrive sequentially as a stream of coordinates positions. After each individual addition, we must report the current total island count.
Re-running flood-fill after each land addition would cost , timing out instantly.
The online fix uses Disjoint Set Union:
- Flatten 2D coordinates to a 1D index:
idx = r * cols + c. - When a land cell arrives:
- If it is already land (duplicate operation), the island count does not change.
- Otherwise, mark it as land and increment
island_count += 1(it is initially its own new island).
- Inspect its 4 cardinal neighbors (North, South, East, West). If an adjacent neighbor is already land, attempt
dsu.union(idx, neighbor_idx). - If
dsu.union()returnsTrue(the neighbor belonged to a different island), those two islands have merged: decrementisland_count -= 1.
🏝️ The Analogy: Raising Volcanic Atolls and Connecting Inter-Island Bridges
Imagine an empty ocean. An undersea volcano pushes an atoll above water. At that instant, it is a brand new solitary island (+1 island). The construction crew immediately inspects the 4 adjacent coordinates: if an neighboring plot of land already exists, they pour concrete to bridge them together. If that neighboring land was part of a separate island, the bridge fuses the two landmasses into one continuous island (-1 island). If the neighbor was already connected through a back-atoll horseshoe, the bridge is redundant and the island count remains unchanged.
🔑 Why It Works
The beauty is the exact semantic duality with cycle detection: in Redundant Connection, union == False signals a cycle; here, union == True signals that two previously isolated components fused, dictating an exact -1 adjustment.
Adding already existing land cell: If an incoming position is already land (
grid[r][c] == 1), it is a duplicate operation and must NOT increment the island count.Flattening 2D coordinates to 1D index: Correctly mapping
(r, c)tor * n + cin the disjoint set parent array.Unifying with non-land neighbor cells: Only perform
union()with neighbor cells that are already initialized as land (grid[nr][nc] == 1).
4-Phase Thought Process Model
Pattern Recognition Signals
The 10-second spot
Grid starts all-water + a STREAM of add-land operations + must report the running island count after EACH operation.
Formulating the Predicate & Invariants
Turning intuition into a boolean rule
Invariant: a newly-activated cell is its own island until proven otherwise; every union() that returns True (a real merge, not a self-loop) means two previously-distinct islands just became one, decrementing the count by exactly 1.
Silent Failure Traps & Edge Cases
Where confident candidates still lose points
Re-running a full DFS/BFS flood-fill over the whole grid after each operation: this is the naive O(kmn) approach the online DSU exists to avoid.
Double-counting a merge: union() must only decrement the count when it returns True (roots were actually different), not on every neighbor check.
The 60-Second Interview Pitch
Say this out loud before you type a single line
"I maintain a DSU over all m*n grid cells plus a running island_count. For each incoming position, if it's already land I just re-report the current count. Otherwise I flip it to land, increment island_count by 1 (it starts as its own island), then check all 4 neighbors: for every neighbor that is already land, I call union() and decrement island_count by 1 for every successful (non-cycle) merge. I append island_count after every operation. This runs in O(k · alpha(mn)) amortized time instead of O(k · m · n) for k operations."
Complexity & Mathematical Proof
O(k · alpha(mn))
Look at the execution steps: For each of k positions, one union-find find/union call per operation and a constant 4-neighbor scan. Each find/union is O(alpha(mn)) amortized with path compression and union by rank. Total: O(k · alpha(mn)).
O(mn) Auxiliary
Look at memory allocations: parent, rank and is_land are each sized m*n, O(mn). find calls itself once per level of a tree, and union by rank keeps every tree at most log2(mn) + 1 levels tall, so the call stack is O(log(mn)). The result list holds one count per position.
T(k, m, n) = O(k · α(mn))
Derivation Progression
is_land[idx] = True; island_count += 1
O(1) constant-time activation and optimistic increment for each of the k operations.
4 × union(idx, neighbor) = O(α(mn))
Checking and unioning with up to 4 cardinal neighbors, each union costing O(alpha(mn)) amortized.
O(k · α(mn))
k operations, each O(alpha(mn)) amortized -- vastly cheaper than O(k · m · n) full re-scans.
Variable Definitions
Number of positions in the operation stream (positions.length)
Grid dimensions (rows, columns)
Inverse Ackermann function (α ≤ 4) from path compression + union by rank
Memory Architecture & Bounds
O(log(mn)) Recursive find, union by rank
O(mn) DSU parent + rank arrays and is_land boolean array
O(k) Result list, one entry per operation
Boundary Best / Worst Cases
if all positions are duplicates of already-land cells.
full incremental merging.
Recurrence Tree Topology
Senior SWE Deconstruction & Hardware Caveats
Triggers: "online incremental positions", "number of islands after each addLand operation". Dynamic connectivity in a 2D grid: land cells are added sequentially over time. Running DFS/BFS per query takes ( ops, TLE). A Senior SWE uses DSU with 2D-to-1D Index Flattening: each new land starts as an island (+1), and merging with adjacent existing land decrements count (-1).
operations. Time budget: near-linear time (ms).
Duplicate operations: if the same position is added multiple times, do NOT increment count; append the current count directly.