Union Find Disjoint Set Data Structure in DSA Javascript - Deep Dive

Overview - Union Find Disjoint Set Data Structure

What is it?

Union Find Disjoint Set is a way to keep track of groups of items that are connected or related. It helps quickly find out if two items belong to the same group and to join two groups together. Imagine you have many separate groups and you want to combine some or check if two items are in the same group. This data structure does that efficiently.

Why it matters

Without Union Find, checking if two items are connected or merging groups would take a lot of time, especially when there are many items. This would slow down programs that need to manage connections, like social networks, computer networks, or grouping problems. Union Find makes these operations fast and simple, saving time and computing power.

Where it fits

Before learning Union Find, you should understand basic data structures like arrays and trees. After this, you can explore graph algorithms, especially those that find connected components or minimum spanning trees, where Union Find is often used.

Mental Model

Core Idea

Union Find keeps track of which items belong together by linking them in groups and quickly finding their group leaders.

Think of it like...

Think of Union Find like a classroom where students form friend circles. Each circle has a leader, and if two circles become friends, their leaders agree to merge the circles. To check if two students are in the same circle, you just check if they share the same leader.

Groups represented as trees:

  1       4
  |       |
  2       5
  |
  3

Each number points to its parent. The root (leader) points to itself.

Operations:
- Find: Follow parents up to the root.
- Union: Connect one root to another.

Build-Up - 7 Steps

1

Foundation

Basic concept of grouping items

Concept: Understanding that items can be grouped and each group has a leader or representative.

Imagine you have 5 items: 1, 2, 3, 4, 5. Initially, each item is alone in its own group. So, 1 is leader of group 1, 2 is leader of group 2, and so on. No connections exist yet.

Result

Five groups: {1}, {2}, {3}, {4}, {5} each with itself as leader.

Knowing that each item starts alone helps us build the structure step-by-step by joining groups later.

2

Foundation

Find operation to identify group leader

Concept: Finding the leader of the group an item belongs to by following parent links.

Each item stores a parent pointer. Initially, each item points to itself. To find the leader of an item, follow the parent pointers until you reach an item that points to itself. That item is the leader.

Result

Find(3) returns 3 because 3 points to itself initially.

Understanding how to find the leader is key to knowing if two items are in the same group.

3

Intermediate

Union operation to merge two groups

Concept: Joining two groups by connecting their leaders so they share the same leader.

To union items 2 and 3, first find their leaders. If different, make one leader point to the other. For example, if leader of 2 is 2 and leader of 3 is 3, set parent of 3 to 2. Now 2 and 3 are in the same group.

Result

Groups: {1}, {2,3}, {4}, {5} with leader 2 for group {2,3}.

Union connects groups efficiently by only changing one pointer, avoiding merging entire lists.

4

Intermediate

Path compression to speed up find

🤔Before reading on: do you think find operation always takes the same time, or can it get faster over time? Commit to your answer.

Concept: Improving find by making every item on the path point directly to the leader, flattening the structure.

When finding the leader of an item, update all items along the path to point directly to the leader. This way, future finds are faster because the path is shorter.

Result

After find(3), parent of 3 points directly to 2, making future finds quicker.

Path compression reduces the time complexity of find operations, making the structure almost flat and very fast.

5

Intermediate

Union by rank to keep trees shallow

🤔Before reading on: do you think always attaching one tree to another without rules is efficient? Commit to yes or no.

Concept: Attaching the smaller tree under the bigger tree to keep the overall tree shallow.

Each leader keeps a rank (approximate tree height). When unioning, attach the tree with smaller rank under the one with bigger rank. If ranks are equal, pick one and increase its rank by one.

Result

Trees remain balanced, preventing long chains and keeping find operations fast.

Union by rank prevents the tree from becoming a long chain, which would slow down find.

6

Advanced

Implementing Union Find in JavaScript

🤔Before reading on: do you think the code for union find is complex or simple? Commit to your answer.

Concept: Writing a complete Union Find class with find, union, path compression, and rank.

class UnionFind { constructor(size) { this.parent = Array(size).fill(0).map((_, i) => i); this.rank = Array(size).fill(0); } find(x) { if (this.parent[x] !== x) { this.parent[x] = this.find(this.parent[x]); // path compression } return this.parent[x]; } union(x, y) { const rootX = this.find(x); const rootY = this.find(y); if (rootX === rootY) return; if (this.rank[rootX] < this.rank[rootY]) { this.parent[rootX] = rootY; } else if (this.rank[rootX] > this.rank[rootY]) { this.parent[rootY] = rootX; } else { this.parent[rootY] = rootX; this.rank[rootX]++; } } } // Example usage: const uf = new UnionFind(5); uf.union(1, 2); uf.union(3, 4); console.log(uf.find(2)); // 1 console.log(uf.find(4)); // 3 uf.union(2, 4); console.log(uf.find(3)); // 1

Result

Output: 1 3 1 Groups merged correctly with fast find operations.

Seeing the full code connects theory to practice and shows how path compression and union by rank work together.

7

Expert

Amortized analysis and real-world performance

🤔Before reading on: do you think each find or union operation always takes constant time? Commit to yes or no.

Concept: Understanding that while single operations may take longer, the average time per operation is almost constant due to optimizations.

The combination of path compression and union by rank makes the amortized time per operation nearly constant, specifically inverse Ackermann function, which grows extremely slowly. This means even millions of operations run very fast in practice.

Result

Union Find can handle huge datasets efficiently, making it practical for real-world problems like network connectivity and clustering.

Knowing the amortized complexity explains why Union Find is preferred in performance-critical applications.

Under the Hood

Union Find stores each item with a parent pointer forming a forest of trees. Each tree represents a group with a root as leader. Find operation follows parent pointers to find the root. Path compression flattens the tree by making nodes point directly to the root during find. Union operation connects two trees by linking one root to another, using rank to keep trees balanced. This structure avoids scanning all items, enabling fast group queries.

Why designed this way?

Originally designed to solve connectivity problems efficiently, Union Find avoids costly searches by using trees and pointers. Path compression and union by rank were added later to optimize performance, reducing worst-case scenarios. Alternatives like storing full lists or matrices were too slow or memory-heavy, so this pointer-based approach balances speed and memory well.

Union Find internal structure:

  [Item] -> [Parent]

  Example:

  1 -> 1 (root)
  2 -> 1
  3 -> 2

  Find(3): 3 -> 2 -> 1 (root)

  After path compression:
  3 -> 1

  Union by rank:
  Attach smaller tree root to bigger tree root to keep shallow trees.

Myth Busters - 4 Common Misconceptions

Quick: Does union operation always merge two groups by making one leader point to the other without any rules? Commit yes or no.

Common Belief: Union just connects one group's leader to another without caring about tree size or rank.

Reality: Union by rank attaches the smaller tree under the bigger tree to keep the structure balanced and operations fast.

Why it matters: Ignoring rank can cause tall trees, making find operations slow and hurting performance on large data.

Quick: Is path compression optional and does not affect performance much? Commit yes or no.

Common Belief: Path compression is a minor tweak and not essential for Union Find efficiency.

Reality: Path compression drastically speeds up find operations by flattening trees, making future finds almost constant time.

Why it matters: Without path compression, find can become slow on deep trees, making Union Find inefficient for many operations.

Quick: Does Union Find store all members of a group explicitly? Commit yes or no.

Common Belief: Union Find keeps a list of all items in each group for easy access.

Reality: Union Find only stores parent pointers and ranks, not full group lists, to save memory and speed up operations.

Why it matters: Expecting full group lists leads to inefficient implementations and misunderstanding of Union Find's design.

Quick: Can Union Find be used to find shortest paths between nodes? Commit yes or no.

Common Belief: Union Find can find shortest paths in a network because it tracks connections.

Reality: Union Find only tells if two items are connected, not the path or distance between them.

Why it matters: Using Union Find for shortest path problems leads to wrong solutions; other algorithms like BFS or Dijkstra are needed.

Expert Zone

1

Union Find's amortized time complexity is almost constant due to the inverse Ackermann function, which is practically constant for all reasonable input sizes.

2

Path compression can be implemented recursively or iteratively, with subtle differences in performance and stack usage.

3

Union by size (attaching smaller set to bigger set) is an alternative to union by rank and can be easier to implement with similar performance.

When NOT to use

Union Find is not suitable when you need to track the actual members of each group or when you need to find paths or distances between nodes. For those cases, use adjacency lists, BFS, DFS, or other graph algorithms.

Production Patterns

Union Find is widely used in Kruskal's algorithm for minimum spanning trees, network connectivity checks, image processing for connected components, and clustering algorithms. It is also used in dynamic connectivity problems where connections are added over time.

Connections

Graph Theory

Union Find is used to manage connected components in graphs.

Understanding Union Find helps grasp how graph connectivity is efficiently maintained and checked.

Database Transactions

Union Find's grouping concept relates to transaction locking and grouping in databases.

Knowing how Union Find groups items can illuminate how databases manage sets of locked resources to avoid conflicts.

Social Networks

Union Find models friend groups and communities by merging connected users.

Seeing Union Find as friend circles helps understand how social networks track and merge communities efficiently.

Common Pitfalls

#1 Not using path compression causes slow find operations on deep trees.

Wrong approach:

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

Correct approach:

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

Root cause:

Forgetting to update parent pointers during find leads to tall trees and slow operations.

#2 Union without rank or size leads to unbalanced trees and slow finds.

Wrong approach:

union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
this.parent[rootY] = rootX;
}

Correct approach:

union(x, y) {
const rootX = this.find(x);
const rootY = this.find(y);
if (this.rank[rootX] < this.rank[rootY]) {
this.parent[rootX] = rootY;
} else if (this.rank[rootX] > this.rank[rootY]) {
this.parent[rootY] = rootX;
} else {
this.parent[rootY] = rootX;
this.rank[rootX]++;
}
}

Root cause:

Ignoring tree size or rank causes deep trees and inefficient operations.

#3 Assuming Union Find can find paths or distances between items.

Wrong approach:

Using Union Find to get shortest path between nodes by tracing parents.

Correct approach:

Use BFS or Dijkstra's algorithm to find shortest paths in graphs.

Root cause:

Misunderstanding Union Find's purpose; it only tracks connectivity, not paths.

Key Takeaways

Union Find Disjoint Set efficiently manages groups of connected items by linking them in trees with leaders.

Find operation locates the group leader by following parent pointers, and path compression flattens the tree for speed.

Union operation merges two groups by connecting their leaders, using rank or size to keep trees balanced.

Together, path compression and union by rank make Union Find operations almost constant time on average.

Union Find is essential for problems involving connectivity but does not provide path or distance information.

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