Track Island Counts as Land Is Added

Track Island Counts as Land Is Added

Problem

Implement trackIslandCounts(grid, additions) -> counts.

grid is a rectangular array containing 0 for water and 1 for land. Two land cells belong to the same island when they are connected through up, down, left, or right neighbors.

First count the islands in the initial grid and append that count to counts. Then process each addition [row, col] in order. An addition changes that cell to land if it is water; adding an existing land cell has no effect. Append the current island count after every addition.

Return an array of length additions.length + 1. Do not mutate grid or additions.

Constraints

• 1 <= grid.length, 1 <= grid[0].length.
• Every row has the same length, and the grid contains at most 200,000 cells.
• 0 <= additions.length <= 200,000.
• Every addition is a two-element integer array naming a valid grid cell.
• Target O(R*C + A*alpha(R*C)) time and O(R*C) auxiliary space, where A is the number of additions.

Examples

grid = [
 [1, 0, 0],
 [0, 0, 1]
]
additions = [[0, 1], [1, 1], [1, 1]]
counts = [2, 2, 1, 1]

grid = [[0, 0]]
additions = [[0, 0], [0, 1]]
counts = [0, 1, 1]

Discussion Requirements

• Explain a BFS or DFS computation for the initial island count.
• Explain why recomputing the whole grid after every addition is unnecessarily expensive.
• Describe how disjoint-set union merges newly adjacent land components and handles duplicate additions.