Number of Islands II LeetCode 305 — Union Find

LeetCode 305 Number of Islands II starts with an m x n grid of all water. You are given a list of positions — each position represents a cell to turn from water to land. After each addition, you must return the total number of distinct islands currently in the grid. An island is a group of horizontally or vertically connected land cells surrounded by water.

This is fundamentally different from the classic Number of Islands (LeetCode 200), where the grid is static and you run one BFS or DFS pass. Here the grid changes with each operation, and you need a running count after every single addition. That dynamic nature is what makes this problem interesting and demands a smarter approach.

The result is an array of integers, one per position in the input list, where each integer is the island count after that land cell is added. Positions can be added out of order, and the same position may appear more than once — duplicate additions must be handled gracefully.

The naive approach is to re-run BFS or DFS from scratch after each land addition to count all islands. Each BFS traversal visits every cell in the grid — O(m * n) per call. With k additions, the total time is O(k * m * n). When k approaches 10^4 and the grid approaches 10^4 cells, this yields up to 10^8 operations per test case, which reliably times out.

Even a smarter incremental BFS — only re-exploring neighbors of the newly added cell — still degrades to O(m * n) per step in the worst case when large islands merge. The fundamental issue is that BFS and DFS cannot efficiently answer "are these two cells in the same island?" without re-exploring. That question is exactly what Union-Find is built for.

The structure we need supports two operations efficiently: union two cells into the same island, and find whether two cells share an island. Union-Find (also called Disjoint Set Union or DSU) does both in near-constant amortized time, turning the overall algorithm from O(k * m * n) into O(k * alpha(m * n)) — practically linear.

The Union-Find structure tracks which cells belong to the same connected component (island). Each cell (i, j) is mapped to a flat index using i * n + j, turning the 2D grid into a 1D array of size m * n. Two arrays power the structure: parent[] and rank[]. Initially all cells are water, so parent[cell] = -1 to signal "not yet land".

The find operation returns the root representative of a cell's component. With path compression, every node on the path to the root is pointed directly at the root on the way back up. This flattens the tree so future find calls on any node in that path cost O(1). The union operation merges two components by attaching the root of the smaller-ranked tree under the root of the larger-ranked tree — union by rank.

When two land cells become adjacent (share an edge), union is called on them. If they are already in the same component, the island count does not change. If they are in different components, the two islands merge into one and the count decreases by one. This is the core logic that runs for each of the four neighbors after every land addition.

When position (r, c) is added, first check if it is already land (parent[r*n+c] != -1). If so, skip it and append the current island count unchanged — handling duplicates in O(1). Otherwise, mark it as land by setting parent[r*n+c] = r*n+c (the cell is its own root), set rank to 0, and increment the island count by one — a brand new island just appeared.

Next, check all four neighbors: up, down, left, right. For each neighbor that is within bounds and is land (parent != -1), call union(cell, neighbor). The union operation checks whether both cells share a root. If not, it merges the two components — attaching one root under the other based on rank — and decrements the island count by one, because two separate islands just became one.

After processing all four neighbors, append the current island count to the result array. That's the entire per-step logic: one potential new-island increment, up to four potential merges. Each union and find call runs in near O(1) amortized time, so the total per-step cost is O(alpha(m*n)), effectively constant.

The problem allows the same grid cell to appear multiple times in the positions list. A naive implementation that sets parent[cell] = cell unconditionally on every visit would incorrectly reset a cell that is already part of a large island, corrupting the Union-Find structure and producing wrong island counts.

The fix is a single guard at the start of each step: if parent[cell] != -1, the cell is already land. Skip all processing — do not reset parent, do not increment the count, do not union with neighbors — and simply record the current island count as-is. This check is O(1) and correctly handles any number of duplicate entries.

In interviews, duplicates are a common edge case that catches candidates off guard. Examiners may specifically ask how you handle them, so it is worth calling out explicitly when explaining your approach. The parent[] array doubles as a visited/land marker, which makes the duplicate check free with no extra memory.

In Python, implement a UnionFind class with an __init__ that allocates parent and rank arrays of size m*n initialized to -1 and 0 respectively, plus an islands counter. The find method uses recursive path compression: return x if parent[x] == x else the result of setting parent[x] = find(parent[x]). The union method finds both roots and, if different, attaches the lower-rank root under the higher-rank root, increments rank if equal, and decrements self.islands. The main numIslands2 function creates a UnionFind, iterates positions, skips if already land, marks land, unions with valid land neighbors, and collects self.islands after each step.

In Java, use two int arrays parent[] and rank[] of size m*n. Initialize all to -1. The find method uses iterative path compression with a while loop. The union method is identical in logic. The main method collects results in a List<Integer>. Total time complexity is O(k * alpha(m*n)) where k is the number of positions — effectively O(k). Space complexity is O(m*n) for the parent and rank arrays.

Both implementations share the same structure: UnionFind encapsulates state, the main loop drives the process, and results are accumulated per step. The key insight is that Union-Find is not just an optimization — it is the right abstraction for dynamic connectivity, and this problem is a textbook application of the pattern.

Number of Islands (LeetCode 200) is the static predecessor — solve it with BFS or DFS first to understand the island connectivity concept, then see how Union-Find handles the dynamic version in LeetCode 305. The two together form a complete picture of island-counting techniques.

Accounts Merge (LeetCode 721) and Redundant Connection (LeetCode 684) are canonical Union-Find problems. Accounts Merge groups email accounts by shared email addresses using Union-Find on string keys. Redundant Connection finds the extra edge in a graph that creates a cycle — union returns false when both nodes already share a root.

The connected components family — Number of Provinces (LeetCode 547), Graph Valid Tree (LeetCode 261), and Making a Large Island (LeetCode 827) — all reward Union-Find fluency. Mastering path compression and union by rank once unlocks all of them. LeetCode 305 is often the bridge problem that converts candidates from BFS thinkers into Union-Find practitioners.