Question

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).

1
2
3

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid0 into a land.

1
2
3

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

Operation #2: addLand(0, 1) turns the water at grid0 into a land.

1
2
3

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

Operation #3: addLand(1, 2) turns the water at grid1 into a land.

1
2
3

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

Operation #4: addLand(2, 1) turns the water at grid2 into a land.

1
2
3

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?

Solution

解法是使用union-find并查法

二维数据转换成一维，实现quick-find，同时赋值-1，因为有可能是根节点是0
利用方向只能是横的跟竖的特性，遍历4个方向，然后选择对手，接着找到临近节点的根节点
如果临近节点已经是岛了，就union起来，然后减一

优化采用权重合并和压缩路径，两者都是可以降低树的高度。

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[] parents = new int[m*n];
        int[] sizes = new int[m*n]; // weight
        //fill parents[] with -1 as parents[i] would be in [0, m*n-1];
        Arrays.fill(parents, -1);
        //directions used for calculating positions of 4 neighbors
        int[][] directions = {{-1,0},{1,0},{0,-1},{0,1}};
        //count varies with each operation (iterating positions)
        int count = 0;
        
        //iterate each operation (adding island on certain position)
        for (int[] position: positions) {
            //2D converted to 1D --> point = n*x+y, save to island
            int island = n*position[0]+position[1];
            //the parent is the island itself
            parents[island] = island;
            sizes[island]++;
            //after added the new island, increase count
            count++;
            for (int[] direction: directions) {
                //calculate each neighbor --> 2D to 1D, save to neighbor
                int x = position[0]+direction[0];
                int y = position[1]+direction[1];
                int neighbor = n*x+y;
                //continue if neighbor position invalid or neighbor ancestor remains -1 (no island)
                if (x < 0 || y < 0 || x >= m || y >= n || parents[neighbor] == -1) continue;
                
                //FIND the neighbor ancestor (the existing island)
                int nbParent = findParent(neighbor, parents);
                int parent = findParent(island, parents);
                //when neighbor's island is a different island, do UNION, and reduce count
                // compare size
                if (sizes[nbParent] >= sizes[island]) {
                    parents[parent] = nbParent;
                    sizes[nbParent] += sizes[island];
                } else {
                    parents[nbParent] = parent;
                    sizes[parent] += sizes[nbParent];
                }
                cnt--;
            }
            //operation ended, add count of current operation into result list
            res.add(count);
        }
        return res;
    }
    
    private int findParent(int island, int[] parents) {
        // compress path 
        while (island != parents[island]) {
            parents[island] = parents[parents[island]];
            island = parents[island];
        }
        return island;
    }
}