Union-Find: The Matrix of Disjoint Sets

The Quest Begins (The Why)

The author recalls their first encounter with a LeetCode problem that required counting separate groups of friends in a social network. They initially attempted a nested loop solution, which worked for small examples but became inefficient as input size increased. The author felt frustrated because they were addressing the problem incorrectly, focusing on pairwise comparisons rather than dynamic merging of connectivity.

A friend shared a video about Union-Find (Disjoint Set Union, DSU), which introduced the author to a new way of thinking about connectivity. The revelation of Union-Find's power came when they saw how it dynamically merges sets and flattens trees for efficient queries.

The Revelation (The Insight)

Union-Find functions by treating each element as part of a set, with each set having a representative called the "root." When two elements are connected, the algorithm only needs to check their roots. If they share the same root, they are already in the same component. Otherwise, one root is attached to the other. Two key optimizations improve performance: Union by rank/size ensures the smaller tree is always attached under the larger one, keeping the overall depth shallow.

Path compression, when querying a node's root, makes every node on the path point directly to the root, making future lookups almost instantaneous. Together, these heuristics result in an amortized time complexity of α(n) (inverse Ackermann), which is so slow-growing that for practical inputs, it behaves like O(1). This means each union or find operation is effectively constant, and a sequence of m operations on n elements runs in O(m α(n)) ≈ O(m) time.

Wielding the Power (Code & Examples)

Before using Union-Find naively, the author provided a DFS-based approach to count connected components in a graph, which had an O(n + e) time complexity per query, becoming a bottleneck for many connectivity checks. After adopting Union-Find, they presented a UnionFind class with two main methods: find and union. The find method implements path compression, collapsing the path to the root for quick future access.

The union method uses Union by rank to attach the smaller tree under the larger one, preventing tall trees. The author then demonstrated how Union-Find could solve two classic problems: Number of Islands (LeetCode 200) and another unspecified problem, both showcasing the efficiency and practicality of Union-Find in handling dynamic connectivity queries.