Number of Islands II

You are given an empty m x n grid initially filled with water. We may perform an addLand operation where positions[i] = [ri, ci] turns the cell (ri, ci) into land. Return an array answer where answer[i] is the number of islands after the ith operation. An island is a maximal group of horizontally or vertically adjacent land cells.

Constraints

• 1 <= m, n <= 50
• 1 <= positions.length <= 50
• positions[i].length == 2
• 0 <= ri < m and 0 <= ci < n

Example 1

Input

m = 3, n = 3 positions = [[1, 0], [0, 1], [2, 2], [3, 3]]

Output

[1, 1, 2, 3]

Explanation

• Initially, there are no islands.
• After adding land at (1, 0), there is 1 island.
• After adding land at (0, 1), there is still 1 island (since it is connected to the first cell).
• After adding land at (2, 2), there are 2 islands (since it is not connected to the first island).
• After adding land at (3, 3), there are 3 islands.

Example 2

Input

m = 5, n = 7 positions = [[0, 0], [0, 1], [1, 1], [1, 0], [2, 2], [3, 3], [3, 4]]

Output

[1, 1, 1, 2, 2, 3, 3]

Hints

• Consider using a union-find data structure to efficiently track the number of islands.