Union Find Disjoint Set Data Structure in DSA Javascript - Execution Trace

Concept Flow - Union Find Disjoint Set Data Structure

Initialize each element as its own set

↓

Find operation: Find root of element

↓

Union operation: Merge two sets

↓

Update parent pointers

↓

Repeat find/union as needed

↓

Check if two elements are in the same set

Start with each element alone. Use find to get set leaders. Use union to merge sets by updating parents. Repeat to manage groups.

Execution Sample

DSA Javascript

class UnionFind {
  constructor(n) {
    this.parent = Array.from({length: n}, (_, 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);
  }
}

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

Creates 5 sets, unions 0 with 1, then 1 with 2, showing parent array after unions.

Execution Table

Step	Operation	Nodes Involved	Parent Array State	Pointer Changes	Visual State
0	Initialize sets	0,1,2,3,4	[0,1,2,3,4]	Each element points to itself	┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ =0 │ │ =1 │ │ =2 │ │ =3 │ │ =4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ head head head head head
1	Union(0,1)	0,1	[1,1,2,3,4]	parent[find(0)] = find(1) → parent[0] = 1	Step 1: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ =1 │ │ =1 │ │ =2 │ │ =3 │ │ =4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ points→ head head head head
2	Union(1,2)	1,2	[1,2,2,3,4]	parent[find(1)] = find(2) → parent[1] = 2	Step 2: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ =1 │ │ =2 │ │ =2 │ │ =3 │ │ =4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ points→ points→ head head head
3	Find(0)	0	[2,2,2,3,4]	Path compression: parent[0] updated to 2	Step 3: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ =2 │ │ =2 │ │ =2 │ │ =3 │ │ =4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ points→ points→ head head head
4	Find(2)	2	[2,2,2,3,4]	No change, 2 is root	Step 4: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ =2 │ │ =2 │ │ =2 │ │ =3 │ │ =4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ points→ points→ head head head
5	Check if 0 and 2 connected	0,2	[2,2,2,3,4]	find(0) == find(2) → true	Sets connected: 0 and 2 share root 2
6	Union(3,4)	3,4	[2,2,2,4,4]	parent[find(3)] = find(4) → parent[3] = 4	Step 6: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ =2 │ │ =2 │ │ =2 │ │ =4 │ │ =4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ points→ points→ head points→ head
7	Find(3)	3	[2,2,2,4,4]	No change, 4 is root	Step 7: ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ ┌────────┐ │ data:0 │ │ data:1 │ │ data:2 │ │ data:3 │ │ data:4 │ │ parent │ │ parent │ │ parent │ │ parent │ │ parent │ │ =2 │ │ =2 │ │ =2 │ │ =4 │ │ =4 │ └────────┘ └────────┘ └────────┘ └────────┘ └────────┘ points→ points→ head points→ head
8	Check if 0 and 3 connected	0,3	[2,2,2,4,4]	find(0) != find(3) → false	Sets not connected: roots 2 and 4 differ

💡 All unions and finds completed; final parent array shows set leaders.

Variable Tracker

Variable	Start	After Step 1	After Step 2	After Step 3	After Step 4	After Step 6	Final
parent	[0,1,2,3,4]	[1,1,2,3,4]	[1,2,2,3,4]	[2,2,2,3,4]	[2,2,2,3,4]	[2,2,2,4,4]	[2,2,2,4,4]
find(0)	0	1	2	2	2	2	2
find(1)	1	1	2	2	2	2	2
find(2)	2	2	2	2	2	2	2
find(3)	3	3	3	3	3	4	4
find(4)	4	4	4	4	4	4	4

Key Moments - 3 Insights

Why does the parent array change during find(0) at step 3?

Because of path compression, find(0) updates parent[0] to point directly to the root (2), speeding up future finds. See execution_table step 3.

Why do we assign parent of root of one set to root of another in union?

Union merges two sets by making one root point to the other root, effectively combining them. This is shown in steps 1 and 2 where parent pointers change.

Why are some elements' parents not themselves after unions?

Because they belong to a merged set, their parent points to the root of that set, not themselves. For example, after union(0,1), parent[0] = 1 (step 1).

Visual Quiz - 3 Questions

Look at the execution_table at step 3. What is the parent of element 0 after find(0)?

A 0

B 2

C 1

D 3

💡 Hint

Check the 'Pointer Changes' and 'Parent Array State' columns at step 3.

At which step does union(1,2) update the parent array?

A Step 2

B Step 4

C Step 1

D Step 6

💡 Hint

Look for the union operation involving nodes 1 and 2 in the execution_table.

If we call union(2,3) after step 6, what would be the parent of element 3?

A 4

B 3

C 2

D 0

💡 Hint

Union sets root of 2 and root of 3; check parent array updates in previous union steps.

Concept Snapshot

Union Find DS stores elements in sets using parent pointers.
Each element starts as its own parent.
Find(x) returns root parent with path compression.
Union(a,b) merges sets by linking roots.
Efficient for connectivity queries in groups.

Full Transcript

Union Find Disjoint Set Data Structure starts by initializing each element as its own set with parent pointing to itself. The find operation locates the root parent of an element, applying path compression to speed up future queries by updating parent pointers directly to the root. The union operation merges two sets by making the root of one set point to the root of the other, effectively combining them. This process is repeated to manage groups and check connectivity. The parent array changes during unions and finds, reflecting the structure of merged sets. Key moments include understanding path compression during find, why union updates parent pointers, and why some elements' parents differ from themselves after unions. The visual execution traces these changes step-by-step, showing parent array states and pointer updates. This structure is efficient for quickly checking if two elements belong to the same set.

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