Typorithm · medium

Find with Path Compression

union-find-findunion-finddisjoint-setpath-compressionroot

Saved on this device

Full lesson · 8 learning steps Open any exercise for focused practice

Step 1 of 8 · intro card

Learn Find with Path Compression

Union-Find

Each element points toward a set root; find climbs to the root while halving the path to flatten the tree.

Union-Find tracks disjoint sets as a forest where each node points to a parent.

Every element begins as its own root, and find climbs parent links until it reaches a self-parent.

Path halving — pointing each node at its grandparent during the climb — keeps future finds nearly constant time.

Elements start self-parented.

A root parents itself.

Path halving flattens the tree.

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
  }

  find(x) {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
}

Read the implementation

Connect each part of the code to the concept before you type.

1. Self-parents

Every element starts as its own set root.

this.parent = Array.from({ length: n }, (_, i) => i)

2. Tree ranks

Rank approximates each tree's height for balanced unions.

this.rank = new Array(n).fill(0)

3. Climb to root

A root is the element that parents itself.

while (this.parent[x] !== x) {

4. Path halving

Point each node at its grandparent to flatten the tree.

this.parent[x] = this.parent[this.parent[x]]

A complete learning loop

Understand

Read the concept map and follow the code breakdown.

Reconstruct

Type the implementation, repair mistakes and work through every recall exercise.

Verify

Use the final check without hints; revisit weak concepts in short practice sessions.