Union-Find Core Concept
Union-Find (Disjoint Set Union, DSU) efficiently tracks which elements belong to the same connected component. Two operations: find(x): returns the root (representative) of x’s component. union(x, y): merges the components of x and y. Naive implementation: O(n) per operation. With two optimizations, nearly O(1) amortized: Path compression (in find): after finding the root, make every node on the path point directly to the root. Flattens the tree for future queries. Union by rank (in union): attach the smaller tree under the root of the larger tree. Prevents the tree from becoming a linked list. Together: O(α(n)) per operation where α is the inverse Ackermann function — essentially constant for any practical n.
class UnionFind:
def __init__(self, n):
self.parent = list(range(n))
self.rank = [0] * n
self.components = n
def find(self, x):
if self.parent[x] != x:
self.parent[x] = self.find(self.parent[x]) # path compression
return self.parent[x]
def union(self, x, y):
rx, ry = self.find(x), self.find(y)
if rx == ry: return False # already connected
if self.rank[rx] < self.rank[ry]: rx, ry = ry, rx
self.parent[ry] = rx
if self.rank[rx] == self.rank[ry]: self.rank[rx] += 1
self.components -= 1
return TrueNumber of Connected Components (LC 323, 547)
Initialize n components (one per node). For each edge (u, v): union(u, v). If they were in different components: components -= 1. Return components count at the end. This is the most direct Union-Find application. LC 547 (Friend Circles / Number of Provinces): same pattern on an adjacency matrix. LC 684 (Redundant Connection): the redundant edge is the first edge (u, v) where find(u) == find(v) before union — they were already connected, so this edge creates a cycle.
Number of Islands with Union-Find (LC 200)
Alternative to BFS/DFS. Initialize all ‘1’ cells as separate components. For each ‘1’ cell: union with adjacent ‘1’ cells. Count remaining components after processing all cells. Each union reduces the count by 1. Final count = number of islands. BFS/DFS is usually preferred for this problem (simpler to implement, same O(mn) time). Union-Find shines when the grid is given incrementally (cells added over time, like LC 305 Number of Islands II): process one cell at a time, union with existing adjacent ‘1’ cells, track the component count after each addition.
Kruskal’s MST with Union-Find
Minimum Spanning Tree (LC 1135, 1168, 1584): connect all nodes with minimum total edge weight. Kruskal’s: sort edges by weight. Process edges in order: if the two endpoints are in different components (find(u) != find(v)), add this edge to the MST and union them. Stop when n-1 edges are added (spanning tree complete) or all edges are processed. O(E log E) for sorting. Union-Find makes the connectivity check O(α(n)). LC 1584 (Min Cost to Connect All Points): build edges between all point pairs (cost = Manhattan distance), run Kruskal’s. Note: for dense graphs (all pairs), Prim’s algorithm is O(n^2) which can be better than Kruskal’s O(n^2 log n).
Weighted Union-Find and Advanced Patterns
Weighted Union-Find: each parent edge has a weight. Queries ask about the relationship between two nodes (e.g., ratio between values — LC 399 Evaluate Division). find(x) returns both the root and the accumulated weight along the path. LC 399: equations give ratios (a/b = 2.0). Model as a weighted graph: union(a, b) with weight 2.0. find(x) returns (root, product_of_weights_along_path). To evaluate a/b: find both roots; if same root, return weight(a) / weight(b). LC 1202 (Smallest String with Swaps): union all swappable index pairs. Within each component, sort the characters and place them in sorted order at the component’s positions. The key insight: any permutation of elements within a component is achievable via the allowed swaps.
Asked at: Meta Interview Guide
Asked at: Apple Interview Guide
Asked at: LinkedIn Interview Guide
Asked at: Atlassian Interview Guide