Path Compression in Union Find in DSA Go - Practice Problems & Challenges

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of Find with Path Compression

What is the output of the following Go code that uses path compression in a Union Find structure?

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 main() {
    parent := []int{0, 1, 2, 3, 4}
    parent[1] = 0
    parent[2] = 1
    parent[3] = 2
    fmt.Println(find(parent, 3))
    fmt.Println(parent)
}

A

0
[0 1 2 0 4]

B

3
[0 1 2 3 4]

C

2
[0 0 1 2 4]

D

0
[0 0 0 0 4]

💡 Hint

Remember that path compression updates the parent of each node visited during find to the root.

The find function recursively finds the root of node 3, which is 0. During this process, it updates the parent of nodes 3, 2, and 1 to 0, compressing the path. So the parent slice becomes [0 0 0 0 4].

🧠 Conceptual

intermediate

Effect of Path Compression on Tree Height

Which statement best describes the effect of path compression in a Union Find data structure?

A It increases the tree height by adding extra parent links.

B It flattens the tree by making nodes point directly to the root, reducing future find times.

C It removes nodes from the tree to reduce size.

D It duplicates nodes to balance the tree.

💡 Hint

Think about how path compression changes the parent links during find.

Path compression makes every node on the find path point directly to the root, flattening the tree and speeding up future find operations.

🔧 Debug

advanced

Identify the Bug in Path Compression Implementation

What error will the following Go code produce when calling find with path compression?

DSA Go

package main
import "fmt"

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

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

A Stack overflow due to infinite recursion

B Index out of range error

C No error, outputs 2

D Compilation error

💡 Hint

Check the parent array for cycles.

The parent array has a cycle between nodes 1 and 2, causing infinite recursion in find and a stack overflow error.

🚀 Application

advanced

Number of Connected Components After Unions

Given the following union operations on 5 elements (0 to 4), how many connected components remain?

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)
    count := 0
    for i := 0; i < 5; i++ {
        if parent[i] == i {
            count++
        }
    }
    fmt.Println(count)
}

A 3

B 4

C 2

D 1

💡 Hint

Count how many nodes are their own parent after unions.

After unions, sets are {0,1,2} and {3,4}. The code counts parents equal to index, which is 2 because parent array is [0 0 0 3 3]. So roots are 0 and 3, count is 2.

❓ Predict Output

expert

Final Parent Array After Multiple Finds with Path Compression

What is the final state of the parent array after running the following Go code?

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 main() {
    parent := []int{0, 1, 2, 3, 4, 5}
    parent[1] = 0
    parent[2] = 1
    parent[3] = 2
    parent[4] = 3
    parent[5] = 4
    _ = find(parent, 5)
    _ = find(parent, 3)
    fmt.Println(parent)
}

A [0 0 0 0 0 0]

B [0 1 1 2 3 4]

C [0 0 1 2 3 4]

D [0 0 0 2 3 4]

💡 Hint

Path compression updates all nodes on the find path to point directly to the root.

Calling find on 5 compresses the path 5->4->3->2->1->0, updating all parents to 0. Then find on 3 also confirms parent[3] = 0. Final parent array is all zeros except for 0 itself.

Practice

1. What is the main purpose of path compression in the Union Find data structure?

easy

A. To speed up the find operation by making nodes point directly to the root

B. To merge two sets by size

C. To initialize the parent array

D. To count the number of connected components

Solution

1. Step 1: Understand the role of path compression

   Path compression is used during the find operation to flatten the tree structure by making nodes point directly to the root.

2. Step 2: Compare with other operations

   Merging sets by size is done in union by size/rank, not path compression. Initialization and counting components are unrelated to path compression.

3. Final Answer:

   To speed up the find operation by making nodes point directly to the root -> Option A

4. Quick Check:

   Path compression optimizes find = To speed up the find operation by making nodes point directly to the root [OK]

Hint: Path compression flattens trees to speed up find [OK]

Common Mistakes:

• Confusing path compression with union by size/rank
• Thinking it initializes the data structure
• Believing it counts components

2. Which of the following is the correct Go syntax for the find function with path compression in Union Find?

easy

A. func find(parent []int, x int) int { for parent[x] != x { x = parent[x] } return x }

B. func find(parent []int, x int) int { parent[x] = x; return x }

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

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

Solution

1. Step 1: Identify path compression in the code

   func find(parent []int, x int) int { if parent[x] != x { parent[x] = find(parent, parent[x]) } return parent[x] } recursively updates parent[x] to the root, which is path compression.

2. Step 2: Check other options for correctness

   func find(parent []int, x int) int { for parent[x] != x { x = parent[x] } return x } uses a loop but no path compression. func find(parent []int, x int) int { if parent[x] == x { return x } else { return find(parent, x) } } calls find without updating parent[x]. func find(parent []int, x int) int { parent[x] = x; return x } wrongly resets parent[x] to itself always.

3. Final Answer:

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

4. Quick Check:

   Recursive update of parent[x] = find(...) = func find(parent []int, x int) int { if parent[x] != x { parent[x] = find(parent, parent[x]) } return parent[x] } [OK]

Hint: Look for recursive parent update for path compression [OK]

Common Mistakes:

• Missing parent update in recursion
• Using loop without compression
• Resetting parent incorrectly

3. What will be the output of the following Go code snippet using Union Find with path compression?

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 main() {
    parent := []int{0, 1, 2, 3, 4}
    parent[1] = 0
    parent[2] = 1
    fmt.Println(find(parent, 2))
    fmt.Println(parent)
}

medium

A. 1
[0 0 1 3 4]

B. 0
[0 0 0 3 4]

C. 2
[0 1 2 3 4]

D. 0
[0 1 0 3 4]

Solution

1. Step 1: Trace the find call for element 2

   find(2) calls find(1), which calls find(0). Since parent[0] = 0, root is 0.

2. Step 2: Apply path compression updates

   parent[2] is updated to 0, parent[1] is updated to 0. Final parent array is [0 0 0 3 4].

3. Final Answer:

   0 [0 0 0 3 4] -> Option B

4. Quick Check:

   Root of 2 is 0 and parent array updated = 0 [0 0 0 3 4] [OK]

Hint: Follow recursion and update parents on return [OK]

Common Mistakes:

• Not updating parent array after find
• Returning intermediate parent instead of root
• Confusing indices in parent array

4. Identify the bug in the following Go code implementing find with path compression:

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

medium

A. The function should not update parent[x] during recursion

B. The base case should check parent[x] != x instead of parent[x] == x

C. The recursive call should be find(parent, parent[x]) instead of find(parent, x)

D. The function should return x always

Solution

1. Step 1: Analyze the recursive call argument

   The recursive call uses find(parent, x), which causes infinite recursion because x does not change.

2. Step 2: Correct the recursive call

   It should call find(parent, parent[x]) to move up the tree towards the root.

3. Final Answer:

   The recursive call should be find(parent, parent[x]) instead of find(parent, x) -> Option C

4. Quick Check:

   Recursive call must move up tree = The recursive call should be find(parent, parent[x]) instead of find(parent, x) [OK]

Hint: Recursive find must use parent[x], not x [OK]

Common Mistakes:

• Calling find with same x causing infinite recursion
• Wrong base case condition
• Not updating parent[x] for compression

5. Given a Union Find structure with parent = [0, 0, 1, 2, 3], what will be the parent array after calling find(parent, 4) with path compression?

hard

A. [0, 0, 0, 0, 0]

B. [0, 0, 1, 2, 0]

C. [0, 1, 1, 2, 3]

D. [0, 0, 1, 3, 4]

Solution

1. Step 1: Trace the find call for element 4

   find(4) calls find(3), find(3) calls find(2), find(2) calls find(1), find(1) calls find(0). Root is 0.

2. Step 2: Apply path compression updates

   During recursion unwind: parent[1] = 0 (already), parent[2] = 0, parent[3] = 0, parent[4] = 0. Final parent array is [0, 0, 0, 0, 0].

3. Final Answer:

   [0, 0, 0, 0, 0] -> Option A

4. Quick Check:

   All nodes on path updated to root 0 = [0, 0, 0, 0, 0] [OK]

Hint: Update only nodes on path to root during find [OK]

Common Mistakes:

• Only updating parent[4] to root
• Failing to compress the full path
• Confusing parent indices