Pattern #22 — Union Find (Disjoint Set Union / DSU) 🔗

Pattern #22 — Union Find (Disjoint Set Union / DSU) 🔗

Union Find is a specialist tool with one job it does brilliantly: tracking which things are connected into groups, and merging groups fast.

1. The Idea (in one line)

Keep track of groups. Ask "are these two in the same group?" and "merge these two groups" — both nearly instantly.

   Real-life analogy 👨‍👩‍👧‍👦
   ─────────────────────────
   Friend circles. Each person belongs to a group of friends.
   • "Are Sam and Alex in the same circle?" → find their circle,
     compare.
   • "Sam and Alex become friends" → merge their two circles
     into one.
   Union Find does exactly this, super fast.

2. The Two Operations

   FIND(x)  → which group does x belong to? (returns a "leader")
   UNION(x, y) → merge x's group and y's group into one.

   The trick: each group has a single "leader" (also called root
   or representative). Two items are in the same group if they
   have the SAME leader.

3. The Picture

   Start: everyone is their own leader (5 separate groups)
   0   1   2   3   4
   (each points to itself)

   union(0, 1) → 1's leader becomes 0
   0 ← 1     2   3   4

   union(2, 3) → 3's leader becomes 2
   0 ← 1     2 ← 3   4

   union(1, 3) → merge the two groups (0's tree and 2's tree)
   0 ← 1
   ↑
   2 ← 3        4

   Now find(3) and find(0) both return 0 → SAME group! ✅
   find(4) returns 4 → different group.

4. 🔍 How to SPOT This Pattern

   Use Union Find when you see:
   ✅ "are these two connected?"
   ✅ "how many groups / components / friend circles?"
   ✅ "merge accounts / networks"
   ✅ "does adding this edge create a cycle?" (Kruskal's MST)
   ✅ Lots of "connect these two" operations coming in over time
      (Union Find handles a STREAM of merges better than re-running DFS).

5. The Code Template 📝

   class UnionFind {
     constructor(n) {
       this.parent = Array.from({ length: n }, (_, i) => i);  // self-leader
       this.rank = new Array(n).fill(0);                       // tree size hint
     }

     find(x) {                       // who is x's leader?
       if (this.parent[x] !== x)
         this.parent[x] = this.find(this.parent[x]);  // path compression
       return this.parent[x];
     }

     union(x, y) {                   // merge the two groups
       const rootX = this.find(x), rootY = this.find(y);
       if (rootX === rootY) return false;   // already together (a cycle!)
       // attach smaller tree under bigger (union by rank)
       if (this.rank[rootX] < this.rank[rootY]) this.parent[rootX] = rootY;
       else if (this.rank[rootX] > this.rank[rootY]) this.parent[rootY] = rootX;
       else { this.parent[rootY] = rootX; this.rank[rootX]++; }
       return true;
     }

     connected(x, y) { return this.find(x) === this.find(y); }
   }

6. The Two Optimizations (say these in interviews)

   • PATH COMPRESSION: when you find a leader, point everyone
     along the way directly to it → future lookups are faster.

   • UNION BY RANK/SIZE: always attach the smaller tree under the
     bigger one → keeps trees flat.

   With both, find and union are almost O(1) (technically the
   inverse-Ackermann function — practically constant). 🚀

7. Practice Problems

   ⭐ core
   • Number of Provinces (friend circles)
   • Number of Connected Components in a Graph

   ⭐⭐ Medium
   • Redundant Connection (find the edge making a cycle)
   • Accounts Merge
   • Graph Valid Tree
   • Number of Islands II (adding land over time)

8. ⚠️ Common Mistake

   ❌ Comparing x and y directly instead of their LEADERS. Two
      items are in the same group only if find(x) === find(y),
      not if x === y.
   ❌ Skipping path compression — it still works, just slower.

Key Takeaway

   Union Find = track connected groups with a "leader" per group.
   find() = which group; union() = merge groups. With path
   compression + union by rank, it's nearly O(1). The go-to for
   "are these connected?", counting components, and cycle detection
   as edges arrive.

Next: Pattern #23 — Bitwise Manipulation, doing magic with 1s and 0s. 💡