Union Find Disjoint Set Data Structure in DSA Java

Mental Model

Union Find keeps track of groups of items and quickly tells if two items are in the same group.

Analogy: Imagine friends in different circles. Union Find helps you quickly find if two friends belong to the same circle or join two circles together.

0 -> 0
1 -> 1
2 -> 2
3 -> 3
4 -> 4
Each number points to itself, meaning each is its own group.

Dry Run Walkthrough

Input: Start with 5 elements (0 to 4), perform union(0,1), union(1,2), check if 0 and 2 are connected

Goal: Group elements 0,1,2 together and verify they belong to the same group

Step 1: union(0,1): connect group of 0 and group of 1

0 -> 0
1 -> 0
2 -> 2
3 -> 3
4 -> 4

Why: We make 1 point to 0 to join their groups

Step 2: union(1,2): connect group of 1 and group of 2

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4

Why: Since 1 points to 0, we make 2 point to 0 to join all three

Step 3: connected(0,2): check if 0 and 2 share the same root

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4

Why: Both 0 and 2 have root 0, so they are connected

Result:

0 -> 0
1 -> 0
2 -> 0
3 -> 3
4 -> 4
connected(0,2) = true

Annotated Code

DSA Java

public class UnionFind {
    private int[] parent;
    private int[] rank;

    public UnionFind(int size) {
        parent = new int[size];
        rank = new int[size];
        for (int i = 0; i < size; i++) {
            parent[i] = i; // each element is its own parent
            rank[i] = 0;   // initial rank is zero
        }
    }

    public int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]); // path compression
        }
        return parent[x];
    }

    public void union(int x, int y) {
        int rootX = find(x);
        int rootY = find(y);
        if (rootX != rootY) {
            if (rank[rootX] < rank[rootY]) {
                parent[rootX] = rootY; // attach smaller tree under bigger
            } else if (rank[rootX] > rank[rootY]) {
                parent[rootY] = rootX;
            } else {
                parent[rootY] = rootX;
                rank[rootX]++; // increase rank if same
            }
        }
    }

    public boolean connected(int x, int y) {
        return find(x) == find(y);
    }

    public static void main(String[] args) {
        UnionFind uf = new UnionFind(5);
        uf.union(0, 1);
        uf.union(1, 2);
        System.out.println("connected(0,2) = " + uf.connected(0, 2));
        System.out.println("connected(0,3) = " + uf.connected(0, 3));
    }
}

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

compress path to root to speed up future finds

int rootX = find(x); int rootY = find(y);

find roots of both elements to check if they belong to different groups

if (rootX != rootY) { ... }

only union if roots differ to avoid cycles

if (rank[rootX] < rank[rootY]) { parent[rootX] = rootY; } else if (rank[rootX] > rank[rootY]) { parent[rootY] = rootX; } else { parent[rootY] = rootX; rank[rootX]++; }

attach smaller tree under bigger tree and update rank if equal

return find(x) == find(y);

check if two elements share the same root

Output

connected(0,2) = true

connected(0,3) = false

Complexity Analysis

Time: O(α(n)) per operation, where α is the inverse Ackermann function, almost constant because path compression and union by rank keep trees flat

Space: O(n) for storing parent and rank arrays for n elements

vs Alternative: Naive union without path compression or rank can degrade to O(n) per operation, much slower for large inputs

Edge Cases

union or find on elements outside valid range

ArrayIndexOutOfBoundsException occurs

DSA Java

No explicit guard; user must ensure valid input

union of two elements already in the same group

No change to structure, no cycles formed

DSA Java

if (rootX != rootY) { ... }

connected check on same element

Returns true immediately

DSA Java

return find(x) == find(y);

When to Use This Pattern

When a problem asks to group items and quickly check if two items are connected or in the same group, use Union Find to efficiently manage these groups.

Common Mistakes

Mistake: Not using path compression in find causes slow queries on large data.
Fix: Add path compression by setting parent[x] = find(parent[x]) during find.

Mistake: Not using union by rank causes tall trees and slow operations.
Fix: Use rank to attach smaller tree under bigger tree to keep trees shallow.

Mistake: Calling union without checking if roots differ causes unnecessary changes.
Fix: Check if roots differ before union to avoid redundant work.

Summary

It groups elements and quickly checks if two elements belong to the same group.

Use it when you need to manage dynamic connectivity between items efficiently.

The key is to keep trees flat using path compression and union by rank for fast operations.

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