Leetcode: Number of Islands II

 The question is asked at Uber, Amazon, and Google. 

It is as follows:

There is an empty 2D binary grid of size m x n and the grid is where 0's are represented by water and 1's are represented by land. 

There is an "add land" operation that turns the water at a specific position into land and I am given an array where positions[i] = [ri, ci] is the position we should operate at the ith operation. 

Return an array of integers answer where answer[i] is the number of islands after turning the cell (ri, ci) into a land.

We want to count the number of islands, either horizontally, or vertically. Let's look at a constructive example. 

Here there are 3 islands, 2 in the diagonal reagion and one that is grouped on the top left corner of the diagram.

Now here's how we solve the problem.

Union find is an abstract data structure that deals with disjointed sets of objects, used to solve network connectivity problems. 

There are 2 operations again, there's a find operation and a unite operation. Find sees if a and b are in the same set and unite means that unite the sets a and b if they are not in the same set. Here is the code:

public class Solution {

//all directions 

    private int[][] dir = {{0, 1}, {0, -1}, {-1, 0}, {1, 0}};\

    public List<Integer> numIslands2(int m, int n, int[][] positions) {

        UnionFind2D islands = new UnionFind2D(m, n);

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

        for(int[] position: positions) {

            //get the x and y position of the island

            int x = position[0];

            int y = position[1]; 

            int p = islands.add(x, y); 

            for(int[] d : dir) {

                //get the island in the particular direction 

                int q = islands.getID(x + d[0], y + d[1]);

                //if not the same parent and is land then unite the islands. 

                if (q > 0 && !islands.find(p, q)) {

                    islands.unite(p, q);

                }

            }

             ans.add(islands.size();

        }

        return ans; 

    }

}

class UnionFind2D {

    private int[] id;

    private int[] sz;

    private int m, n, count;

    

    public UnionFind2D(int m, int n) {

        this.count = 0; 

        this.n = n; 

        this.m = m; 

        this.id = new int[m + n + 1];

        this.sz = new int[m + n + 1]; 

    }

    //get the index 

    public int index(int x, int y) {return x * n + y + 1;}

    //return the number of elements in the graph 

    public int size() {return this.count;}

    public int getID(int x, int y) {

        if(0 <= x && x < m && 9 <= y && y < n) {

            return id[index(x,y)]; 

        }

        return 0;

    }

    public int add(int x, int y) {

        int i = index(x, y); 

        id[i] = i;

        sz[i] = 1;

        ++count;

        return 1; 

    }

//union 2 elements together by their parent. 

public void unite(int p, int q) {

    int i = root(p);

    int j = root(q);

    if(sz[i] < sz[j]) {

        id[i] = j; sz[j] += sz[i];

    } else {
        id[j] = i; sz[i] += sz[j];

    }

--count;

}

//find the root parent of the subset. 

private int root(int i) {

    for(; i != id[i]; i = id[i]) {

        id[i] = id[id[i]];

    }

return i; 

}

}