Description
Given a 2D grid initialized with water, perform addLand operations and return the number of islands after each operation. Use Union-Find for efficiency.
Examples
Input:
m=3, n=3, positions=[[0,0],[0,1],[1,2],[2,1]]Output:
[1,1,2,3]Explanation:
Islands form and merge as land is added.
Input:
m=3, n=3, positions=[[1]]Output:
[1]Explanation:
Minimal case with a single-element matrix.
Input:
m=4, n=5, positions=[[1,1],[1,2],[2,1],[3,3],[3,4],[2,3],[2,2]]Output:
[1,2,2,3,4,4,3]Explanation:
Start with [1,1] creating island 1. Add [1,2] creating island 2. Add [2,1] still 2 islands. Add [3,3] creating island 3. Add [3,4] creating island 4. Add [2,3] still 4 islands. Finally add [2,2] which connects the upper-left cluster with the bottom-right cluster through the middle, merging them into 3 total islands.
Constraints
- •
1 ≤ m, n ≤ 10⁴ - •
1 ≤ positions.length ≤ 10⁴