Number of Islands II

Given a n,m which means the row and column of the 2D matrix and an array of pair A( size k). Originally, the 2D matrix is all 0 which means there is only sea in the matrix. The list pair has k operator and each operator has two integer A[i].x, A[i].y means that you can change the grid matrix[A[i].x][A[i].y] from sea to island. Return how many island are there in the matrix after each operator.

Example:

Given n = 3, m = 3, array of pair A = [(0,0),(0,1),(2,2),(2,1)].

return [1,1,2,2].

Solution:

Use UnionFInd to merge land cell into different island. When a new land cell is coming in, we increase the counter for island. If this cell is merged with its neighbor, we decrease the counter.

In the end, the counter will store all separated islands.

Code:

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
public class Solution {
    /**
     * @param n an integer
     * @param m an integer
     * @param operators an array of point
     * @return an integer array
     */

    private static final int[] XMOVES = {1, -1, 0, 0};
    private static final int[] YMOVES = {0, 0, 1, -1};

    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        List<Integer> res = new ArrayList<>();
        if (operators == null || operators.length == 0) {
            return res;
        }
        UnionFind uf = new UnionFind(n * m);
        int count = 0;
        int[][] grid = new int[n][m];
        for (Point p : operators) {
            if (grid[p.x][p.y] == 1) {
                continue;
            }
            grid[p.x][p.y] = 1;
            count++;
            int shortP = shortenIdx(p.x, p.y, m);
            for (int i = 0; i < XMOVES.length; i++) {
                int x = p.x + XMOVES[i];
                int y = p.y + YMOVES[i];
                if (island(x, y, grid)) {
                    int shortCur = shortenIdx(x, y, m);
                    if (uf.find(shortP) != uf.find(shortCur)) {
                        count--;
                        uf.union(shortP, shortCur);
                    }
                }
            }
            res.add(count);
        }
        return res;
    }

    private int shortenIdx(int x, int y, int m) {
        return x * m + y;
    }

    private boolean island(int x, int y, int[][] grid) {
        if (x < 0 || x >= grid.length || y < 0 || y >= grid[x].length) {
            return false;
        }
        return grid[x][y] == 1;
    }

    class UnionFind {
        private int[] father;
        public UnionFind(int n) {
            father = new int[n];
            for (int i = 0; i < n; i++) {
                father[i] = i;
            }
        }
        public int find(int i) {
            int parent = father[i];
            while (parent != father[parent]) {
                parent = father[parent];
            }
            //compress update
            int temp = -1;
            int fa = father[i];
            while (fa != father[fa]) {
                temp = father[fa];
                father[fa] = parent;
                fa = temp;
            }
            return parent;
        }
        public void union(int a, int b) {
            int parentA = find(a);
            int parentB = find(b);
            father[parentB] = parentA;
        }
    }
}