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

Union Find Disjoint Set Data Structure

📖 Scenario: Imagine you are managing groups of friends in a social app. You want to know if two people are in the same friend group or not. You will use a Union Find Disjoint Set data structure to keep track of these groups efficiently.

🎯 Goal: Build a Union Find Disjoint Set data structure in Java that can join two friend groups and check if two people belong to the same group.

📋 What You'll Learn

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

Create an integer array called rank to keep track of the tree height for optimization.

Implement a find method to find the leader of a person's group with path compression.

Implement a union method to join two groups by their leaders using rank.

Check if two people are in the same group using the find method.

💡 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 components.

💼 Career

Understanding Union Find helps in solving problems related to grouping, clustering, and network connectivity efficiently, which is valuable in software engineering and data science roles.

1

Create the parent and rank arrays

Create an integer array called parent of size 5 and initialize it so that each element is its own parent (0 to 4). Also create an integer array called rank of size 5 and initialize all elements to 0.

DSA Java

// Create parent and rank arrays for 5 elements
// Your code here

Hint

Each person starts as their own group leader, so parent[i] = i. The rank array starts with zeros.

2

Write the find method with path compression

Write a method called find that takes an integer x and returns the leader of x's group. Use recursion and path compression by setting parent[x] to the result of find(parent[x]) if x is not its own parent.

DSA Java

int[] parent = new int[5];
int[] rank = new int[5];
for (int i = 0; i < 5; i++) {
    parent[i] = i;
    rank[i] = 0;
}

// Write the find method below
// Your code here

Hint

Use recursion to find the root parent. Update parent[x] to the root to speed up future finds.

3

Write the union method using rank

Write a method called union that takes two integers x and y. Find their leaders using find. If leaders are different, attach the smaller rank tree under the larger rank tree. If ranks are equal, attach y's leader under x's leader and increase rank[x] by 1.

DSA Java

int[] parent = new int[5];
int[] rank = new int[5];
for (int i = 0; i < 5; i++) {
    parent[i] = i;
    rank[i] = 0;
}

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

// Write the union method below
// Your code here

Hint

Compare ranks to decide which root becomes parent. Increase rank if both ranks are equal.

4

Test union and find methods and print results

Use the union method to join groups (0, 1), (1, 2), and (3, 4). Then print find(2) and find(4) to show their group leaders. Finally, print true if find(0) equals find(2) and false if find(0) equals find(4).

DSA Java

int[] parent = new int[5];
int[] rank = new int[5];
for (int i = 0; i  rank[rootY]) {
            parent[rootY] = rootX;
        } else {
            parent[rootY] = rootX;
            rank[rootX]++;
        }
    }
}

// Use union to join groups and print find results
// Your code here

Hint

After unions, 0,1,2 share the same leader. 3 and 4 share another leader. Print leaders and compare equality.

Practice

1. What is the primary purpose of the Union Find Disjoint Set data structure?

easy

A. To efficiently manage and query connected components in a set

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 purpose of Union Find

   The Union Find data structure is designed to keep track of elements partitioned into disjoint sets and quickly find which set an element belongs to.

2. Step 2: Compare with other options

   Sorting, key-value storage, and queue operations are unrelated to Union Find's main goal.

3. Final Answer:

   To efficiently manage and query connected components in a set -> Option A

4. Quick Check:

   Union Find = Manage connected components [OK]

Hint: Union Find tracks groups, not order or key-value pairs [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs like a map
• Assuming it implements queue operations

2. Which of the following is the correct way to initialize a Union Find structure for 5 elements in Java?

easy

A. UnionFind uf = new UnionFind[5];

B. UnionFind uf = new UnionFind(); uf.init(5);

C. UnionFind uf = new UnionFind(5);

D. UnionFind uf = new UnionFind(0, 5);

Solution

1. Step 1: Recognize typical Union Find constructor

   Usually, Union Find is initialized by passing the number of elements to its constructor, like new UnionFind(5).

2. Step 2: Check other options for syntax errors

   UnionFind uf = new UnionFind(); uf.init(5); suggests a separate init method which is uncommon; UnionFind uf = new UnionFind[5]; tries to create an array of UnionFind objects, not a single instance; UnionFind uf = new UnionFind(0, 5); uses two parameters which is not standard.

3. Final Answer:

   UnionFind uf = new UnionFind(5); -> Option C

4. Quick Check:

   Constructor with size parameter = UnionFind uf = new UnionFind(5); [OK]

Hint: Union Find needs size in constructor, no separate init [OK]

Common Mistakes:

• Trying to create an array of UnionFind instead of one instance
• Using multiple parameters in constructor incorrectly
• Assuming an init method is required after construction

3. Consider the following Java code using Union Find:

UnionFind uf = new UnionFind(5);
uf.union(0, 1);
uf.union(1, 2);
boolean connected = uf.connected(0, 2);
System.out.println(connected);

What will be the output?

medium

A. Runtime exception

B. false

C. Compilation error

D. true

Solution

1. Step 1: Trace union operations

   First, 0 and 1 are joined, then 1 and 2 are joined. This means 0, 1, and 2 belong to the same set.

2. Step 2: Check connected query

   Querying if 0 and 2 are connected returns true because they share the same root after unions.

3. Final Answer:

   true -> Option D

4. Quick Check:

   Union chains connect 0 and 2 = true [OK]

Hint: Union chains connect elements; connected returns true [OK]

Common Mistakes:

• Assuming union does not link transitive elements
• Confusing union with overwrite of sets
• Expecting false because 0 and 2 were not directly united

4. The following code snippet has a bug. What is the error?

UnionFind uf = new UnionFind(3);
uf.union(0, 1);
uf.union(1, 2);
System.out.println(uf.connected(0, 3));

medium

A. Index out of bounds error at connected(0, 3)

B. No error, prints false

C. Compilation error due to wrong method call

D. Logical error, should print true

Solution

1. Step 1: Check the size and indices used

   The UnionFind is initialized with size 3, so valid indices are 0, 1, and 2. Index 3 is invalid.

2. Step 2: Identify the error at connected call

   Calling connected(0, 3) accesses an invalid index, causing an index out of bounds error.

3. Final Answer:

   Index out of bounds error at connected(0, 3) -> Option A

4. Quick Check:

   Invalid index access = Index out of bounds error [OK]

Hint: Check indices are within 0 to size-1 [OK]

Common Mistakes:

• Assuming connected returns false for invalid index
• Ignoring array bounds in Union Find
• Thinking compilation error occurs instead of runtime error

5. You have 6 elements (0 to 5). After performing unions: union(0,1), union(2,3), union(4,5), union(1,2), how many distinct sets remain?

hard

A. 3

B. 2

C. 1

D. 4

Solution

1. Step 1: Analyze unions step-by-step

   Initially, sets are {0}, {1}, {2}, {3}, {4}, {5}. - union(0,1) merges {0} and {1} -> {0,1} - union(2,3) merges {2} and {3} -> {2,3} - union(4,5) merges {4} and {5} -> {4,5} - union(1,2) merges sets containing 1 and 2 -> merges {0,1} and {2,3} -> {0,1,2,3}

2. Step 2: Count remaining distinct sets

   After all unions, sets are {0,1,2,3} and {4,5}, so total 2 sets remain.

3. Step 3: Re-examine options

   Options say 3, 2, 1, 4. The correct count is 2.

4. Final Answer:

   2 -> Option B

5. Quick Check:

   Union merges sets, final count = 2 [OK]

Hint: Count sets after unions by merging connected groups [OK]

Common Mistakes:

• Counting unions instead of distinct sets
• Forgetting transitive merges
• Assuming each union reduces sets by one without checking connections