Track Island Counts as Land Is Added
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.
Quick Answer: 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.