Union Find Disjoint Set Data Structure in DSA Javascript - Build from Scratch

Union Find Disjoint Set Data Structure

📖 Scenario: Imagine you are managing a social network where people can form friend groups. You want to keep track of which people are in the same friend group efficiently.

🎯 Goal: Build a simple Union Find (Disjoint Set) data structure in JavaScript to group people and check if two people are in the same group.

📋 What You'll Learn

Create an array called parent to represent each person's group leader.

Create a function called find that returns the leader of a person's group.

Create a function called union that merges two groups.

Use the find and union functions to group people and check if two people are connected.

💡 Why This Matters

🌍 Real World

Union Find is used in social networks to find friend groups, in network connectivity to check if computers are connected, and in image processing to find connected regions.

💼 Career

Understanding Union Find helps in solving problems related to grouping, connectivity, and clustering which are common in software engineering interviews and real-world applications.

1

Create the parent array

Create an array called parent with 5 elements where each element is its own index (0 to 4). This means each person is initially their own group leader.

DSA Javascript

// Create the parent array where each person is their own leader
// Your code here

Hint

Each person starts as their own leader, so parent[i] = i.

2

Create the find function

Create a function called find that takes a number x and returns the leader of x's group by following the parent links until the leader is found.

DSA Javascript

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

// Create the find function to find the leader of x
// Your code here

Hint

Keep moving up the parent links until you find a node that is its own parent.

3

Create the union function

Create a function called union that takes two numbers a and b. Use the find function to find their leaders and set the leader of b's group to be the leader of a's group, merging the two groups.

DSA Javascript

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

function find(x) {
    while (parent[x] !== x) {
        x = parent[x];
    }
    return x;
}

// Create the union function to merge groups of a and b
// Your code here

Hint

Find leaders of both groups and set one leader as the parent of the other.

4

Use union and find to group and check connections

Use the union function to merge groups (0, 1) and (1, 2). Then use the find function to check if 0 and 2 have the same leader. Print true if they are connected, otherwise false.

DSA Javascript

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

function find(x) {
    while (parent[x] !== x) {
        x = parent[x];
    }
    return x;
}

function union(a, b) {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA !== rootB) {
        parent[rootB] = rootA;
    }
}

// Use union to merge groups (0,1) and (1,2)
// Then print true if 0 and 2 are connected, else false
// Your code here

Hint

After merging, check if leaders of 0 and 2 are the same and print the result.

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