Union Find

Disjoint Set Union

1:00

How the disjoint-set forest tracks connected components in near-constant time using union by rank and path compression.

By the end, you can

Explain what a disjoint-set partition is and how the parent array represents it.
Trace `find(x)` on a given parent array and state which root it returns.
Trace a sequence of `union` calls and compute how many sets remain.
Explain why a naive forest degrades to O(n) and construct the worst-case chain.
Apply union by rank correctly, including when (and why) rank is incremented.
Describe what path compression does and why it does not update stored ranks.
State the three-tier complexity ladder: O(n) naive, O(log n) with one optimization, O(α(n)) with both.
Identify whether Union-Find can solve a given problem (connectivity / cycle / MST) versus problems it cannot (shortest path).

Up next in Coding Interview Patterns