Count Islands After Land Additions

Problem Statement

You are given an n x n grid initially filled with water (0). You are provided with a sequence of k operations, where each operation is represented as a list of coordinates [row, col]. For each operation, you transform the cell at (row, col) from water to land (1). After each addition, return the current number of connected components of land (islands) in the grid.

Two pieces of land are connected if they are adjacent horizontally or vertically.

Function Signature

def countIslandsAfterAdditions(n: int, positions: List[List[int]]) -> List[int]:

Constraints

• 1 <= n <= 1000
• 1 <= len(positions) <= n * n
• Coordinates are 0-indexed.

Examples

Example 1: Input: n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]

• After [0,0]: Grid has 1 island.
• After [0,1]: New land connects to [0,0]. Grid has 1 island.
• After [1,2]: New land is isolated. Grid has 2 islands.
• After [2,1]: New land connects to [1,2] (via vertical/horizontal neighbors). Grid has 2 islands. Output: [1, 1, 2, 2]

Edge Cases

• Multiple additions to the same coordinate (the cell remains land).
• Adding land that merges two or more existing islands.
• An empty positions list or a full grid.