Path Compression in Union Find in DSA Go

Mental Model

Path compression makes finding the group leader faster by flattening the tree structure during searches.

Analogy: Imagine a family tree where each person points to their parent. Path compression is like updating everyone in the chain to point directly to the oldest ancestor, so next time you find the ancestor quickly.

Before path compression:
1 -> 2 -> 3 -> 4 -> null
After path compression:
1 -> 4 -> null
2 -> 4 -> null
3 -> 4 -> null
4 -> null

Dry Run Walkthrough

Input: Union-Find with elements 1, 2, 3, 4; unions: union(1,2), union(2,3), union(3,4); then find(1)

Goal: Show how path compression flattens the chain when finding the leader of element 1

Step 1: union(1,2) links 1's leader to 2

1 -> 2 -> null
2 -> null
3 -> null
4 -> null

Why: We connect 1 and 2 so they share the same leader

Step 2: union(2,3) links 2's leader to 3

1 -> 2 -> 3 -> null
2 -> 3 -> null
3 -> null
4 -> null

Why: We connect 2 and 3, extending the chain

Step 3: union(3,4) links 3's leader to 4

1 -> 2 -> 3 -> 4 -> null
2 -> 3 -> 4 -> null
3 -> 4 -> null
4 -> null

Why: We connect 3 and 4, chain is now 1->2->3->4

Step 4: find(1) starts, sees 1 points to 2, recursively find leader of 2

1 -> [curr->2] -> 3 -> 4 -> null

Why: We need to find the ultimate leader of 1

Step 5: find(2) sees 2 points to 3, recursively find leader of 3

1 -> 2 -> [curr->3] -> 4 -> null

Why: Continue up the chain to find leader

Step 6: find(3) sees 3 points to 4, recursively find leader of 4

1 -> 2 -> 3 -> [curr->4] -> null

Why: Keep going until leader found

Step 7: find(4) sees 4 points to itself, leader found; path compression updates 3,2,1 to point directly to 4

1 -> 4 -> null
2 -> 4 -> null
3 -> 4 -> null
4 -> null

Why: Flatten the chain so future finds are faster

Result:

1 -> 4 -> null
2 -> 4 -> null
3 -> 4 -> null
4 -> null
Leader of 1 is 4

Annotated Code

DSA Go

package main

import "fmt"

type UnionFind struct {
	parent []int
}

func NewUnionFind(size int) *UnionFind {
	uf := &UnionFind{parent: make([]int, size+1)}
	for i := 1; i <= size; i++ {
		uf.parent[i] = i
	}
	return uf
}

func (uf *UnionFind) Find(x int) int {
	if uf.parent[x] != x {
		uf.parent[x] = uf.Find(uf.parent[x]) // path compression
	}
	return uf.parent[x]
}

func (uf *UnionFind) Union(a, b int) {
	rootA := uf.Find(a)
	rootB := uf.Find(b)
	if rootA != rootB {
		uf.parent[rootA] = rootB
	}
}

func main() {
	uf := NewUnionFind(4)
	uf.Union(1, 2)
	uf.Union(2, 3)
	uf.Union(3, 4)
	leader := uf.Find(1)
	for i := 1; i <= 4; i++ {
		fmt.Printf("%d -> %d\n", i, uf.parent[i])
	}
	fmt.Printf("Leader of 1 is %d\n", leader)
}

if uf.parent[x] != x { uf.parent[x] = uf.Find(uf.parent[x]) // path compression }

recursively find leader and update current node to point directly to leader

rootA := uf.Find(a) rootB := uf.Find(b) if rootA != rootB { uf.parent[rootA] = rootB }

find leaders of both elements and link one leader to the other

Output

1 -> 4

2 -> 4

3 -> 4

4 -> 4

Leader of 1 is 4

Complexity Analysis

Time: O(α(n)) per operation because path compression makes the tree almost flat, where α is the inverse Ackermann function, very slow growing and practically constant

Space: O(n) for storing parent pointers for each element

vs Alternative: Without path compression, find operations can be O(n) in worst case due to long chains; path compression reduces this to almost O(1)

Edge Cases

Find on element that is its own leader

Returns the element itself immediately without recursion

DSA Go

if uf.parent[x] != x {

Union of two elements already in the same set

No change to parent pointers, avoids cycles

DSA Go

if rootA != rootB {

Union-Find with single element

Find returns the element itself; union has no effect

DSA Go

for i := 1; i <= size; i++ { uf.parent[i] = i }

When to Use This Pattern

When you see problems asking to repeatedly merge groups and check if elements are connected, use Union Find with path compression to speed up repeated queries.

Common Mistakes

Mistake: Not updating the parent pointer during find, missing path compression
Fix: Assign uf.parent[x] = uf.Find(uf.parent[x]) inside the find function to flatten the tree

Summary

It speeds up finding the leader of a group by flattening the tree structure during searches.

Use it when you need to efficiently manage and query connected components or groups.

The key insight is updating each node on the path to point directly to the leader, making future searches faster.

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