This is the dynamic version of the classic "Number of Islands" problem. In the original problem (LeetCode #200), you get a fixed grid and count connected components of land cells. Here, the grid starts empty and land cells are added one at a time. After each addition, we report the current island count.

The challenge is doing this efficiently. Each time we add a land cell, only its four neighbors can change connectivity, so rerunning a full BFS or DFS over the whole grid after every addition wastes work. When the new cell touches an existing island, it joins that island. When it touches two or more separate islands at once, those islands merge into one and the total count drops. We need a structure that handles these incremental merges without rescanning everything.

Union Find (Disjoint Set Union) matches this shape directly. It groups elements dynamically and answers whether two elements are in the same group, which is what tracking islands as land arrives requires.

Key Constraints:

Intuition

Treat each operation as a fresh "Number of Islands" problem. Maintain a grid, and after each addLand, run a full BFS over the entire grid to count connected components from scratch.

For each addLand, mark the cell as land, then iterate over the grid. Every time you find an unvisited land cell, start a BFS to mark all connected land cells as visited, and increment the island count.

Algorithm

Visualization and Code

With k up to 10^4 and the grid up to 10^8 cells, O(k m n) is far too slow, and allocating the full grid is not even possible at the upper bound. The next approach keeps the connectivity information between operations instead of rebuilding it, updating only what the new cell affects.

Intuition

Maintain a running island count and update it as each cell arrives. When we add a new land cell, it starts as its own island, so the count goes up by 1. Then we check the four neighbors. For each neighbor that is already land and sits in a different island, we union the two and decrement the count by 1. After processing all four neighbors, the count is the answer for this operation.

Union Find supports two operations: find(x) returns the representative of x's group, and union(x, y) merges two groups. With path compression in find and union by rank, both run in nearly O(1) amortized time, measured as O(alpha(mn)) where alpha is the inverse Ackermann function.

The grid can hold up to 10^8 cells but at most 10^4 become land, so we store the parent and rank in a HashMap keyed only by land cells instead of allocating a full array. Each 2D coordinate maps to a single integer key with row * n + col, which is unique because every column index is less than n.

Algorithm

Visualization and Code