Union-Find Path Compression Dry Run for Beginners

Disjoint set union (DSU) solves connectivity questions fast, but the parent updates can feel invisible. This dry run illustrates each find and union with path compression so you can narrate the structure clearly in interviews.

TL;DR

• Topic: Disjoint set union with path compression and union by rank.
• Interview value: Guarantees near-constant amortized operations and demonstrates data structure rigor.
• Core steps: initialize parents, find with compression, union by rank, answer queries.
• Beginners often skip rank updates, forget to attach smaller trees, or miss compressing during find.
• You'll get a diagram-friendly walkthrough, TypeScript code, prep drills, and pitfalls to avoid.

Beginner-Friendly Explanations

The Forest Mental Model

Think of each node pointing to a parent; roots point to themselves. Compression flattens paths so future finds walk fewer edges, aligning with the sliding window learning path.

Why Union by Rank Matters

Attaching the smaller tree under the larger keeps height small. Without it, compression alone can still leave skewed trees that slow repeated queries.

How Path Compression Feels in Practice

During find(x), you recursively reach the root, then rewrite parent[x] to that root on the way back. This "shortcut" is the secret to almost O(1) queries.

Step-by-Step Learning Guidance

1) Initialize Parents and Rank

Create parent[i] = i and rank[i] = 1 for all nodes. Handle empty inputs and single-node cases first, habits consistent with the interview communication guide.

2) Implement find with Compression

When find(x) recurses, set parent[x] = find(parent[x]) to flatten the path. This keeps future queries quick.

3) Implement union by Rank

Find roots of a and b. If equal, do nothing. Otherwise attach the lower-rank root under the higher. If ranks tie, pick one root, attach, and increment its rank.

4) Narrate While Dry Running

For edges (0,1), (1,2), (3,4), say out loud: "connect 0-1 -> roots 0 and 1, attach 1 under 0; connect 1-2 -> roots 0 and 2, attach 2 under 0." This narration prepares you for a mock interview routine.

5) Verify Connectivity Queries

Answer find(x) == find(y) for pairs like (0,2) or (2,3). After compression, parents should point directly to roots.

Visualizable Example: DSU in TypeScript

class DSU {
  parent: number[];
  rank: number[];

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = Array(n).fill(1);
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(a: number, b: number): void {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return;

    if (this.rank[rootA] < this.rank[rootB]) {
      this.parent[rootA] = rootB;
    } else if (this.rank[rootA] > this.rank[rootB]) {
      this.parent[rootB] = rootA;
    } else {
      this.parent[rootB] = rootA;
      this.rank[rootA]++;
    }
  }
}

Trace the parents after unions (0,1), (1,2), (3,4), (2,4). You should see all nodes compressed under a single root.

Practical Preparation Strategies

Draw Parents After Every Operation

Record parent arrays after each union. This visualization trains you to spot whether compression actually shortened paths.

Mix Query Orders

Interleave finds and unions to mimic interview follow-ups. This strengthens muscle memory for when compression triggers.

Compare With and Without Compression

Run the same sequence with compression commented out. Observe the deeper trees and slower reasoning; this contrast sticks, especially when using the AI prep primer.

Light Guidance Only When Needed

Tools like LeetCopilot can point out missed rank bumps without revealing the entire solution, keeping your reasoning intact.

Common Mistakes to Avoid

Forgetting to Return the Root in find

If find doesn't return the compressed root, unions may attach wrong parents.

Skipping Rank Updates

Without rank bumps on ties, future unions might favor already larger trees incorrectly.

Compressing Only Sometimes

Always compress on find; partial compression leaves inconsistent depths that complicate debugging.

Assuming 1-Indexed Nodes

If the input uses 0-indexing, offset mistakes break connectivity checks. Confirm indexing early.

FAQ

How do I know compression worked?

After a find call, parent[x] should equal the ultimate root; printing the parent array after queries helps verify.

What should I practice before DSU?

Be comfortable with arrays, recursion, and simple graph representations.

Is DSU important for interviews?

Yes—it's common in graph connectivity, Kruskal's MST, and grouping problems.

Can I skip union by rank if I compress paths?

You can, but rank keeps trees shallow even before many queries run, improving consistency.

Conclusion

Union-find with path compression rewards careful narration: initialize cleanly, compress on every find, and attach by rank. With steady dry runs and small diagrams, you'll answer connectivity questions confidently without hand-waving.