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

# 305     Number of Islands II

## 305. [Number of Islands II](https://leetcode.com/problems/number-of-islands-ii/description/)

## 1. Question

A 2d grid map of`m`rows and`n`columns is initially filled with water. We may perform anaddLandoperation which turns the water at position (row, col) into a land. Given a list of positions to operate,**count the number of islands after eachaddLandoperation**. 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:**

Given`m = 3, n = 3`,`positions = [[0,0], [0,1], [1,2], [2,1]]`.\
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
```

We return the result as an array:`[1, 1, 2, 3]`

**Challenge:**

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

## 2. Implementation

**(1) Union Find**

思路: 动态连接的话用Union Find最适合

```java
class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> res = new ArrayList();

        if (m <= 0 || n <= 0) {
            return res;
        }

        int[][] directions = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};

        UnionFind uf = new UnionFind(m * n);

        for (int[] position : positions) {
            int row = position[0];
            int col = position[1];
            int id1 = row * n + col;

            uf.add(id1);

            for (int[] direction : directions) {
                int nextRow = row + direction[0];
                int nextCol = col + direction[1];

                if (isValid(nextRow, nextCol, m, n)) {
                    int id2 = nextRow * n + nextCol;

                    if (uf.getSize(id2) >= 1) {
                        uf.union(id1, id2);
                    }
                }
            }
            res.add(uf.count);
        }
        return res;
    }

    public boolean isValid(int row, int col, int m, int n) {
        return row >= 0 && row < m && col >= 0 && col < n;
    }

    class UnionFind {
        int[] sets;
        int[] size;
        int count;

        public UnionFind(int n) {
            sets = new int[n];
            size = new int[n];
            count = 0;
        }

        public void add(int id) {
            sets[id] = id;
            size[id] = 1;
            ++count;
        }

        public int getSize(int id) {
            return size[id];
        }

        public int find(int node) {
            while (node != sets[node]) {
                node = sets[node];
            }
            return node;
        }

        public void union(int i, int j) {
            int node1 = find(i);
            int node2 = find(j);

            if (node1 == node2) {
                return;
            }

            if (size[node1] < size[node2]) {
                sets[node1] = node2;
                size[node2] += size[node1];
            }
            else {
                sets[node2] = node1;
                size[node1] += size[node2];
            }
            --count;
        }
    }
}
```

## 3. Time & Space Complexity

时间复杂度O(k\* log(mn)), 空间复杂度O(mn)