Number of Islands II

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:

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]

TIPS:

和 Number of Islands 一毛一样，只是这次DFS和BFS的复杂度都变很高，要O(knm)。所以用UF做法，操作第K个点的复杂度为O(K)。 设count为0，每加一个岛做一次UF，如果发现与别的岛相连就count--。注意这里用了compress find，时间复杂度大大降低哟，因为compress的平摊复杂度是O(1)。

Code:

public class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> result = new ArrayList<Integer>();
        int count = 0;
        HashMap<Integer, Integer> map = new HashMap<>();
        int[][] distance = {{1,0},{-1,0},{0,1},{0,-1}};
        for (int[] pos : positions) {
            int x = pos[0];
            int y = pos[1];
            map.put(x * n + y, x * n + y);
            count++;
            for (int[] d : distance) {
                int nx = x + d[0];
                int ny = y + d[1];
                int npos = nx * n + ny;
                if (nx < 0 || ny < 0 || nx >= m || ny >= n || !map.containsKey(npos)) {
                    continue;
                }
                int fa_x = find(x * n + y, map);
                int fa_y = find(npos, map);
                if (fa_x != fa_y) {
                    map.put(fa_x, fa_y);
                    count--;
                }
            }
            result.add(count);
        }
        return result;
    }

    private int find(int pos, HashMap<Integer, Integer> map) {
        int father = map.get(pos);
        while (father != map.get(father)) {
            father = map.get(father);
        }
        // find compress here
        int temp = -1;
        while (pos != map.get(pos)) {
            temp = map.get(pos);
            map.put(pos, father);
            pos = temp;
        }
        //end of the compress
        return father;
    }
}