A map has rows × cols cells, and every cell starts as water. positions lists cells [r, c] that are turned into land one at a time, in order. An island is a group of land cells joined horizontally or vertically (diagonals don't count). Turning a cell that is already land changes nothing, and the same cell can appear in positions more than once.
Write islands_after_each(rows: int, cols: int, positions: list[list[int]]) -> list[int]: the number of islands right after each step, one count per entry of positions.
Examples:
islands_after_each(3, 4, [[0, 0], [2, 3], [0, 2], [0, 1], [1, 3], [2, 0], [0, 3], [0, 3]])
# [1, 2, 3, 2, 2, 3, 2, 2]
Steps 1 to 3 each start a new island. Step 4, [0, 1], lands between [0, 0] and [0, 2] and joins them: 2 islands. Step 5 grows the island at [2, 3]. Step 7, [0, 3], links the top row to the right-hand column, and step 8 repeats it, so nothing changes.
islands_after_each(1, 1, [[0, 0], [0, 0]]) # [1, 1]
islands_after_each(2, 2, [[0, 0], [1, 1], [0, 1]]) # [1, 2, 1] diagonal cells are separate until [0, 1] joins them
Constraints:
1 <= rows, colsandrows * cols <= 10^5.0 <= len(positions) <= 10^5, and every[r, c]is inside the map.
⭐ Bonus: speed tests on 200 × 200 maps with up to 50,000 steps earn a star in close to O(rows · cols + k) time, where k = len(positions). Counting the islands again with a flood fill after every step costs up to 40,000 cells per step there, billions of visits in all.
Show hint
a new land cell is a new island of its own, and then every neighbouring island it touches merges with it, lowering the count by one per merge. Merging and asking "are these two cells already on the same island?" is what a union-find is for.