305 Number of Islands II *****Details !! Understanding of UF !!!

Union Find

Union Operation takes constant time when union find is implemented with both path compression and union by rank

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

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

Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0
Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0
Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0
Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0
Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0
Follow up:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

Treat the 2d grid map as an undirected graph (formatted as adjacency matrix) and there is an edge between two horizontally or vertically adjacent nodes of value1, then the problem reduces to finding the number of connected components in the graph after each_addLand_operation.

Make use of a Union Find data structure of size m*n to store all the nodes in the graph 
and initially each node's parent value is set to -1 to represent an empty graph. 
Our goal is to update Union Find with lands added by addLand operation and union lands belong to the same 
island.

For each addLand operation at position (row, col), 
union it with its adjacent neighbors if they belongs to some islands, 
if none of its neighbors belong to any islands, then initialize the new position as a new island 
(set parent value to itself) within Union Find.

Time complexity : O(m * n + L) L is the number of operations, m is the number of rows and n is the number
of cols. It takes o(m * n) to initialize Union Find, and O(L) to process positions
Note that Union Operation takes constant time when union find is implemented with both path compression
and union by rank
Space complexity O(m * N) as required by union find

In computer science, a disjoint-set data structure (also called a union–find data structure 
or merge–find set) is a data structure that tracks a set of elements partitioned into 
a number of disjoint (non-overlapping) subsets. 
It provides near-constant-time operations (bounded by the inverse Ackermann function)
 to add new sets, to merge existing sets, and to determine whether elements are in the same set.
  In addition to many other uses (see the Applications section), 
  disjoint-sets play a key role in Kruskal's algorithm for finding the minimum spanning tree of a graph.

Path compression
Path compression flattens the structure of the tree by making every node point to the root 
whenever Find is used on it. 
This is valid, since each element visited on the way to a root is part of the same set. 
The resulting flatter tree speeds up future operations not only on these elements, 
but also on those referencing them.

by rank[edit]
Union by rank always attaches the shorter tree to the root of the taller tree. 
Thus, the resulting tree is no taller than the originals unless they were of equal height, 
in which case the resulting tree is taller by one node.

To implement union by rank, each element is associated with a rank.
 Initially a set has one element and a rank of zero. 
 If two sets are unioned and have the same rank, the resulting set's rank is one larger; 
 otherwise, if two sets are unioned and have different ranks,
  the resulting set's rank is the larger of the two. 
  Ranks are used instead of height or depth because path compression will change 
  the trees' heights over time.

class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        List<Integer> ans = new ArrayList<>();
        if (m <= 0 || n <= 0) {
            return ans;
        }
        // union find first step: initialize the matrix
        int[] roots = new int[m * n];
        Arrays.fill(roots, -1);

        int count = 0;
        int[] dx = {0, 0, 1, -1};
        int[] dy = {1, -1, 0, 0};
        for (int[] pos : positions) {
            count++; // add the count for every node 
            int loc = n * pos[0] + pos[1]; //convert two dimensional pos to one dime pos
            roots[loc] = loc;  //mark the position with new loc

            for (int i = 0; i < 4; i++) { 
                // go four possible direcs to find if there is any islands
                int newX = pos[0] + dx[i];
                int newY = pos[1] + dy[i];
                int newLoc = n * newX + newY;
                if (newX < 0 || newX >= m || newY < 0 || newY >= n || roots[newLoc] == -1) {
                    continue;
                }
                //here is the trick
                int realPos = find(roots, newLoc); // first find the origin of the connected island
                if (realPos != loc) {
                    count--;
                    roots[loc] = realPos; // for the current added node, roots[curtNode] = parent;
                    loc = realPos;//must update the loc to the origin, !!!!!!!
                    //so that all the compare is done on parent nodes!!!!!!
                }
            }
            ans.add(count);
        }
        return ans;
    }
    public int find(int[] roots, int x) {
        while (roots[x] != x) { 
            //while (roots[x] != x) means it is not the root.. go find the root
            // not roots[x] == -1, since we have updated the nodes
            x = roots[x];
        }
        return x;
    }
}