You start with an m x n grid of water. You're given positions, where positions[i] = [r, c] turns the cell (r, c) into land. After each operation, report the number of islands (4-directionally connected land). Return an array with the island count after each operation. (Turning an already-land or out-of-range cell to land leaves the count unchanged.)
Input: m = 3, n = 3, positions = [[0,0],[0,1],[1,2],[2,1]] Output: [1, 1, 2, 3] The second add merges with the first; the rest are new islands.
Input: m = 1, n = 1, positions = [[0,0]] Output: [1] A single land cell is one island.
- 1 <= m, n <= 10^4 - 0 <= positions.length <= 10^4 - positions[i] is [r, c]
Land is only ever added, never removed — a perfect fit for union-find, which maintains a component count incrementally. When you add a land cell, it starts as its own island (count += 1); then check its four neighbours, and for each that's already land, union them — every successful merge means two islands became one (count -= 1). Record the count after each step. Each operation is near-O(α), so the whole thing is near-O(positions).
The brute alternative re-floods the entire grid after every add to recount islands — correct, but O(positions · m·n), hopelessly slow for a long stream.
“Report after each add?”
Yes — one count per operation.
“Repeated or invalid positions?”
The count stays the same for that step.
Each new land cell is a new island; then I union it with any adjacent land, subtracting one per merge.
Union-find keeps the running island count in near-O(1), unlike re-flooding the grid each time.
Worked example — m=3, n=3, positions [[0,0],[0,1],[1,2],[2,1]]
[0,0] -> 1 island [0,1] -> merges with (0,0) -> 1 [1,2] -> new island -> 2 [2,1] -> new island -> 3 result = [1, 1, 2, 3]
Before merging, a fresh cell is its own island.
Uniting with an adjacent land cell fuses two islands.
Growing connectivity maintained incrementally.
| Re-flood each add | Incremental union-find | |
|---|---|---|
| Idea | recount islands after every operation | update count as land is added |
| Time | O(P·m·n) | O(P·α) |
| Reuse | recomputes from scratch | maintains running count |
Both produce the same count sequence; union-find is dramatically faster. Full code is in the Approaches selector below.
Key takeaway
Land only grows, so use union-find: each new cell adds an island, and every union with an adjacent land cell subtracts one. Record the count after each add. Near-O(positions).
add (r,c): count++; for each land neighbour: if union merges: count-- append count
