Union Find Disjoint Set Data Structure in DSA Java - Cheat Sheet & Quick Revision

Recall & Review

beginner

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

It helps to keep track of elements split into one or more disjoint (non-overlapping) sets and supports two main operations: finding which set an element belongs to, and uniting two sets.

beginner

Explain the 'find' operation in Union Find Disjoint Set.

The 'find' operation returns the representative or parent of the set that an element belongs to. It helps to check if two elements are in the same set by comparing their representatives.

beginner

What does the 'union' operation do in the Union Find Disjoint Set?

The 'union' operation merges two different sets into one by connecting their representatives, so that elements from both sets share the same parent.

intermediate

Why is path compression important in Union Find?

Path compression flattens the structure of the tree during 'find' operations by making each node point directly to the root. This speeds up future 'find' operations by reducing the tree height.

intermediate

What is union by rank or size and why is it used?

Union by rank or size attaches the smaller tree under the root of the larger tree during union operations. This keeps the tree shallow, improving the efficiency of future operations.

What does the 'find' operation return in a Union Find Disjoint Set?

A The representative (parent) of the set containing the element

B The size of the set containing the element

C The total number of sets

D The union of all sets

The 'find' operation returns the representative or parent of the set that the element belongs to.

Which technique helps speed up the 'find' operation by flattening the tree?

A Path compression

B Union by size

C Breadth-first search

D Depth-first search

Path compression makes nodes point directly to the root, flattening the tree and speeding up future 'find' operations.

What is the goal of the 'union' operation?

A To delete a set

B To split a set into two

C To find the size of a set

D To merge two sets into one

The 'union' operation merges two different sets into a single set.

Union by rank or size helps to:

A Delete elements from the set

B Increase the height of the tree

C Keep the tree shallow for efficiency

D Find the representative faster

Union by rank or size attaches smaller trees under larger ones to keep the tree shallow and efficient.

If two elements have the same representative, what does it mean?

A They are the roots of their sets

B They belong to the same set

C They are not connected

D They belong to different sets

Same representative means both elements are in the same set.

Describe how the Union Find Disjoint Set data structure works and its main operations.

Think about how sets are combined and how to check if elements share the same set.

Explain why path compression and union by rank/size improve the efficiency of Union Find.

Consider how the structure of the tree affects the speed of find and union.

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