Track Island Counts as Land Is Added

Quick Overview

Report the initial number of grid islands and update that count after each requested water-to-land addition. The problem probes incremental connectivity, duplicate additions, local merge effects, scalability to large grids, and alternatives to recomputing the entire map.

Company: Google

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: medium

Interview Round: Onsite

## 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. ```hint Count effects locally When one water cell becomes land, enumerate the distinct neighboring islands it touches and compare that set with the count change. ``` ### Examples ```text grid = [ [1, 0, 0], [0, 0, 1] ] additions = [[0, 1], [1, 1], [1, 1]] counts = [2, 2, 1, 1] ``` ```text 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.

Overview: Report the initial number of grid islands and update that count after each requested water-to-land addition. The problem probes incremental connectivity, duplicate additions, local merge effects, scalability to large grids, and alternatives to recomputing the entire map.

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. Diagonal contact does not connect two land cells. 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`. The output is fully determined: entry `0` is the initial island count and entry `i + 1` is the island count after applying `additions[i]`, so the result order is exactly the order of the additions. ### Examples Example 1: ```text grid = [ [1, 0, 0], [0, 0, 1] ] additions = [[0, 1], [1, 1], [1, 1]] counts = [2, 2, 1, 1] ``` The initial grid holds two separate land cells, so the first count is `2`. Adding `[0, 1]` joins the land at `[0, 0]` into one larger island, leaving `2`. Adding `[1, 1]` touches both islands at once and merges them, giving `1`. The repeated `[1, 1]` is already land, so the count stays `1`. Example 2: ```text grid = [[0, 0]] additions = [[0, 0], [0, 1]] counts = [0, 1, 1] ``` The all-water grid starts with `0` islands. Adding `[0, 0]` creates one island. Adding `[0, 1]` is adjacent to it, so the two cells form a single island and the count stays `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.

Constraints

1 <= grid.length, 1 <= grid[0].length
Every row of grid has the same length, and grid contains at most 200000 cells
grid[r][c] is either 0 (water) or 1 (land)
0 <= additions.length <= 200000
additions[i] is a two-element array [row, col] naming a valid cell: 0 <= row < grid.length and 0 <= col < grid[0].length
The same cell may appear in additions more than once; every occurrence after the first is a no-op
The returned array has exactly additions.length + 1 entries, and grid and additions must not be mutated
Target O(R*C + A*alpha(R*C)) time and O(R*C) auxiliary space, where R and C are the grid dimensions and A is the number of additions

Examples

Input: ([[1, 0, 0], [0, 0, 1]], [[0, 1], [1, 1], [1, 1]])

Expected Output: [2, 2, 1, 1]

Input: ([[0, 0]], [[0, 0], [0, 1]])

Expected Output: [0, 1, 1]

Hints

Counting the whole grid again after every addition repeats work that did not change. Only the cells around the new land can affect the answer.
Count effects locally: when one water cell becomes land, enumerate the distinct neighboring islands it touches and compare that set with the count change.
Two of the four neighbors may already belong to the same island. Merge by component, not by neighbor cell, and let the disjoint-set union tell you whether a merge actually happened.

Approach

The reference keeps a disjoint-set union (DSU) over the R*C cell indices plus a boolean land array, and maintains a running island count instead of recomputing it.

Initialization: mark every land cell of the input grid, adding 1 to the count for each. Then sweep the grid once and, for each land cell, union it with its right and down land neighbors. Each union that actually joins two different roots reduces the number of components by exactly one, so subtracting 1 per successful union turns the cell count into the island count. Scanning only right and down visits every adjacent pair once. That initial count is the first element of the result.

Each addition: if the cell is already land the state is unchanged and the current count is appended again, which is what makes duplicate additions a no-op. Otherwise the cell becomes land and the count goes up by 1 (a brand-new island of one cell), then the four orthogonal neighbors are examined. For each neighbor that is land, a union is attempted, and the count is decremented only when the union actually merged two distinct roots. This is the crux: a new cell can have two, three, or four land neighbors that already belong to the same island, and those cost nothing. Letting the DSU report whether a merge happened counts distinct components rather than adjacent cells.

Neither argument is written to: the grid is read once into the private land array and the addition pairs are only read.

With path compression and union by rank each operation is effectively constant (inverse Ackermann), so the initial sweep costs O(RC) and each addition O(alpha(RC)). The naive alternative of re-running a BFS flood fill after every addition is O(ARC), which at the stated bounds is far too slow.

Time complexity:

O(R*C + A*alpha(R*C))

Space complexity:

O(R*C)