Union Find Disjoint Set Data Structure in DSA Javascript

Mental Model

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

Analogy: Imagine groups of friends where each friend knows who their group leader is. When two groups meet, they pick one leader to represent both groups.

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
Each number points to itself as its own leader initially.

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.

Goal: Group elements 0,1,2 together and verify they belong to the same group.

Step 1: union(0,1): find leaders of 0 and 1, both are themselves; connect leader of 1 to leader of 0

0 -> 0
1 -> 0
2 -> 2
3 -> 3
4 -> 4

Why: We merge groups of 0 and 1 by making 0 the leader of 1

Step 2: union(1,2): find leaders of 1 and 2; leader of 1 is 0, leader of 2 is 2; connect leader of 2 to leader of 0

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4

Why: We merge groups of 1 and 2 by making 0 the leader of 2 as well

Step 3: connected(0,2): find leaders of 0 and 2; both are 0; return true

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4

Why: 0 and 2 share the same leader, so they are connected

Result:

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4
connected(0,2) = true

Annotated Code

DSA Javascript

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

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

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

    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;
    }
  }

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

// Driver code
const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
console.log(uf.parent.map((p, i) => `${i} -> ${p}`).join('\n'));
console.log('connected(0,2) =', uf.connected(0, 2));

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

compress path by pointing directly to leader to speed up future finds

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

find leaders of both elements 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, update rank if equal

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

check if two elements share the same leader

Output

0 -> 0

1 -> 0

2 -> 0

3 -> 3

4 -> 4

connected(0,2) = true

Complexity Analysis

Time: O(α(n)) per operation, where α is the inverse Ackermann function, 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: Naive union-find without path compression or rank can degrade to O(n) per operation, much slower on large inputs

Edge Cases

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

No change; find returns same leader; union skips as already connected

DSA Javascript

if (rootX === rootY) return;

union called on elements already connected

No change to structure; union returns early

DSA Javascript

if (rootX === rootY) return;

empty structure (size 0)

No elements to union or find; code handles gracefully by no operations

DSA Javascript

constructor handles size 0 by creating empty arrays

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 and queries sets.

Common Mistakes

Mistake: Not using path compression in find, causing slow repeated searches
Fix: Add path compression by updating parent[x] during find to point directly to leader

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

Summary

It groups elements into sets and quickly checks if two elements are in the same set.

Use it when you need to manage and query connected components or groups efficiently.

The key is to keep trees flat by path compression and union by rank to make operations almost constant time.

Practice

1. What is the main purpose of the Union Find Disjoint Set data structure?

easy

A. To efficiently track and merge groups of connected elements

B. To sort elements in ascending order

C. To store key-value pairs for fast lookup

D. To implement a queue with fast enqueue and dequeue

Solution

1. Step 1: Understand the role of Union Find

   The Union Find data structure helps keep track of which elements belong to the same group or set.

2. Step 2: Identify its main operation

   It supports merging two groups and checking if two elements are in the same group efficiently.

3. Final Answer:

   To efficiently track and merge groups of connected elements -> Option A

4. Quick Check:

   Union Find = Track and merge groups [OK]

Hint: Union Find connects groups, not sorting or key-value storage [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs like a dictionary
• Assuming it works like a queue or stack

2. Which of the following is the correct way to initialize a Union Find parent array for 5 elements in JavaScript?

easy

A. const parent = new Array(5).fill(-1);

B. const parent = [0, 1, 2, 3, 4];

C. const parent = new Array(5).fill(0);

D. const parent = [1, 2, 3, 4, 5];

Solution

1. Step 1: Understand parent array initialization

   Each element is initially its own parent, so parent[i] = i for all i.

2. Step 2: Check each option

   const parent = [0, 1, 2, 3, 4]; correctly sets parent to [0,1,2,3,4]. const parent = new Array(5).fill(0); fills all with 0, wrong. const parent = new Array(5).fill(-1); fills with -1, wrong. const parent = [1, 2, 3, 4, 5]; starts from 1, wrong index.

3. Final Answer:

   const parent = [0, 1, 2, 3, 4]; -> Option B

4. Quick Check:

   Parent array = self indices [OK]

Hint: Parent array starts with each element as its own parent [OK]

Common Mistakes:

• Filling parent array with zeros or -1
• Starting indices from 1 instead of 0
• Not initializing parent array at all

3. Consider the following JavaScript code using Union Find:

const parent = [0, 1, 2, 3, 4];
function find(x) {
  if (parent[x] !== x) {
    parent[x] = find(parent[x]);
  }
  return parent[x];
}
function union(a, b) {
  const rootA = find(a);
  const rootB = find(b);
  if (rootA !== rootB) {
    parent[rootB] = rootA;
  }
}

union(0, 1);
union(1, 2);
console.log(parent);

What will be printed?

medium

A. [0, 0, 0, 3, 4]

B. [0, 1, 2, 3, 4]

C. [1, 1, 1, 3, 4]

D. [0, 0, 1, 3, 4]

Solution

1. Step 1: Perform union(0, 1)

   Find roots: root of 0 is 0, root of 1 is 1. Set parent[1] = 0. Parent becomes [0,0,2,3,4].

2. Step 2: Perform union(1, 2)

   Find roots: root of 1 is find(0) = 0, root of 2 is 2. Set parent[2] = 0. Parent becomes [0,0,0,3,4].

3. Final Answer:

   [0, 0, 0, 3, 4] -> Option A

4. Quick Check:

   Union updates parents to root 0 [OK]

Hint: Union sets parent of one root to the other root [OK]

Common Mistakes:

• Not applying path compression in find
• Confusing which root becomes parent
• Assuming parent array stays unchanged

4. The following code attempts to implement Union Find but has a bug:

const parent = [0, 1, 2, 3];
function find(x) {
  if (parent[x] === x) return x;
  return find(parent[x]);
}
function union(a, b) {
  const rootA = find(a);
  const rootB = find(b);
  if (rootA !== rootB) {
    parent[rootA] = rootB;
  }
}

union(0, 1);
union(1, 2);
console.log(parent);

What is the bug in this code?

medium

A. Union assigns parent[rootA] = rootB instead of parent[rootB] = rootA

B. The find function does not return a value

C. Parent array is not initialized correctly

D. Missing path compression in find function

Solution

1. Step 1: Examine the find function

   The find recurses to the root but lacks path compression: it should set parent[x] = find(parent[x]) before returning when parent[x] !== x.

2. Step 2: Verify other options

   Find returns correctly. Parent is initialized properly as self-references. Union direction (parent[rootA] = rootB) is valid.

3. Final Answer:

   Missing path compression in find function -> Option D

4. Quick Check:

   Path compression: parent[x] = find(parent[x]) [OK]

Hint: Path compression flattens tree: parent[x] = find(parent[x]) [OK]

Common Mistakes:

• Ignoring missing path compression
• Thinking find lacks return statement
• Assuming parent array is wrong when it's correct

5. You have 6 elements (0 to 5) initially in separate sets. After these operations:

union(0, 1);
union(2, 3);
union(4, 5);
union(1, 2);
union(0, 4);

How many distinct sets remain?

hard

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Perform unions step-by-step

   union(0,1) merges sets {0},{1} -> {0,1} union(2,3) merges {2},{3} -> {2,3} union(4,5) merges {4},{5} -> {4,5}

2. Step 2: Continue unions

   union(1,2) merges {0,1} and {2,3} -> {0,1,2,3} union(0,4) merges {0,1,2,3} and {4,5} -> {0,1,2,3,4,5}

3. Step 3: Count distinct sets

   All elements are connected in one set.

4. Final Answer:

   1 -> Option C

5. Quick Check:

   All unions connect all elements [OK]

Hint: Count merges; all connected means one set [OK]

Common Mistakes:

• Counting each union as a new set
• Not merging transitive connections
• Forgetting that union merges sets fully