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.