Number of Islands II

Problem

You are given the dimensions m and n of a grid that starts entirely as water. Then a sequence of operations arrives: positions[i] = [r, c] turns the cell at row r, column c into land. After each operation, report how many islands the grid contains, where an island is a maximal group of land cells connected horizontally or vertically.

Return a list answer where answer[i] is the island count after applying the first i + 1 operations. Turning a cell that is already land into land again is a no-op and should not change the count.

• Grid dimensions and the operation count are each bounded by roughly ten thousand; the grid area can be far larger than the number of operations.
• Up to about ten thousand operations.
• Every row and column index in positions is within bounds for the given m, n.

Examples

• m = 3, n = 3, positions = [[0,1],[2,1],[1,0],[1,2]] → [1,2,3,4]. Each new cell is isolated from the others, one per corner-ish side of the center.
• m = 3, n = 3, positions = [[0,1],[2,1],[1,0],[1,2],[1,1]] → [1,2,3,4,1]. The final cell at the center touches all four islands and merges them into one.
• m = 2, n = 2, positions = [[0,0],[0,0]] → [1,1]. Repeating a position does not create a second island.

Hints

1. After each new land cell, what is the most the island count can change by, and in which direction?
2. A new land cell starts as its own island. What happens to the count each time it turns out to touch a neighbor that belongs to a different island?
3. Union-find keyed by cell index (or by coordinates in a dictionary): count += 1 for the new cell, count -= 1 for every successful union with a neighboring land cell.