> For the complete documentation index, see [llms.txt](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://jimmylin1991.gitbook.io/practice-of-algorithm-problems/graph/305.-number-of-islands-ii.md).

# 305. Number of Islands II

A 2d grid map of `m` rows and `n` columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, **count the number of islands after each addLand operation**. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

**Example:**

```
Input: m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]]
Output: [1,1,2,3]
```

**Explanation:**

Initially, the 2d grid `grid` is filled with water. (Assume 0 represents water and 1 represents land).

```
0 0 0
0 0 0
0 0 0
```

Operation #1: addLand(0, 0) turns the water at grid\[0]\[0] into a land.

```
1 0 0
0 0 0   Number of islands = 1
0 0 0
```

Operation #2: addLand(0, 1) turns the water at grid\[0]\[1] into a land.

```
1 1 0
0 0 0   Number of islands = 1
0 0 0
```

Operation #3: addLand(1, 2) turns the water at grid\[1]\[2] into a land.

```
1 1 0
0 0 1   Number of islands = 2
0 0 0
```

Operation #4: addLand(2, 1) turns the water at grid\[2]\[1] into a land.

```
1 1 0
0 0 1   Number of islands = 3
0 1 0
```

**Follow up:**

Can you do it in time complexity O(k log mn), where k is the length of the `positions`?

```cpp
// Union-Find
int findRoot(vector<int>& roots, int id) {
    return id == roots[id] ? id : roots[id] = findRoot(roots, roots[id]);
}
vector<int> numIslands2(int m, int n, vector<vector<int> >& positions) {
    if (m == 0 || n == 0 || positions.empty()) return {};
    int count = 0;
    vector<int> res, roots(m * n, -1), size(m * n, 1);
    vector<int> dir({0, 1, 0, -1, 0});
    for (vector<int>& pos : positions) {
        int id = pos[0] * n + pos[1];
        if (roots[id] == -1) { // fill land
            roots[id] = id;
            ++count;
        }
        for (int k = 0; k < 4; ++k) { // union with neighboring lands
            int x = pos[0] + dir[k], y = pos[1] + dir[k + 1], cur_id = x * n + y;
            if (x < 0 || x >= m || y < 0 || y >= n || roots[cur_id] == -1) continue;
            int r1 = findRoot(roots, cur_id), r2 = findRoot(roots, id);
            if (r1 != r2) {
                if (size[r1] > size[r2]) {
                    roots[r2] = r1;
                    size[r1] += size[r2];
                } else {
                    roots[r1] = r2;
                    size[r2] += size[r1];
                }
                --count;
            }
        }
        res.push_back(count);
    }
    return res;
}
```