Why Union Find Disjoint Set Data Structure in DSA Javascript?

The Big Idea

What if you could instantly know if two people belong to the same group without searching through everyone?

The Scenario

Imagine you have many groups of friends, and you want to quickly find out if two people are in the same group or not. Doing this by checking every friend in each group manually is like searching for a needle in a haystack.

The Problem

Manually checking groups means going through each friend one by one. This is slow and tiring, especially when groups change often. Mistakes happen easily, like forgetting who belongs where.

The Solution

The Union Find Disjoint Set helps by keeping track of groups smartly. It quickly tells if two people are connected and can join groups together without checking everyone. It's like having a magic list that updates itself instantly.

Before vs After

✗ Before

function areInSameGroup(personA, personB, groups) {
  for (const group of groups) {
    if (group.includes(personA) && group.includes(personB)) {
      return true;
    }
  }
  return false;
}

✓ After

class UnionFind {
  constructor(size) {
    this.parent = Array(size).fill(0).map((_, i) => i);
  }
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }
  union(a, b) {
    this.parent[this.find(a)] = this.find(b);
  }
  connected(a, b) {
    return this.find(a) === this.find(b);
  }
}

What It Enables

This data structure makes it easy and fast to manage and check connections in large, changing groups.

Real Life Example

Social networks use this to quickly find if two users are connected through friends, even if the network is huge and always changing.

Key Takeaways

Manual group checks are slow and error-prone.

Union Find keeps track of groups efficiently.

It allows quick connection checks and group merges.

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