Islands Rising One Cell at a Time
Implement islandCounts
A map starts as all water. Cells are then turned into land one at a time. After each change, report the number of islands (groups of land cells connected through shared sides).
Recounting with a flood fill after every change works but repeats a lot of work. Union-find keeps the islands as groups and updates the count locally: a new cell adds an island and every merge with a neighbouring island removes one.
Example 1:
Input: rows = 4, cols = 4, positions = [[0,0],[0,1],[2,2],[1,2],[1,1],[3,3],[1,2]]
Output: [1,1,2,2,1,2,2]
Example 2:
Input: rows = 2, cols = 2, positions = [[0,0],[1,1],[0,1]]
Output: [1,2,1]
Example 3:
Input: rows = 1, cols = 1, positions = [[0,0],[0,0]]
Output: [1,1]
+ 13 hidden test cases run on Submit.
Constraints:
- ●
1 ≤ rows, cols ≤ 8; the map starts as all water - ●
positions lists at most 12 cells [row, column]; the cells are turned into land one after another, in the given order (a cell may appear again; nothing changes then) - ●
An island is a group of land cells connected through shared sides (up, down, left, right) - ●
Return an array whose entry k is the number of islands right after the k-th cell has been turned into land
rows =
cols =
positions =