Union Find Disjoint Set Data Structure in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Union Find after unions

What is the printed parent array after performing the following union operations on a Union Find structure of size 5 initialized with each element as its own parent?

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

Assume union by rank is NOT used, and union attaches the second element's root to the first element's root.

DSA Go

package main
import "fmt"

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

func union(parent []int, x, y int) {
    rootX := find(parent, x)
    rootY := find(parent, y)
    if rootX != rootY {
        parent[rootY] = rootX
    }
}

func main() {
    parent := []int{0, 1, 2, 3, 4}
    union(parent, 0, 1)
    union(parent, 1, 2)
    union(parent, 3, 4)
    fmt.Println(parent)
}

A [1 1 1 4 4]

B [0 1 2 3 4]

C [0 0 0 3 3]

D [0 0 1 3 3]

💡 Hint

Trace each union step and update parents accordingly.

Initially, each element is its own parent: [0 1 2 3 4]. After union(0,1), parent of 1 becomes 0: [0 0 2 3 4]. After union(1,2), find(1) is 0, so parent of 2 becomes 0: [0 0 0 3 4]. After union(3,4), parent of 4 becomes 3: [0 0 0 3 3].

🧠 Conceptual

intermediate

Number of connected components after unions

Given a Union Find structure of size 6, after performing union operations union(0,1), union(2,3), union(4,5), and union(1,2), how many connected components remain?

A 1

B 3

C 4

D 2

💡 Hint

Count how many groups are merged after each union.

Initially, 6 components: {0}, {1}, {2}, {3}, {4}, {5}. After union(0,1): {0,1}, {2}, {3}, {4}, {5} (5 components). After union(2,3): {0,1}, {2,3}, {4}, {5} (4 components). After union(4,5): {0,1}, {2,3}, {4,5} (3 components). After union(1,2): merges {0,1} and {2,3} into {0,1,2,3}, so components are {0,1,2,3}, {4,5} (2 components).

🔧 Debug

advanced

Find function causes infinite recursion

What is the cause of infinite recursion in the following find function of a Union Find implementation?

DSA Go

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

A The recursive call uses x instead of parent[x], causing infinite recursion.

B The base case is incorrect; it should check if parent[x] != x.

C The function should not be recursive; it should use a loop instead.

D The parent array is not initialized properly.

💡 Hint

Check the argument passed in the recursive call.

The recursive call should be find(parent, parent[x]) to move up the tree. Using find(parent, x) calls the same function with the same argument repeatedly, causing infinite recursion.

❓ Predict Output

advanced

Output after union by rank operations

Given a Union Find structure with rank optimization, what is the parent array after these operations on size 5?

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

Assume initial ranks are zero and union attaches the tree with smaller rank under the one with larger rank, increasing rank if equal.

DSA Go

package main
import "fmt"

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

func union(parent, rank []int, x, y int) {
    rootX := find(parent, x)
    rootY := find(parent, 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]++
        }
    }
}

func main() {
    parent := []int{0, 1, 2, 3, 4}
    rank := []int{0, 0, 0, 0, 0}
    union(parent, rank, 0, 1)
    union(parent, rank, 2, 3)
    union(parent, rank, 1, 2)
    union(parent, rank, 4, 0)
    fmt.Println(parent)
}

A [0 1 2 3 4]

B [0 0 0 2 0]

C [1 1 1 3 1]

D [0 0 2 2 0]

💡 Hint

Track ranks and parents carefully after each union.

After union(0,1): parent[1]=0, rank[0]=1. After union(2,3): parent[3]=2, rank[2]=1. After union(1,2): roots are 0 and 2, ranks equal, parent[2]=0, rank[0]=2. After union(4,0): root4=4, root0=0, rank[4]

🧠 Conceptual

expert

Time complexity of Union Find operations with path compression and union by rank

What is the amortized time complexity of find and union operations in a Union Find data structure that uses both path compression and union by rank for n elements?

A O(α(n)) (inverse Ackermann function)

B O(1) amortized

C O(log n)

D O(n)

💡 Hint

Consider the known theoretical bound for optimized Union Find.

With both path compression and union by rank, the amortized time per operation is almost constant, bounded by the inverse Ackermann function α(n), which grows extremely slowly and is practically constant for all reasonable n.

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