Dynamic Island Counts
Uber● HardFULLTIMEPHONE SCREENProblem statement
An initially all-water grid has rows rows and cols columns. Process the positions in order. For each [row, col], turn that cell into land if it is still water, then record the current number of horizontally or vertically connected islands.
If a position is repeated, the grid does not change and the previous island count is recorded again. Return one count per position.
Function
dynamicIslandCounts(rows: int, cols: int, positions: int[][]) → int[]Examples
Example 1
rows = 3cols = 3positions = [[0,0],[0,1],[1,2],[2,1]]return = [1,1,2,3]The second addition joins the first island; the final two additions are isolated from existing land.
Example 2
rows = 3cols = 3positions = [[0,0],[0,1],[1,2],[1,1]]return = [1,1,2,1]The last cell bridges the two existing islands into one.
Example 3
rows = 1cols = 2positions = [[0,0],[0,0],[0,1]]return = [1,1,1]The repeated position is a no-op, and the final cell joins the existing island.
Constraints
1 <= rows, cols <= 10000.1 <= positions.length <= 100000.- Every position contains exactly two integers within the grid.
rows * cols <= 10^7.