Lintcode 434. 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

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]

Notice

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.

Code (Java):

public class Solution {
    private int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    private int numCC = 0;

    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        List<Integer> ans = new ArrayList<>();
        
        if (operators == null || operators.length == 0) {
            return ans;
        }

        int[] parents = new int[n * m];
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                parents[i * m + j] = i * m + j;
            }
        }

        Set<Integer> islands = new HashSet<>();

        for (Point point : operators) {
            if (!islands.contains(point.x * m + point.y)) {
                islands.add(point.x * m + point.y);
                numCC++;
                for (int i = 0; i < 4; i++) {
                    connect(point.x, point.y, point.x + dirs[i][0], point.y + dirs[i][1], n, m, islands, parents);
                }
            }
            ans.add(numCC);
        }
        return ans;
    }

    private void connect(int ax, int ay, int bx, int by, int n, int m, Set<Integer>islands, int[] parents) {
        if (bx < 0 || bx >= n || by < 0 || by >= m) {
            return;
        }

        if (!islands.contains(bx * m + by)) {
            return;
        }

        int rootA = find(ax, ay, n, m, parents);
        int rootB = find(bx, by, n, m, parents);

        if (rootA != rootB) {
            parents[rootB] = rootA;
            numCC--;
        }
    }

    private int find(int x, int y, int n, int m, int[] parents) {
        int p = x * m + y;
        int root = p;

        while (root != parents[root]) {
            root = parents[root];
        }

        // path compression
        //
        while (root != p) {
            int temp = parents[p];
            parents[p] = root;
            p = temp;
        }

        return root;
    }
}

/**
 * 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 int[] parents;
    private int numIslands = 0;
    
    private int find(int x) {
        int root = x;
        while (parents[root] != root) {
            root = parents[root];
        }
        
        // path compression
        while (root != x) {
            int temp = parents[x];
            parents[x] = root;
            x = temp;
        }
        
        return x;
    }
    
    private void union(int x, int y) {
        int parentX = find(x);
        int parentY = find(y);
        
        if (parents[parentX] != parentY) {
            parents[parentX] = parentY;
            numIslands--;
        }
    }
     
    public List<Integer> numIslands2(int n, int m, Point[] operators) {
        // write your code here
        List<Integer> ans = new ArrayList<>();
        if (n <= 0 || m <= 0 || operators == null || operators.length == 0) {
            return ans;
        }
        
        parents = new int[n * m];
        
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < m; j++) {
                parents[i * m + j] = i * m + j;
            }
        }
        
        int[][] islands = new int[n][m];
        int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
        
        for (Point opeartor : operators) {
            int x = opeartor.x;
            int y = opeartor.y;
            
            if (islands[x][y] == 1) {
                ans.add(numIslands);
                continue;
            }
            
            numIslands += 1;
            islands[x][y] = 1;
            
            for (int[] dir : dirs) {
                int nx = x + dir[0];
                int ny = y + dir[1];
                
                if (nx >= 0 && nx < n && ny >= 0 && ny < m && islands[nx][ny] == 1) {
                    union(x * m + y, nx * m + ny);
                }
            }
            
            ans.add(numIslands);
        }
        
        return ans;
    }
}