213. What does path compression do, and what are union-find costs with and without the optimizations?
HardDisjoint sets
Technical
Show model answer
During find, after locating the root, point every node on the search path directly at the root (or use path halving: point each node at its grandparent while walking). Later finds on those nodes become nearly O(1).
Costs: plain quick-union is O(n) per operation worst case; union by rank alone gives O(log n); path compression alone gives O(log n) amortized; both together give O(α(n)) amortized per operation, where α is the inverse Ackermann function, which is at most 4 for any input size that fits in the universe. For m operations that is O(m α(n)), effectively linear.
What interviewers listen for
- Rank alone: O(log n)
- Compression alone: O(log n) amortized
- Both: O(α(n)) amortized