211. Compare quick-find and quick-union implementations of disjoint sets.
MediumDisjoint sets
Technical
Show model answer
Quick-find stores a set id per element. find is O(1), but union must relabel every element of one set, O(n) per union and O(n²) for n − 1 unions.
Quick-union stores a parent pointer per element, forming trees whose roots are representatives. union just links one root under the other, but without balancing the trees can degenerate into a chain, making find O(n) worst case. The fix is union by size or rank plus path compression, which together make both operations nearly constant amortized.