Union Find Disjoint Set Data Structure in DSA Javascript - Interactive Practice

Practice - 5 Tasks

1fill in blank

easy

Complete the code to initialize the parent array where each element is its own parent.

DSA Javascript

class UnionFind {
  constructor(size) {
    this.parent = new Array(size);
    for (let i = 0; i < size; i++) {
      this.parent[i] = [1];
    }
  }
}

Drag options to blanks, or click blank then click option'

Ai

B0

C-1

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning all parents to 0 or null, which merges all elements incorrectly.

Using -1 which is not a valid index here.

Each element starts as its own parent, so we assign i to parent[i].

2fill in blank

medium

Complete the code to find the root parent of an element with path compression.

DSA Javascript

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

Drag options to blanks, or click blank then click option'

Ax

Bthis.find(this.parent[x])

Cthis.parent[x]

Dnull

Attempts:

3 left

💡 Hint

Common Mistakes

Assigning parent[x] to x or parent[x] itself, which breaks path compression.

Returning null or incorrect values.

Path compression sets the parent of x to the root parent found recursively by find.

3fill in blank

hard

Fix the error in the union method to correctly merge two sets by their root parents.

DSA Javascript

union(a, b) {
  let rootA = this.find(a);
  let rootB = this.find(b);
  if (rootA !== rootB) {
    this.parent[[1]] = [2];
  }
}

Drag options to blanks, or click blank then click option'

ArootA

Ba

CrootB

Db

Attempts:

3 left

💡 Hint

Common Mistakes

Using original elements instead of root parents.

Assigning parent of rootB to rootA instead (not wrong but inconsistent).

We set the parent of rootA to rootB to merge the two sets.

4fill in blank

hard

Fill both blanks to check if two elements belong to the same set.

DSA Javascript

connected(a, b) {
  return this.find(a) [1] this.find(b);
}

Drag options to blanks, or click blank then click option'

A===

B!==

C==

D!=

Attempts:

3 left

💡 Hint

Common Mistakes

Using != or !== which checks for inequality.

Using loose equality == which is less precise.

Two elements are connected if their root parents are strictly equal.

5fill in blank

hard

Fill all three blanks to implement union by rank optimization.

DSA Javascript

class UnionFind {
  constructor(size) {
    this.parent = new Array(size);
    this.rank = new Array(size).fill(0);
    for (let i = 0; i < size; i++) {
      this.parent[i] = i;
    }
  }

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

  union(a, b) {
    let rootA = this.find(a);
    let rootB = this.find(b);
    if (rootA !== rootB) {
      if (this.rank[rootA] [1] this.rank[rootB]) {
        this.parent[rootA] = rootB;
      } else if (this.rank[rootA] [2] this.rank[rootB]) {
        this.parent[rootB] = rootA;
      } else {
        this.parent[rootB] = rootA;
        this.rank[rootA] [3] 1;
      }
    }
  }
}

Drag options to blanks, or click blank then click option'

A<

B>

C+=

D==

Attempts:

3 left

💡 Hint

Common Mistakes

Using == instead of < or > for rank comparison.

Not increasing rank when ranks are equal.

Union by rank attaches the smaller tree under the larger one. If ranks are equal, attach and increase rank.

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