hardGraphsPure DSA~45 min
Incremental Cluster Count
Nodes come online one at a time on a grid. Two online nodes in adjacent cells form one cluster. After each node powers on, report how many separate clusters currently exist.
Problem
Given an m×n grid initially all water, process a list of positions that turn into land one by one. After each addition, report the number of islands (4-directionally connected land groups). Return the list of counts.
Input
Integers m, n and a list positions of [row, col] cells turned to land in order.
Output
An array where the i-th value is the island count after the i-th addition.
Constraints
- 1 ≤ m, n ≤ 10^4 (grid is sparse)
- 0 ≤ positions.length ≤ 10^4
- Repeated positions leave the count unchanged
Examples
Example 1
Input
m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]]
Output
[1,1,2,3]
Adjacent (0,0)&(0,1) merge; the later cells stay separate.
Example 2
Input
m = 1, n = 1, positions = [[0,0],[0,0]]
Output
[1,1]
The duplicate addition doesn't change the count.