DSA problem
Number of Islands II
You are given an empty 2D binary grid of size m x n. The grid represents a map where 0s represent water and 1s represent land. Initially, all the cells of the grid are water cells (i.e., all the cells are 0s). We may perform an add land operation which turns the water at position positions[i] = [r_i, c_i] into land. Return an array of integers answer where answer[i] is the number of islands after turning the cell (r_i, c_i) into land.
An island is a maximal group of 1s connected horizontally or vertically (4-directional). The challenge is that operations happen online — after every single addition we must report the current island count, and additions can both create new islands and merge several existing ones into one.
Recomputing the island count from scratch after every operation with BFS/DFS would cost O(K * m * n). The Union-Find approach gives us each operation in amortised O(α(m * n)). We treat each cell index r * n + c as a DSU node. Maintain a running counter of the number of islands.
When we add land at (r, c) that was previously water, increment the counter by 1 (a brand-new singleton island). Then, for each of the 4 neighbours that is land, attempt to union it with (r, c); every successful union decrements the counter by 1 (two islands have become one). If the same position is added twice (a duplicate operation), we leave the counter unchanged. The output array logs the counter after each operation.
Examples
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]][1,1,2,3]m = 1, n = 1, positions = [[0,0]][1]m = 3, n = 3, positions = [[0,0],[0,0]][1,1]Constraints
- 1 <= m, n, positions.length <= 10^4
- 1 <= m * n <= 10^4
- positions[i].length == 2
- 0 <= r_i < m
- 0 <= c_i < n
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.