Union Find Disjoint Set Data Structure in DSA Typescript

Mental Model

Union Find keeps track of groups of items and quickly tells if two items are in the same group.

Analogy: Imagine friend circles where each person belongs to one circle. Union Find helps you join two circles or check if two people are already friends in the same circle.

0 [parent->0]
1 [parent->1]
2 [parent->2]
3 [parent->3]
4 [parent->4]
Each number points to itself, meaning each is its own group.

Dry Run Walkthrough

Input: Start with 5 elements: 0,1,2,3,4 each in their own group. Perform union(0,1), union(1,2), check if 0 and 2 are connected, then union(3,4), check if 0 and 4 are connected.

Goal: Show how groups merge and how to check if two elements belong to the same group.

Step 1: union(0,1): merge groups containing 0 and 1

0 [parent->0]
1 [parent->0]
2 [parent->2]
3 [parent->3]
4 [parent->4]

Why: We link 1's group to 0's group to combine them.

Step 2: union(1,2): merge groups containing 1 and 2

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->4]

Why: Since 1's parent is 0, we link 2's group to 0's group, merging 0,1,2.

Step 3: connected(0,2): check if 0 and 2 share the same parent

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->4]

Why: Both 0 and 2 have parent 0, so they are connected.

Step 4: union(3,4): merge groups containing 3 and 4

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->3]

Why: We link 4's group to 3's group to combine them.

Step 5: connected(0,4): check if 0 and 4 share the same parent

0 [parent->0]
1 [parent->0]
2 [parent->0]
3 [parent->3]
4 [parent->3]

Why: 0's parent is 0, 4's parent is 3, so they are not connected.

Result:

Groups:
0 -> 1 -> 2 (parent 0)
3 -> 4 (parent 3)
0 and 2 connected: true
0 and 4 connected: false

Annotated Code

DSA Typescript

class UnionFind {
  private parent: number[];
  private rank: number[];

  constructor(size: number) {
    this.parent = Array(size).fill(0).map((_, i) => i);
    this.rank = Array(size).fill(0);
  }

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

  union(x: number, y: number): void {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return; // already in same group

    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY; // attach smaller tree under bigger
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX;
    } else {
      this.parent[rootY] = rootX;
      this.rank[rootX] += 1; // increase rank if same
    }
  }

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

// Driver code
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
console.log('0 and 2 connected:', uf.connected(0, 2));
uf.union(3, 4);
console.log('0 and 4 connected:', uf.connected(0, 4));

if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); // path compression }

compress path to root to speed up future finds

const rootX = this.find(x); const rootY = this.find(y); if (rootX === rootY) return;

find roots and skip union if already connected

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] += 1; }

attach smaller tree under bigger to keep tree shallow

return this.find(x) === this.find(y);

check if two elements share the same root

Output

0 and 2 connected: true

0 and 4 connected: false

Complexity Analysis

Time: O(α(n)) per operation, where α is the inverse Ackermann function, which is very slow growing and practically constant, because path compression and union by rank keep trees flat.

Space: O(n) for storing parent and rank arrays for n elements.

vs Alternative: Compared to naive union-find without path compression, this approach is much faster for many operations, reducing near-linear time to almost constant.

Edge Cases

union or connected called with same element (e.g., union(2,2))

No change occurs; element is always connected to itself.

DSA Typescript

if (rootX === rootY) return;

checking connected on elements not yet united

Returns false as they belong to different groups.

DSA Typescript

return this.find(x) === this.find(y);

empty UnionFind with zero elements

No operations possible; code handles size 0 gracefully by empty arrays.

DSA Typescript

constructor(size: number) { this.parent = Array(size).fill(0).map((_, i) => i); }

When to Use This Pattern

When you need to quickly group items and check if two items belong to the same group, use Union Find because it efficiently merges groups and checks connectivity.

Common Mistakes

Mistake: Not using path compression in find, causing slow operations.
Fix: Add path compression by setting parent[x] = find(parent[x]) during find.

Mistake: Not using union by rank or size, causing tall trees and slow find.
Fix: Use rank or size to attach smaller tree under bigger tree during union.

Mistake: Forgetting to check if roots are same before union, causing unnecessary changes.
Fix: Check if rootX === rootY before union and skip if true.

Summary

It keeps track of groups of elements and quickly merges or checks if two elements are in the same group.

Use it when you need to manage dynamic connectivity or grouping problems efficiently.

The key is to keep trees flat using path compression and union by rank for fast operations.