1051. Number of Islands II (Dynamic)

Given an m x n grid initially all water, process a list of positions that each add land at [row, col]. After each addition, report the current number of islands (land connected 4-directionally). Adding land on an already-land cell leaves the count unchanged. Return the counts as an array. The input is JSON {m, n, positions}.

Input: JSON {m, n, positions}.

Output: Array — island count after each addition.

Examples

Input: {"m":3,"n":3,"positions":[[0,0],[0,1],[1,2],[2,1]]}
Output: [1,1,2,3]
Explanation: Counts after each land add.

Input: {"m":1,"n":1,"positions":[[0,0]]}
Output: [1]
Explanation: One island.

Input: {"m":2,"n":2,"positions":[[0,0],[1,1],[0,1]]}
Output: [1,2,1]
Explanation: The third add merges two islands.

Constraints

• 1<=m,n<=1000
• 1<=positions<=10^4

Asked by