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.

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.

Example

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

return[1,1,2,2].

Solution

1. Define the matrix of n * m.
2. Loop through the array pair of A. For each round, it's like adding a new island to the matrix. If the position of a pair is already an island, then the total number of islands will be the same, so we just continue.
3. If the position of a pair, let's say (i, j), is not an island yet, then we mark it as an island: grid[i][j] = true, count++. Next we are going to check if this island (i, j) belongs to any existing island block.
4. Check its four directions to see if there is any adjacent island. If there is, union join the pair to the subset of the adjacent island (set it's parent to the root element of the subset), count--.

/**
 * Definition for a point.
 * class Point {
 *     int x;
 *     int y;
 *     Point() { x = 0; y = 0; }
 *     Point(int a, int b) { x = a; y = b; }
 * }
 */
class UnionFind {
    private int[] parent;
    private int count;

    public UnionFind(int size) {
        parent = new int[size];

        for (int i = 0; i < size; i++) {
            parent[i] = i;
        }

        count = 0;
    }

    public void setCount(int num) {
        count = num;
    }

    public int getCount() {
        return count;
    }

    public void countIncrement() {
        count++;
    }

    public int find(int x) {
        if (parent[x] == x) {
            return x;
        }
        return parent[x] = find(parent[x]);
    }

    public void connect(int x, int y) {
        int subsetx = find(x);
        int subsety = find(y);

        if (subsetx != subsety) {
            parent[subsetx] = subsety;
            count--;
        }
    }
}

public class Solution {
    /*
     * @param n: An integer
     * @param m: An integer
     * @param operators: an array of point
     * @return: an integer array
     */
    public List<Integer> numIslands2(int n, int m, Point[] operators) {

        List<Integer> result = new ArrayList<>();

        if (m == 0 || n == 0) {
            return result;    
        }

        if (operators == null || operators.length == 0) {
            return result;
        }

        boolean[][] grid = new boolean[n][m];
        int[][] directions = {{0, 1}, {0, -1}, {1, 0}, {-1, 0}}; 

        UnionFind uf = new UnionFind(m * n);
        uf.setCount(0);

        for (Point op : operators) {

            // if the next island is at the same position as a previous island, the number of islands won't change.
            if (grid[op.x][op.y]) {
                result.add(uf.getCount());
                continue;
            }

            uf.countIncrement();
            grid[op.x][op.y] = true;

            for (int i = 0; i < 4; i++) {
                int adjx = op.x + directions[i][0];
                int adjy = op.y + directions[i][1];

                if (inBoundary(adjx, adjy, n, m) && grid[adjx][adjy]) {
                    uf.connect(op.x * m + op.y, adjx * m + adjy);
                }
            }

            result.add(uf.getCount());
        }

        return result;
    }

    public boolean inBoundary(int x, int y, int n, int m) {
        if (x < 0 || x >= n || y < 0 || y >= m) {
            return false;
        }
        return true;
    }
}