Count Islands After Each Land Addition to an All-Water Grid

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

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

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

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.