Skip to interview prep
Apexed

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
What does path compression do, and what are union-find costs with and without the optimizations — Data structures & algorithms interview question — Apexed