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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Union Find after union operations

What is the printed parent array after performing the union operations shown below?

DSA Typescript

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = Array(size).fill(-1);
  }
  find(x: number): number {
    if (this.parent[x] < 0) return x;
    this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(a: number, b: number): void {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA !== rootB) {
      if (this.parent[rootA] <= this.parent[rootB]) {
        this.parent[rootA] += this.parent[rootB];
        this.parent[rootB] = rootA;
      } else {
        this.parent[rootB] += this.parent[rootA];
        this.parent[rootA] = rootB;
      }
    }
  }
}

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

A [-3, 0, 1, -2, 3]

B [-3, 0, 0, -2, 3]

C [-2, 0, 0, -3, 3]

D [-3, 1, 1, -2, 3]

💡 Hint

Remember that the parent array stores negative sizes for roots and points to root for others.

The union operations merge sets by size. After union(0,1) and union(1,2), the root 0 has size -3 and nodes 1 and 2 point to 0. After union(3,4), root 3 has size -2 and node 4 points to 3.

🧠 Conceptual

intermediate

Number of disjoint sets after unions

Given the following union operations on a Union Find of size 6, how many disjoint sets remain?

DSA Typescript

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

A 4

B 3

C 1

D 2

💡 Hint

Count how many unique roots remain after unions.

Unions merge sets: (0,1) and (2,3) and (4,5) initially create 3 sets. Then union(1,2) merges sets containing 0,1 and 2,3 into one. So total sets become 2.

🔧 Debug

advanced

Identify the error in this Union Find implementation

What error will this code produce when calling uf.union(0, 1)?

DSA Typescript

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = Array(size).fill(-1);
  }
  find(x: number): number {
    if (this.parent[x] < 0) return x;
    return this.find(this.parent[x]);
  }
  union(a: number, b: number): void {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA !== rootB) {
      if (this.parent[rootA] < this.parent[rootB]) {
        this.parent[rootA] += this.parent[rootB];
        this.parent[rootB] = rootA;
      } else {
        this.parent[rootB] += this.parent[rootA];
        this.parent[rootA] = rootB;
      }
    }
  }
}

const uf = new UnionFind(2);
uf.union(0, 1);

A Maximum call stack size exceeded (infinite recursion)

B TypeError: Cannot read property of undefined

C No error, runs correctly

D ReferenceError: uf is not defined

💡 Hint

Check if find method updates parent during path compression.

The find method lacks path compression assignment, so repeated calls cause infinite recursion when parent points to non-root.

❓ Predict Output

advanced

Output of find after unions and path compression

What is the output of the console.log statements after these operations?

DSA Typescript

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = Array(size).fill(-1);
  }
  find(x: number): number {
    if (this.parent[x] < 0) return x;
    this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(a: number, b: number): void {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA !== rootB) {
      if (this.parent[rootA] <= this.parent[rootB]) {
        this.parent[rootA] += this.parent[rootB];
        this.parent[rootB] = rootA;
      } else {
        this.parent[rootB] += this.parent[rootA];
        this.parent[rootA] = rootB;
      }
    }
  }
}

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

A

0
2
[-2, 0, -2, 2]

B

1
3
[-2, 0, -2, 2]

C

0
3
[-2, 0, -2, 2]

D

0
2
[-2, 1, -2, 2]

💡 Hint

Remember find returns root and compresses paths.

After unions, roots are 0 for set {0,1} and 2 for set {2,3}. find(1) returns 0 and updates parent[1] to 0. find(3) returns 2 and updates parent[3] to 2. Parent array reflects sizes and parents.

🧠 Conceptual

expert

Effect of union by size on tree height

Which statement best describes the effect of union by size in a Union Find data structure?

A It does not affect tree height or efficiency; it only tracks the number of unions performed.

B It always attaches the second argument's root under the first argument's root regardless of size.

C It keeps the tree height minimal by always attaching smaller trees under larger ones, improving find efficiency.

D It increases tree height by attaching larger trees under smaller ones, slowing down find operations.

💡 Hint

Think about how attaching smaller trees under larger roots affects depth.

Union by size attaches smaller trees under larger ones to keep trees shallow, which speeds up find operations by reducing path length.

Practice

1. What is the primary 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 data structure's goal

   The Union Find Disjoint Set is designed to keep track of which elements belong to which groups or sets, especially when these groups merge.

2. Step 2: Compare options with the purpose

   Sorting, key-value storage, and queue operations are unrelated to the main function of Union Find, which is about grouping and merging sets.

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 manages connected groups, not sorting or queues [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 TypeScript syntax to initialize a Union Find class with 5 elements?

easy

A. const uf = UnionFind(5);

B. const uf = new UnionFind(5);

C. let uf = new UnionFind[];

D. let uf = UnionFind.new(5);

Solution

1. Step 1: Recall TypeScript class instantiation syntax

   In TypeScript, to create an instance of a class, we use the new keyword followed by the class name and parentheses with arguments.

2. Step 2: Check each option for correct syntax

   const uf = new UnionFind(5); uses new UnionFind(5); which is correct. const uf = UnionFind(5); misses new. let uf = new UnionFind[]; uses incorrect array syntax. let uf = UnionFind.new(5); uses invalid method call syntax.

3. Final Answer:

   const uf = new UnionFind(5); -> Option B

4. Quick Check:

   Use new ClassName(args) to create instance [OK]

Hint: Use 'new' keyword with class name and parentheses [OK]

Common Mistakes:

• Omitting the 'new' keyword
• Using array syntax instead of class instantiation
• Incorrect method call syntax for constructors

3. Consider the following TypeScript code using a Union Find class:

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

What will be the output?

medium

A. true\nfalse

B. false\ntrue

C. true\ntrue

D. false\nfalse

Solution

1. Step 1: Track unions and connections

   Union(0,1) connects 0 and 1. Union(1,2) connects 1 and 2, so 0,1,2 are connected. Union(3,4) connects 3 and 4.

2. Step 2: Check connected queries

   connected(0,2) is true because 0 and 2 are in the same set. connected(0,4) is false because 0 and 4 belong to different sets.

3. Final Answer:

   true false -> Option A

4. Quick Check:

   Connected(0,2) = true, Connected(0,4) = false [OK]

Hint: Track unions step-by-step to check connectivity [OK]

Common Mistakes:

• Assuming all elements are connected initially
• Mixing up union and connected method effects
• Forgetting that union merges sets

4. The following TypeScript code attempts to implement the find method of a Union Find class but has a bug:

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

What is the bug and how to fix it?

medium

A. Incorrect comparison; fix by using '==' instead of '!=='

B. Infinite loop possible; fix by adding a break statement

C. Wrong return type; fix by returning boolean instead of number

D. No path compression; fix by setting parent[x] = find(parent[x]) inside loop

Solution

1. Step 1: Identify missing optimization in find method

   The method correctly finds the root but does not apply path compression, which speeds up future queries by flattening the tree.

2. Step 2: Explain fix with path compression

   To fix, recursively find the root and set parent[x] to the root during traversal, e.g., parent[x] = find(parent[x]).

3. Final Answer:

   No path compression; fix by setting parent[x] = find(parent[x]) inside loop -> Option D

4. Quick Check:

   Path compression improves find by updating parents [OK]

Hint: Add path compression to speed up find method [OK]

Common Mistakes:

• Ignoring path compression optimization
• Adding unnecessary break causing incomplete search
• Changing return type incorrectly
• Using wrong equality operator

5. You have 7 elements (0 to 6) initially disconnected. After these union operations:

uf.union(0, 1);
uf.union(1, 2);
uf.union(3, 4);
uf.union(5, 6);
uf.union(4, 5);
uf.union(2, 6);

How many distinct sets remain?

hard

A. 3

B. 2

C. 1

D. 4

Solution

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

   Union(0,1) connects 0 and 1. Union(1,2) connects 2 to 0,1 group. Union(3,4) connects 3 and 4. Union(5,6) connects 5 and 6. Union(4,5) connects sets {3,4} and {5,6} into one group {3,4,5,6}. Union(2,6) connects {0,1,2} and {3,4,5,6} into one big group {0,1,2,3,4,5,6}.

2. Step 2: Count distinct sets after all unions

   All elements are connected into a single set, so only 1 distinct set remains.

3. Final Answer:

   1 -> Option C

4. Quick Check:

   All unions connect all elements into 1 set [OK]

Hint: Follow unions stepwise to count final distinct sets [OK]

Common Mistakes:

• Counting sets before all unions complete
• Missing that union(2,6) merges two big sets
• Assuming initial sets remain unchanged