Number of Islands II

Description

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.

0 is represented as the sea, 1 is represented as the island. If two 1 is adjacent, we consider them in the same island. We only consider up/down/left/right adjacent.

Example

Example 1:

Input: n = 4, m = 5, A = [[1,1],[0,1],[3,3],[3,4]]
Output: [1,1,2,2]
Explanation:
0.  00000
    00000
    00000
    00000
1.  00000
    01000
    00000
    00000
2.  01000
    01000
    00000
    00000
3.  01000
    01000
    00000
    00010
4.  01000
    01000
    00000
    00011

Example 2:

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

public class Solution {
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        List<Integer> ans = new ArrayList<>();
        if (operators == null || operators.length == 0)
            return ans;
        Point[][] parent = new Point[n][m];
        int count = 0;
        int[][] dir = { { 1, 0 }, { 0, 1 }, { -1, 0 }, { 0, -1 } };
        for (Point p : operators) {
            // Self parent in starting
            if(parent[p.x][p.y]!=null){
                ans.add(count);
                continue;
            }
            parent[p.x][p.y] = p;
            boolean inIsland = false;
            for (int i = 0; i < 4; i++) {
                int newX = p.x + dir[i][0];
                int newY = p.y + dir[i][1];
                if (newX >= 0 && newX < n && newY >= 0 && newY < m && parent[newX][newY] != null) {
                    if (!inIsland) {
                        parent[p.x][p.y] = parent[newX][newY];
                        inIsland = true;
                    } else {
                        Point topParent1 = findParent(parent, parent[newX][newY]);
                        Point topParent2 = findParent(parent, p);
                        if (topParent1.x != topParent2.x || topParent1.y != topParent2.y) {
                            parent[topParent1.x][topParent1.y] = topParent2;
                            count--;
                        }
                    }
                }
            }
            if (!inIsland)
                count++;
            ans.add(count);
        }
        return ans;
    }

    public Point findParent(Point[][] parent, Point p) {
        while (parent[p.x][p.y].x == p.x && parent[p.x][p.y].y == p.y)
            return p;
        return parent[p.x][p.y]=findParent(parent,parent[p.x][p.y]);
    }
}