Hard · Incremental Grid DSU
Understand → Visualise → Practice.
Land cells are added to an all-water grid. Return the island count after each addition.
Each new land cell is a new island. Union it with every land neighbour; each union that joins two different sets reduces the island count by one.
If it is already land, the count doesn't change; otherwise make it its own set and add 1.
For each of the four neighbours that is land, union them; subtract 1 for each successful merge.
Append the current island count after every addition.
O(k α(rows × cols)) time for k additions and O(rows × cols) space.
Re-running a full flood fill after every addition is O(k × rows × cols).
Read the full guide first: Union-Find for Dynamic Connectivity.
Guest mode lets you understand, visualise and run the sample tests. Create a free account to submit and save your solutions.