Union Find Disjoint Set Data Structure in DSA Javascript - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

What is the output after union operations?

Consider a Union Find structure initialized with 5 elements (0 to 4). After performing union(0, 1), union(1, 2), and union(3, 4), what is the parent array representing the sets?

DSA Javascript

class UnionFind {
  constructor(n) {
    this.parent = Array.from({ length: n }, (_, i) => i);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA !== rootB) {
      this.parent[rootB] = rootA;
    }
  }
}

const uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
console.log(uf.parent);

A [0, 0, 1, 3, 4]

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

C [1, 1, 1, 4, 4]

D [0, 0, 0, 3, 3]

💡 Hint

Remember that union sets the parent of one root to the other root.

After union(0,1), parent of 1 becomes 0. After union(1,2), parent of 2 becomes 0 (since 1's root is 0). After union(3,4), parent of 4 becomes 3. So the parent array is [0,0,0,3,3].

🧠 Conceptual

intermediate

What does the 'find' function return?

In a Union Find data structure, what does the 'find' function return when called with an element?

A The size of the set containing the element

B The immediate parent of the element without path compression

C The root parent representing the set of the element

D The number of elements connected to the element

💡 Hint

Think about what identifies the group an element belongs to.

The 'find' function returns the root parent of the element, which uniquely identifies the set it belongs to.

🔧 Debug

advanced

Why does this union find code cause infinite recursion?

Identify the reason for infinite recursion in this 'find' method of Union Find: class UnionFind { constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); } find(x) { if (this.parent[x] === x) { return x; } return this.find(this.parent[x]); } union(a, b) { const rootA = this.find(a); const rootB = this.find(b); if (rootA !== rootB) { this.parent[rootA] = rootB; } } } const uf = new UnionFind(3); uf.union(0, 1); uf.union(1, 2); console.log(uf.find(0));

A The find method lacks path compression, causing infinite recursion

B The union method sets parent of rootA to rootB, causing a cycle in parent links

C The constructor initializes parent array incorrectly

D The union method does not check if roots are equal before union

💡 Hint

Check how parents are assigned in union.

Setting parent of rootA to rootB without ensuring no cycles can cause a cycle if rootB is already a child of rootA, leading to infinite recursion in find.

🚀 Application

advanced

How many connected components after unions?

Given 7 elements (0 to 6) and unions: union(0,1), union(2,3), union(4,5), union(5,6), how many connected components are there?

A 3

B 2

C 5

D 4

💡 Hint

Count how many groups are formed after unions.

Groups are: {0,1}, {2,3}, {4,5,6}, so total 3 connected components.

❓ Predict Output

expert

What is the output of find with path compression?

Consider this Union Find with path compression: class UnionFind { constructor(n) { this.parent = Array.from({ length: n }, (_, i) => i); } find(x) { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); } return this.parent[x]; } union(a, b) { const rootA = this.find(a); const rootB = this.find(b); if (rootA !== rootB) { this.parent[rootB] = rootA; } } } const uf = new UnionFind(6); uf.union(0, 1); uf.union(1, 2); uf.union(3, 4); uf.union(4, 5); console.log(uf.find(5)); console.log(uf.parent);

A

3
[0, 0, 0, 3, 3, 3]

B

0
[0, 0, 0, 3, 3, 3]

C

0
[0, 0, 0, 3, 3, 0]

D

3
[0, 1, 2, 3, 4, 5]

💡 Hint

Path compression updates parents to root during find.

After unions, sets are {0,1,2} with root 0 and {3,4,5} with root 3. find(5) returns 3's root which is 3, and path compression sets parent of 5 to 3. The parent array is [0, 0, 0, 3, 3, 3].

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