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

Recall & Review

beginner

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

It helps keep track of which elements are in which groups or sets, allowing quick checks if two elements belong to the same group and to merge groups efficiently.

beginner

Explain the 'find' operation in Union Find.

The 'find' operation finds the representative or leader of the group that an element belongs to. This helps identify which set the element is part of.

beginner

What does the 'union' operation do in the Union Find data structure?

The 'union' operation merges two different groups into one, connecting their leaders so they share the same representative.

intermediate

Why is path compression important in Union Find?

Path compression makes future 'find' operations faster by making each node on the path point directly to the group's leader, flattening the structure.

intermediate

What is the role of 'union by rank' or 'union by size'?

It helps keep the tree shallow by always attaching the smaller tree under the bigger one, improving the speed of future operations.

What does the 'find' operation return in a Union Find data structure?

A The parent of the element

B The size of the set

C The leader or representative of the element's set

D The total number of sets

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

What is the main benefit of path compression?

A It reduces the height of trees to speed up future 'find' operations

B It increases the number of sets

C It merges two sets

D It deletes elements from sets

Path compression flattens the tree structure, making future 'find' operations faster.

Which operation merges two sets in Union Find?

A union

B find

C compress

D split

The 'union' operation merges two sets into one.

Why use 'union by rank' or 'union by size'?

A To find the leader faster

B To increase the number of sets

C To delete sets

D To keep trees balanced and shallow

'Union by rank' or 'union by size' keeps the tree balanced to optimize operations.

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

A They belong to different sets

B They belong to the same set

C They are not connected

D They are the leaders themselves

Same leader means both elements are in the same set.

Describe how the Union Find data structure works and why it is useful.

Think about how you keep track of friend groups and check if two friends are connected.

Explain the optimizations 'path compression' and 'union by rank' in Union Find and how they improve performance.

Imagine making your friend groups easier to navigate and merge.

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 manages connected groups fast [OK]

Common Mistakes:

• Confusing Union Find with sorting algorithms
• Thinking it stores key-value pairs
• Mixing it up with queue or stack data structures

2. Which of the following is the correct way to declare a Union Find parent array in Go for 5 elements?

easy

A. parent := make([]int, 5)

B. parent := [5]int{0}

C. parent := []int{5}

D. parent := make(int, 5)

Solution

1. Step 1: Understand Go slice creation

   To create a slice of integers with length 5, use make([]int, 5).

2. Step 2: Check each option

   parent := make([]int, 5) correctly uses make with []int and size 5. parent := [5]int{0} is an array but initializes only first element. parent := []int{5} creates a slice with one element 5, not length 5. parent := make(int, 5) is invalid syntax.

3. Final Answer:

   parent := make([]int, 5) -> Option A

4. Quick Check:

   Go slice with make([]int, 5) = correct [OK]

Hint: Use make([]int, size) to create int slice [OK]

Common Mistakes:

• Using make(int, 5) instead of make([]int, 5)
• Confusing array and slice syntax
• Initializing slice with single element instead of length

3. Consider the following Go code using Union Find:

parent := []int{0, 1, 2, 3, 4}

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

func union(a, b int) {
    rootA := find(a)
    rootB := find(b)
    if rootA != rootB {
        parent[rootB] = rootA
    }
}

union(0, 1)
union(1, 2)
union(3, 4)

fmt.Println(find(2), find(4))

What is the output?

medium

A. 1 3

B. 2 4

C. 0 4

D. 0 3

Solution

1. Step 1: Trace union operations

   union(0,1) merges sets of 0 and 1, so parent[1] = 0. union(1,2) merges sets of 1 and 2, so parent[2] = 0 (since find(1) = 0). union(3,4) merges sets of 3 and 4, so parent[4] = 3.

2. Step 2: Find roots of 2 and 4

   find(2) follows parent[2] = 0, so root is 0. find(4) follows parent[4] = 3, so root is 3.

3. Final Answer:

   0 3 -> Option D

4. Quick Check:

   Roots after unions = 0 and 3 [OK]

Hint: Follow parent links to find root [OK]

Common Mistakes:

• Not applying path compression in find
• Mixing up which root belongs to which element
• Assuming union merges by value instead of root

4. The following Go code for Union Find has a bug. What is the error?

parent := []int{0, 1, 2, 3, 4}

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

func union(a, b int) {
    rootA := find(a)
    rootB := find(b)
    if rootA != rootB {
        parent[rootA] = rootB
    }
}

union(0, 1)
union(1, 2)
fmt.Println(find(2))

medium

A. Incorrect union direction causing unbalanced tree

B. Missing path compression in find function

C. Parent array not initialized properly

D. Using recursion in find causes stack overflow

Solution

1. Step 1: Analyze find function

   The find function recursively finds the root but does not update parent[x] to root, so path compression is missing.

2. Step 2: Understand impact of missing path compression

   Without path compression, the tree can become deep, causing slower future finds. The union logic is correct, and parent array is initialized properly.

3. Final Answer:

   Missing path compression in find function -> Option B

4. Quick Check:

   Path compression missing = bug [OK]

Hint: Add parent[x] = find(parent[x]) in find [OK]

Common Mistakes:

• Thinking union direction is always wrong
• Assuming recursion causes stack overflow here
• Ignoring path compression benefits

5. You have 6 elements (0 to 5) initially separate. After these unions: union(0,1), union(2,3), union(4,5), union(1,2), which of the following pairs are in the same set?

hard

A. 2 and 4

B. 1 and 5

C. 0 and 3

D. 3 and 5

Solution

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

   union(0,1) merges sets {0,1}, union(2,3) merges {2,3}, union(4,5) merges {4,5}, union(1,2) merges sets containing 1 and 2, so {0,1,2,3} become one set.

2. Step 2: Check pairs

   Pair 0 and 3 are in the same set {0,1,2,3}. Pairs 1 and 5, 2 and 4, 3 and 5 are in different sets.

3. Final Answer:

   0 and 3 -> Option C

4. Quick Check:

   Unions merge sets correctly = 0 and 3 same set [OK]

Hint: Merge sets stepwise, check membership [OK]

Common Mistakes:

• Assuming all unions merge all elements
• Mixing sets after union(1,2)
• Confusing pairs in different sets