Count Islands After Each Land Addition to an All-Water Grid
Company: Uber
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Start with an `m x n` grid in which every cell is water. You receive a sequence of operations: operation `i` turns the cell `positions[i] = [r, c]` into land. After each operation, report the number of islands, where an island is a maximal group of land cells connected horizontally or vertically.
Return a list whose `i`-th value is the number of islands after the first `i + 1` operations have been applied.
### Function Signature
```python
def islands_after_each_addition(m: int, n: int, positions: list[list[int]]) -> list[int]:
```
### Rules
- Two land cells belong to the same island exactly when one can be reached from the other by moving up, down, left or right through land cells. Diagonal contact does not connect cells.
- Every position outside the grid is water.
- If an operation targets a cell that is already land, the grid does not change, and the value reported for that operation equals the previous value.
- The result has exactly `len(positions)` values.
### Constraints
- `1 <= m, n <= 10^4` and `m * n <= 10^5`
- `1 <= len(positions) <= 10^5`
- `0 <= positions[i][0] < m` and `0 <= positions[i][1] < n`
- The same cell may appear more than once in `positions`.
- Every reported count is at most `m * n`.
### Examples
**Example 1**
```text
Input: m = 3, n = 4,
positions = [[0, 0], [2, 3], [0, 2], [0, 1], [1, 3], [0, 0], [1, 2]]
Output: [1, 2, 3, 2, 2, 2, 1]
```
- `[0, 1]` touches `(0, 0)` and `(0, 2)`, joining two islands, so the count drops from 3 to 2.
- `[1, 3]` touches `(2, 3)` and joins its island, so the count stays 2.
- `[0, 0]` is already land, so the count stays 2.
- `[1, 2]` touches `(0, 2)` above it and `(1, 3)` to its right, joining the last two islands into one.
**Example 2**
```text
Input: m = 2, n = 2, positions = [[0, 0], [1, 1], [0, 1]]
Output: [1, 2, 1]
```
`(0, 0)` and `(1, 1)` touch only diagonally, so they are separate islands until `(0, 1)` connects them.
Overview: A grid coding problem where land cells are added one at a time to an initially all-water grid and you must report the number of islands after every addition. It tests incremental connectivity, efficient merging of islands as they join, and correct handling of repeated additions.
Start with an `m x n` grid in which every cell is water. You receive a sequence of operations `positions`: operation `i` turns the cell `positions[i] = [r, c]` (row `r`, column `c`) into land. After each operation, report the number of islands, where an island is a maximal group of land cells connected horizontally or vertically.
Implement `islands_after_each_addition(m, n, positions)`, which returns a list whose `i`-th value is the number of islands after the first `i + 1` operations have been applied.
### Rules
- Two land cells belong to the same island exactly when one can be reached from the other by moving up, down, left or right through land cells. Diagonal contact does not connect cells.
- Every position outside the grid is water.
- If an operation targets a cell that is already land, the grid does not change, and the value reported for that operation equals the previous value.
- The result has exactly `len(positions)` values.
### Constraints
- `1 <= m, n <= 10^4` and `m * n <= 10^5`
- `1 <= len(positions) <= 10^5`
- `0 <= positions[i][0] < m` and `0 <= positions[i][1] < n`
- The same cell may appear more than once in `positions`.
- Every reported count is at most `m * n`.
No input value or reported count can exceed 2^31 - 1, so 32-bit integers (`int` in Java and C++) are sufficient.
### Examples
**Example 1**
```text
Input: m = 3, n = 4,
positions = [[0, 0], [2, 3], [0, 2], [0, 1], [1, 3], [0, 0], [1, 2]]
Output: [1, 2, 3, 2, 2, 2, 1]
```
- `[0, 1]` touches `(0, 0)` and `(0, 2)`, joining two islands, so the count drops from 3 to 2.
- `[1, 3]` touches `(2, 3)` and joins its island, so the count stays 2.
- `[0, 0]` is already land, so the count stays 2.
- `[1, 2]` touches `(0, 2)` above it and `(1, 3)` to its right, joining the last two islands into one.
**Example 2**
```text
Input: m = 2, n = 2, positions = [[0, 0], [1, 1], [0, 1]]
Output: [1, 2, 1]
```
`(0, 0)` and `(1, 1)` touch only diagonally, so they are separate islands until `(0, 1)` connects them.
Constraints
- 1 <= m, n <= 10^4 and m * n <= 10^5
- 1 <= len(positions) <= 10^5
- 0 <= positions[i][0] < m and 0 <= positions[i][1] < n
- The same cell may appear more than once in positions.
- Every reported count is at most m * n.
Examples
Input: (3, 4, [[0, 0], [2, 3], [0, 2], [0, 1], [1, 3], [0, 0], [1, 2]])
Expected Output: [1, 2, 3, 2, 2, 2, 1]
Explanation: Source Example 1: merges, a join into an existing island, and a repeated cell.
Input: (2, 2, [[0, 0], [1, 1], [0, 1]])
Expected Output: [1, 2, 1]
Explanation: Source Example 2: diagonal cells stay separate until an orthogonal bridge joins them.
Hints
- Recounting every island from scratch after each operation can cost O(m * n) per operation; consider what a single new land cell can actually change.
- A newly added land cell can only affect the islands that contain its up to four orthogonal neighbours, and several of those neighbours may already belong to the same island.
- An operation on a cell that is already land leaves the grid unchanged, so its reported value is simply the previous one.