What is Path Compression?

A technique that makes the "Find" operation flash-flat by pointing every node in a path directly to the root.

What is Union by Rank/Size?

A technique that always attaches the smaller tree under the root of the larger tree to keep the overall structure flat and efficient.

What is the Amortized Complexity?

With both optimizations, DSU achieves near-constant time O(α(n)), where α is the Inverse Ackermann Function.

Optimized Union-Find

Visualize how Path Compression and Union by Rank flatten the tree structure, achieving nearly constant time complexity.

Disjoint Set Union (DSU)

Ready

Node A

Node B

Path CompressionUnion by Rank

See the Logic in Motion

Stop memorizing code. Unlock the full interactive visualizer to master the logic step-by-step.

Unlock VisualizerPREMIUM FEATURE

Intuition

The naive Union-Find can degrade into a tall tree (like a linked list), making searching slow. We can fix this with two tricks:

1. Path Compression: When finding the leader, make every node on the path point directly to the leader. Next time, the lookup is instant.

2. Union by Rank: Always attach the shorter tree to the taller tree. This keeps the combined tree height minimal.

Concept

Optimizations:

Path Compression: During `find(x)`, set `parent[x] = find(parent[x])`. This flattens the path.
Union by Rank: Track tree height (rank). If `rank[rootX] > rank[rootY]`, `parent[rootY] = rootX`. If equal, increment rank of new root.

How it Works

Toggle the optimizations in the visualizer to see the difference!

Without Optimizations: Trees can get very deep.
With Path Compression: After a Find operation, all nodes on the path jump to the root.
With Union by Rank: Trees tend to look broad and shallow "bushes" rather than tall "spines".

Step-by-Step Breakdown

1. Find(x): If `parent[x] != x`, recursively call `find` and update `parent[x]` with the result. Return `parent[x]`.

2. Union(x, y): Find roots. Compare ranks. Attach smaller rank to larger rank. If equal, pick one and increment its rank.

When to Use

When you have millions of operations (N large, Q large).
MST algorithms (Kruskal) where speed is critical.
Dynamic graph connectivity.

When NOT to Use

If you need to reconstruct the history of unions (Compression destroys history).

How to Identify

"Fastest way to group items", "Check if graph is fully connected", "Detect cycle in undirected graph".

Stop Guessing, Start Mastering.

Build the FAANG intuition. Master this pattern with optimized implementations, visual dry runs, and our curated collection of high-yield problems.

Start Your Premium Prep