Union Find Disjoint Set Data Structure in DSA C# - Time & Space Complexity

Time Complexity: Union Find Disjoint Set Data Structure

O(α(n))

Understanding Time Complexity

We want to understand how fast the Union Find data structure works when connecting groups and checking if elements belong to the same group.

How does the time needed change as we add more elements and connections?

Scenario Under Consideration

Analyze the time complexity of the following code snippet.

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;
    }

    public int Find(int x) {
        if (parent[x] != x) parent[x] = Find(parent[x]);
        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;
            else if (rank[rootX] > rank[rootY]) parent[rootY] = rootX;
            else {
                parent[rootY] = rootX;
                rank[rootX]++;
            }
        }
    }
}
    

This code creates a Union Find structure that groups elements and finds their group leaders efficiently using path compression and rank.

Identify Repeating Operations

Identify the loops, recursion, array traversals that repeat.

• Primary operation: The Find method uses recursion with path compression to find the group leader.
• How many times: Each Union or Find call may trigger multiple Find calls, but path compression reduces repeated work over time.

How Execution Grows With Input

As we add more elements, each Find or Union operation takes slightly more time at first, but path compression keeps it very fast.

Input Size (n)	Approx. Operations per Find/Union
10	About 2-3 steps
100	About 4-5 steps
1000	About 6-7 steps

Pattern observation: The number of steps grows very slowly, almost like a flat line, thanks to path compression.

Final Time Complexity

Time Complexity: O(α(n)) per operation, where α(n) is the inverse Ackermann function.

This means each Union or Find runs almost in constant time, even for very large inputs.

Common Mistake

[X] Wrong: "Each Find or Union takes linear time because it might traverse many elements."

[OK] Correct: Path compression and rank keep the trees very flat, so the actual steps per operation are extremely small, not linear.

Interview Connect

Understanding this time complexity shows you know how efficient grouping works behind the scenes, a skill useful in many problems involving connected components or networks.

Self-Check

"What if we removed path compression from Find? How would the time complexity change?"

Practice

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

easy

A. To store key-value pairs for fast lookup

B. To sort elements in ascending order

C. To efficiently track and merge groups of connected elements

D. To implement a queue with priority

Solution

1. Step 1: Understand the role of Union Find

   The Union Find data structure is designed to keep track of which elements belong to which groups or sets, especially when these groups merge over time.

2. Step 2: Compare with other data structures

   Sorting elements or storing key-value pairs are not the main goals of Union Find. It focuses on connectivity and grouping.

3. Final Answer:

   To efficiently track and merge groups of connected elements -> Option C

4. Quick Check:

   Union Find = track and merge groups [OK]

Hint: Union Find tracks connected groups efficiently [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs like a dictionary
• Assuming it manages priority queues

2. Which of the following is the correct syntax to initialize a Union Find structure with 5 elements in C#?

easy

A. UnionFind uf = UnionFind(5);

B. var uf = new UnionFind(5);

C. var uf = UnionFind.New(5);

D. UnionFind uf = new UnionFind[] {5};

Solution

1. Step 1: Recall C# object initialization syntax

   In C#, to create a new object, we use the new keyword followed by the constructor call with parameters.

2. Step 2: Check each option

   var uf = new UnionFind(5); uses correct syntax: var uf = new UnionFind(5);. UnionFind uf = UnionFind(5); misses new. var uf = UnionFind.New(5); uses a non-standard method. UnionFind uf = new UnionFind[] {5}; tries to create an array incorrectly.

3. Final Answer:

   var uf = new UnionFind(5); -> Option B

4. Quick Check:

   Use 'new' keyword for object creation [OK]

Hint: Use 'new' keyword to create objects in C# [OK]

Common Mistakes:

• Omitting the 'new' keyword
• Using array syntax instead of constructor
• Calling non-existent static methods

3. Consider the following C# code using a Union Find structure:

var uf = new UnionFind(5);
uf.Union(0, 1);
uf.Union(1, 2);
bool connected = uf.Connected(0, 2);
Console.WriteLine(connected);

What will be the output?

medium

A. False

B. Runtime exception

C. Compilation error

D. True

Solution

1. Step 1: Analyze the union operations

   First, elements 0 and 1 are united, then 1 and 2 are united. This means 0, 1, and 2 are all connected.

2. Step 2: Check the connectivity query

   The call uf.Connected(0, 2) checks if 0 and 2 are in the same set, which they are after the unions.

3. Final Answer:

   True -> Option D

4. Quick Check:

   Union chains connect 0 and 2 = True [OK]

Hint: Union chains connect elements; check connectivity [OK]

Common Mistakes:

• Assuming only direct unions connect elements
• Confusing union with assignment
• Ignoring transitive connectivity

4. The following code snippet is intended to unite two sets and check if they are connected:

var uf = new UnionFind(3);
uf.Union(0, 1);
uf.Union(1, 3);
Console.WriteLine(uf.Connected(0, 3));

What is the problem with this code?

medium

A. Index 3 is out of range for Union Find of size 3

B. Union method does not exist

C. Connected method returns wrong type

D. No problem, code runs correctly

Solution

1. Step 1: Check Union Find size and indices used

   The Union Find is initialized with size 3, so valid indices are 0, 1, and 2.

2. Step 2: Identify invalid index usage

   The code calls uf.Union(1, 3) and uf.Connected(0, 3), but index 3 is invalid and out of range.

3. Final Answer:

   Index 3 is out of range for Union Find of size 3 -> Option A

4. Quick Check:

   Indices must be within 0 to size-1 [OK]

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

Common Mistakes:

• Using indices equal to size or larger
• Assuming Union Find auto-expands
• Ignoring runtime exceptions from invalid indices

5. You have 6 elements (0 to 5) and perform unions: Union(0,1), Union(2,3), Union(4,5), Union(1,2). How many distinct sets remain?

hard

A. 2

B. 4

C. 3

D. 1

Solution

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

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

2. Step 2: Count remaining distinct sets

   After all unions, only two sets remain: {0,1,2,3} and {4,5}.

3. Final Answer:

   2 -> Option A

4. Quick Check:

   Count sets after unions = 2 [OK]

Hint: Merge sets stepwise; count remaining groups [OK]

Common Mistakes:

• Counting unions instead of sets
• Forgetting transitive merges
• Assuming each union reduces sets by one always