Count Islands in a Grid and Track the Count as Land Cells Are Added
Company: Google
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
A map is a grid with `m` rows and `n` columns in which every cell is land (`1`) or water (`0`). An island is a maximal group of land cells connected horizontally or vertically. Cells that touch only at a corner are not connected.
You are given the initial map and a sequence of additions, each of which turns one cell into land. Report the number of islands before any addition, and again after each addition.
### Function Signature
```python
def island_counts(grid: list[list[int]], additions: list[tuple[int, int]]) -> list[int]:
```
### Rules
- `grid[r][c]` is `1` for land and `0` for water, where `r` is the row index and `c` is the column index.
- An addition `(r, c)` turns cell `(r, c)` into land. If that cell is already land, either initially or because of an earlier addition, the map does not change.
- Additions are applied in the given order. Land never turns back into water.
- Return a list of length `len(additions) + 1`. Element `0` is the number of islands in the initial grid. For `i >= 1`, element `i` is the number of islands after the first `i` additions have been applied.
### Constraints
- `1 <= m <= 1000`, `1 <= n <= 1000` and `m * n <= 200000`
- Every row of `grid` has exactly `n` entries, each `0` or `1`.
- `0 <= len(additions) <= 200000`
- Every addition `(r, c)` satisfies `0 <= r < m` and `0 <= c < n`. The same cell may appear more than once.
- Every count is at most `m * n`, so all values fit in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: grid = [[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]], additions = []
Output: [3]
```
The islands are {(0, 0), (0, 1)}, {(1, 3), (2, 3)} and {(2, 0)}. With no additions, the only element is the initial count.
**Example 2**
```text
Input: grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]], additions = [(0, 0), (0, 1), (1, 2), (2, 1), (1, 1), (1, 1)]
Output: [0, 1, 1, 2, 3, 1, 1]
```
The grid starts with no land. (0, 0) creates an island and (0, 1) joins it. (1, 2) and (2, 1) each touch no land, so each creates a new island. (1, 1) touches all three islands and merges them into one. The second (1, 1) is already land, so nothing changes.
**Example 3**
```text
Input: grid = [[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]], additions = [(0, 2), (0, 3), (1, 0)]
Output: [3, 3, 2, 1]
```
(0, 2) joins the top-left island. It touches (1, 3) only at a corner, so the count stays 3. (0, 3) connects the top-left island to the island at (1, 3) and (2, 3), giving 2. (1, 0) connects the merged island to (2, 0), giving 1.
Overview: Count the islands of horizontally or vertically connected land cells in a grid, then report the updated count after each cell in a sequence is turned into land. Tests grid connectivity, handling a new cell that merges several islands at once, and processing up to 200,000 additions efficiently.
A map is a grid with m rows and n columns in which every cell is land (1) or water (0). An island is a maximal group of land cells connected horizontally or vertically. Cells that touch only at a corner are not connected.
You are given the initial map grid and a sequence of additions, each of which turns one cell into land. Each addition is given as a pair [r, c]. Report the number of islands before any addition, and again after each addition.
Rules:
- grid[r][c] is 1 for land and 0 for water, where r is the row index and c is the column index.
- An addition [r, c] turns cell (r, c) into land. If that cell is already land, either initially or because of an earlier addition, the map does not change.
- Additions are applied in the given order. Land never turns back into water.
- Return a list of length len(additions) + 1. Element 0 is the number of islands in the initial grid. For i >= 1, element i is the number of islands after the first i additions have been applied.
Constraints:
- 1 <= m <= 1000, 1 <= n <= 1000 and m * n <= 200000
- Every row of grid has exactly n entries, each 0 or 1.
- 0 <= len(additions) <= 200000
- Every addition [r, c] satisfies 0 <= r < m and 0 <= c < n. The same cell may appear more than once.
- Every count is at most m * n, so all values fit in a 32-bit signed integer (no value can exceed 2^31 - 1).
Example 1:
Input: grid = [[0, 0, 0], [0, 0, 0], [0, 0, 0]], additions = [[0, 0], [0, 1], [1, 2], [2, 1], [1, 1], [1, 1]]
Output: [0, 1, 1, 2, 3, 1, 1]
The grid starts with no land. [0, 0] creates an island and [0, 1] joins it. [1, 2] and [2, 1] each touch no land, so each creates a new island. [1, 1] touches all three islands and merges them into one. The second [1, 1] is already land, so nothing changes.
Example 2:
Input: grid = [[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]], additions = [[0, 2], [0, 3], [1, 0]]
Output: [3, 3, 2, 1]
The initial islands are {(0, 0), (0, 1)}, {(1, 3), (2, 3)} and {(2, 0)}. [0, 2] joins the top-left island; it touches (1, 3) only at a corner, so the count stays 3. [0, 3] connects the top-left island to the island at (1, 3) and (2, 3), giving 2. [1, 0] connects the merged island to (2, 0), giving 1.
Constraints
- 1 <= m <= 1000, 1 <= n <= 1000 and m * n <= 200000
- Every row of grid has exactly n entries, each 0 or 1.
- 0 <= len(additions) <= 200000
- Every addition [r, c] satisfies 0 <= r < m and 0 <= c < n. The same cell may appear more than once.
- Every count is at most m * n, so all values fit in a 32-bit signed integer (no value can exceed 2^31 - 1).
Examples
Input: ([[1, 1, 0, 0], [0, 0, 0, 1], [1, 0, 0, 1]], [])
Expected Output: [3]
Explanation: Source example 1: islands {(0,0),(0,1)}, {(1,3),(2,3)}, {(2,0)} and no additions, so only the initial count is returned.
Input: ([[0, 0, 0], [0, 0, 0], [0, 0, 0]], [[0, 0], [0, 1], [1, 2], [2, 1], [1, 1], [1, 1]])
Expected Output: [0, 1, 1, 2, 3, 1, 1]
Explanation: Source example 2: islands are created, (1,1) merges three islands into one, and its repeat changes nothing.
Hints
- Land never turns back into water, so adding one cell can only change the island count in a limited way; consider what the new cell can connect to.
- If the new cell touches the same island from more than one side, that island must only be counted as merged once, so you need a fast way to tell whether two land cells already belong to the same island.
- Recounting all islands from scratch after every addition is too slow with up to 200000 cells and 200000 additions.