LeetCode 305. Number of Islands II Detailed Explanation + Coding UnionFind: Rank & Path Compression

[@algorithmssimplified1563]

In the video, I forget to include the big-O analysis, but the solution takes O((m * n) + p) time + O(m * n) memory, where m and n are the dimensions of the grid, and p is the length of positions. TIME: UnionFind without rank and path compression could take O(m * n), since a tree can be skewed to have all nodes to one side, creating a O(m * n) tall tree for find() method to traverse. Using rank to balance the tree into having O(log(m * n)) height, and having path compression complement rank makes the amortized time complexity practically O(1) (See www.geeksforgeeks.org/union-find-algorithm-set-2-union-by-rank/ for details). Therefore, we need O(p * 1) to union and find trees + O(m * n) to initialize parents and rank arrays = O((m * n) + p) time. SPACE: We need O(m * n) memory to initialize parents and rank arrays for UnionFind class, assuming there are no repeats of positions in p, or there is a guaranteed finite number of times a position in positions can be repeated so that O(p)