Union Find

Question 1

What are two data structures needed in Union-Find (disjoint data set)?

Answer 1

Data Structures Needed in Union-Find
1. Size (or Rank) Array:
* This array keeps track of the number of elements (or rank) in the set for which a node is a root.
* Helps in optimizing merging (union) by attaching smaller trees to larger trees.
2. Parent Dictionary (or Array):
* This keeps track of the parent node of each node.
* If a node is its own parent, it is the root of a set.

class UnionFind:
def __init__(self, n):
self.parent = {i: i for i in range(n)} # Each node is its own parent initially
self.size = {i: 1 for i in range(n)} # Each set starts with size 1

def find(self, node):
    if self.parent[node] != node:  # Path compression
        self.parent[node] = self.find(self.parent[node])
    return self.parent[node]

def union(self, node1, node2):
    root1 = self.find(node1)
    root2 = self.find(node2)

    if root1 != root2:  # Only union if they are in different sets
        if self.size[root1] > self.size[root2]:  # Union by size
            self.parent[root2] = root1
            self.size[root1] += self.size[root2]
        else:
            self.parent[root1] = root2
            self.size[root2] += self.size[root1]

Question 2

What are two methods needed in a Union-Find (disjoint data set)?

Answer 2

Methods of Union-Find
1. Union (merge two sets)
* Unites two nodes by making one the parent of the other.
* Uses the size or rank heuristic (Union by Size or Rank) to attach smaller trees to larger trees for efficiency.
2. Find (find the root of a node)
* Finds the root representative of a node.
* Uses path compression to make future lookups faster by directly linking nodes to the root.

class UnionFind:
def __init__(self, n):
self.parent = {i: i for i in range(n)} # Each node is its own parent initially
self.size = {i: 1 for i in range(n)} # Each set starts with size 1

def find(self, node):
    if self.parent[node] != node:  # Path compression
        self.parent[node] = self.find(self.parent[node])
    return self.parent[node]

def union(self, node1, node2):
    root1 = self.find(node1)
    root2 = self.find(node2)

    if root1 != root2:  # Only union if they are in different sets
        if self.size[root1] > self.size[root2]:  # Union by size
            self.parent[root2] = root1
            self.size[root1] += self.size[root2]
        else:
            self.parent[root1] = root2
            self.size[root2] += self.size[root1]

Question 3

What’s the TC of Union Find?

Answer 3

Time Complexity
* Find with path compression: O(α(n)), nearly constant time.
* Union with size/rank heuristic: O(α(n)), nearly constant time.
* α(n) is the inverse Ackermann function, which grows extremely slowly.

Question 4

What’s SC of union find?

Answer 4

Space Complexity Breakdown
1. Parent Array/Dictionary:
* Stores the parent of each node → O(n)
2. Size (or Rank) Array/Dictionary:
* Stores the size or rank of each set → O(n)

Since we store at most O(n) + O(n) = O(n) additional space, the overall space complexity is:

Space Complexity: O(n)
* This is optimal and scales linearly with the number of elements.

Can Union-Find Be Space Optimized?
* Without the Size/Rank Array: We can remove the size array if we don’t use union by size/rank, but it may lead to inefficient merging, increasing the time complexity.
* Path Compression Only: With path compression, we don’t need explicit rank storage, but the parent array is still O(n).