Definition
Number of Islands II uses dynamic Union-Find to track island counts as land is added.
- Union-Find maintains disjoint sets keyed by flattened cell index (row * cols + col).
- Land addition increments the island count by one for each new singleton island.
- Neighbor merge unions the new cell with each already-land neighbor; each successful union decrements the count.
- Duplicate addition of an already-land cell is a no-op.
- Path compression and union by size keep the tree shallow for near-constant-time operations.
National Bank of India activates banking service in map cells one at a time. Each newly activated cell starts as its own service region, raising the region count by one. If it touches an already-active neighbor, those regions fuse and the count drops. After each activation the team announces how many separate regions currently exist.
Understanding the Concepts
What is the Number of Islands II Problem?
You start with an all-water m x n grid. Land is added one cell at a time at given positions. After each addition, report the current number of islands. An island is a group of connected land cells (horizontally or vertically adjacent).
At National Bank of India, the operations team activates service coverage cells one at a time and needs the running count of contiguous service regions after each activation.
package com.bank.service;
import java.util.ArrayList;
import java.util.List;
public class NumberOfIslandsII {
private int[] parent;
private int[] size;
private int count;
public List<Integer> numIslands2(int m, int n, int[][] positions) {
parent = new int[m * n];
size = new int[m * n];
boolean[] isLand = new boolean[m * n];
java.util.Arrays.fill(parent, -1);
count = 0;
List<Integer> result = new ArrayList<>();
int[][] dirs = {{0,1},{0,-1},{1,0},{-1,0}};
for (int[] pos : positions) {
int r = pos[0], c = pos[1];
int idx = r * n + c;
if (isLand[idx]) {
result.add(count); // duplicate: no change
continue;
}
isLand[idx] = true;
parent[idx] = idx;
size[idx] = 1;
count++; // new singleton island
for (int[] d : dirs) {
int nr = r + d[0], nc = c + d[1];
int nIdx = nr * n + nc;
if (nr >= 0 && nr < m && nc >= 0 && nc < n && isLand[nIdx]) {
if (union(idx, nIdx)) count--; // merged two islands
}
}
result.add(count);
}
return result;
}
private int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // path compression
x = parent[x];
}
return x;
}
private boolean union(int a, int b) {
int ra = find(a), rb = find(b);
if (ra == rb) return false; // already same island
if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }
parent[rb] = ra;
size[ra] += size[rb];
return true; // merged
}
public static void main(String[] args) {
NumberOfIslandsII solver = new NumberOfIslandsII();
int[][] positions = {{0,0},{0,1},{1,2},{2,1},{1,1}};
System.out.println(solver.numIslands2(3, 3, positions));
}
}
[1, 1, 2, 3, 1]
Why Use Union-Find Instead of BFS/DFS?
The static Number of Islands problem (grid given all at once) is solved with BFS/DFS. But the dynamic version adds land one cell at a time and needs the count after each addition. Running BFS/DFS after each addition would be O(k * m * n) total. Union-Find gives near-O(1) per operation, making the total O(k * alpha(m*n)) where alpha is the inverse Ackermann function.
package com.bank.core;
public class WhyUnionFind {
// Static (all-at-once): BFS/DFS O(m*n)
// Dynamic (one cell at a time): Union-Find O(k * alpha(m*n))
// alpha(m*n) is effectively constant for practical sizes
// BFS/DFS after each addition: O(k * m * n) -> too slow
}
How Does the Union-Find Work?
Union-Find (Disjoint Set Union) maintains a forest where each tree represents an island. Each cell points to a parent, and the root of the tree is the representative of the island. Two optimizations keep it fast:
- Path compression: during
find, point each visited node directly to the root. - Union by size: attach the smaller tree under the larger tree's root.
package com.bank.core;
public class UnionFindExplained {
// find(x): walk to root, compress path
// union(a, b): find roots, attach smaller under larger
// If roots are same: already connected, return false
// If roots differ: merge, return true (count--)
// Path compression example:
// Before: 5 -> 3 -> 1 -> 1
// After find(5): 5 -> 1, 3 -> 1 (flattened)
}
How Is This Different from Static Number of Islands?
| Aspect | Static (Number of Islands) | Dynamic (Number of Islands II) |
|---|---|---|
| Input | Full grid given at once | Land added one cell at a time |
| Algorithm | BFS/DFS flood fill | Union-Find with incremental updates |
| Output | Single count | Running count after each addition |
| Time | O(m * n) | O(k * alpha(m*n)) total |
| Handles removal | Not applicable | Not supported by basic Union-Find |
What Are the Edge Cases?
Edge cases include: duplicate land additions (same cell added twice), land added at grid boundaries, and land additions that merge multiple islands at once.
package com.bank.core;
public class IslandsIIEdgeCases {
public static void main(String[] args) {
NumberOfIslandsII solver = new NumberOfIslandsII();
// Duplicate addition: count stays the same
int[][] dup = {{0,0},{0,0}};
System.out.println(solver.numIslands2(2, 2, dup)); // [1, 1]
}
}
[1, 1]
What About Land Removal?
Standard Union-Find has no split operation, so it cannot handle land removal directly. The workaround is offline processing: process the timeline in reverse, treating each removal as an addition. This works when all operations are known upfront.
package com.bank.core;
public class LandRemovalWorkaround {
// Union-Find supports union but not split
// To handle removal:
// 1. Process operations in reverse
// 2. Treat removals as additions
// 3. Reverse the result array
// Requires knowing all operations upfront (offline)
// For true online removal: use link-cut trees (advanced)
}
What About Multiple Merges in One Addition?
A single land addition can merge up to 4 separate islands if all four neighbors are land from different islands. Each successful union decrements the count by one, so adding one cell could decrease the island count by up to 3 (add 1, merge 4 neighbors = net -3).
package com.bank.core;
public class MultiMergeExample {
public static void main(String[] args) {
NumberOfIslandsII solver = new NumberOfIslandsII();
// Create 4 separate islands around (1,1)
// Then add (1,1) to merge all 4
int[][] positions = {{0,1},{1,0},{1,2},{2,1},{1,1}};
System.out.println(solver.numIslands2(3, 3, positions));
// [1, 2, 3, 4, 1] -> adding (1,1) merges all 4 into 1
}
}
[1, 2, 3, 4, 1]
What About Time and Space Complexity?
Time is O((m*n + k) * alpha(m*n)) where k is the number of operations and alpha is effectively constant. Space is O(m*n) for the parent and size arrays.
package com.bank.core;
public class IslandsIIComplexity {
// Time: O((m*n + k) * alpha(m*n)) ~ O(m*n + k)
// Space: O(m*n) for parent[], size[], isLand[]
// alpha(m*n) <= 5 for all practical input sizes
// k = number of addLand operations
}
What Are Common Interview Follow-Up Questions?
Interviewers commonly ask:
- Static Number of Islands: BFS/DFS on the full grid.
- Handle land removal: offline reverse processing or link-cut trees.
- Count the size of each island: Union-Find already tracks size in the size array.
- Largest island after each addition: track the maximum size alongside the count.
package com.bank.core;
public class IslandsIIFollowUps {
// Static: BFS/DFS flood fill
// Size tracking: already in size[] array
// Largest island: track maxSize alongside count
// Removal: offline reverse or link-cut trees
}
Visual Overview
Number of Islands II - Step by Step: 3x3 grid, positions: (0,0), (0,1), (1,2), (2,1), (1,1) Step 1: Add (0,0) Step 2: Add (0,1) ┌───┬───┬───┐ ┌───┬───┬───┐ │ L │ │ │ count=1 │ L │ L │ │ count=1 (merged) │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ │ └───┴───┴───┘ └───┴───┴───┘ Step 3: Add (1,2) Step 4: Add (2,1) ┌───┬───┬───┐ ┌───┬───┬───┐ │ L │ L │ │ count=2 │ L │ L │ │ count=3 │ │ │ L │ │ │ │ L │ │ │ │ │ │ │ L │ │ └───┴───┴───┘ └───┴───┴───┘ Step 5: Add (1,1) Merges all 3 islands! ┌───┬───┬───┐ │ L │ L │ │ count=1 │ │ L │ L │ │ │ L │ │ └───┴───┴───┘
Key Takeaway
Number of Islands II is the dynamic version where land is added one cell at a time and I must report the island count after each addition. I maintain a Union-Find keyed by the flattened cell index together with a running island counter. Each time a new land cell is added, I first increment the counter because that cell is initially its own island, then I try to union it with each of its four neighbors that is already land, decrementing the counter on every union that genuinely merges two separate islands.
Using path compression with union by size keeps the trees shallow, so the whole sequence runs in time proportional to the grid plus the number of operations, each at effectively constant cost. The key operation detail is handling duplicate additions as no-ops.
At National Bank of India, a service rollout activated map cells one at a time and operations needed the current number of contiguous service regions after each activation for staffing decisions. Union-Find gave near-constant-time updates that BFS/DFS could not match.
The interviewer's favorite follow-up is land removal, and the honest answer is that plain Union-Find has no split operation. Removal is handled offline by processing the timeline in reverse and treating each removal as an addition, or by using advanced link-cut structures.
Remember one sentence: add one island per new cell, merge with live neighbors via Union-Find, decrement on each real merge, and report the count.
---