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

Challenge - 5 Problems

❓ Predict Output

intermediate

Output of find operation with path compression

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

DSA Rust

struct UnionFind {
    parent: Vec<usize>,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        UnionFind { parent: (0..size).collect() }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }

    fn union(&mut self, a: usize, b: usize) {
        let root_a = self.find(a);
        let root_b = self.find(b);
        if root_a != root_b {
            self.parent[root_b] = root_a;
        }
    }
}

fn main() {
    let mut uf = UnionFind::new(5);
    uf.union(0, 1);
    uf.union(1, 2);
    println!("{}", uf.find(2));
    println!("{:?}", uf.parent);
}

A

0
[0, 0, 0, 3, 4]

B

2
[0, 0, 0, 3, 4]

C

0
[0, 1, 1, 3, 4]

D

2
[0, 1, 1, 3, 4]

💡 Hint

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

The find function returns the root of the set. After union(0,1) and union(1,2), the root of 2 is 0. The path compression updates parents of 1 and 2 to 0. So, uf.find(2) returns 0, and the parent array becomes [0, 0, 0, 3, 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 Path compression removes nodes from the tree to reduce memory usage.

B Path compression increases the height of the tree to speed up union operations.

C Path compression flattens the tree, reducing the height and speeding up future find operations.

D Path compression delays the union operation until find is called.

💡 Hint

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

Path compression makes nodes point directly to the root, flattening the tree and reducing its height. This speeds up future find operations.

🔧 Debug

advanced

Identify the error in path compression implementation

What error will the following Rust code cause when calling find with path compression?

DSA Rust

struct UnionFind {
    parent: Vec<usize>,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        UnionFind { parent: (0..size).collect() }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.find(self.parent[x]);
        }
        self.parent[x]
    }
}

fn main() {
    let mut uf = UnionFind::new(3);
    uf.parent[1] = 0;
    println!("{}", uf.find(1));
}

A Runtime panic due to index out of bounds

B Compilation error due to missing return statement

C Correct output 0 with no error

D Stack overflow due to infinite recursion

💡 Hint

Check if the recursive call updates the parent array.

The find function calls itself recursively but does not update the parent[x] with the result. This causes infinite recursion when parent[x] != x, leading to stack overflow.

❓ Predict Output

advanced

Parent array after multiple unions with path compression

What is the parent array after executing the following Rust code?

DSA Rust

struct UnionFind {
    parent: Vec<usize>,
}

impl UnionFind {
    fn new(size: usize) -> Self {
        UnionFind { parent: (0..size).collect() }
    }

    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }

    fn union(&mut self, a: usize, b: usize) {
        let root_a = self.find(a);
        let root_b = self.find(b);
        if root_a != root_b {
            self.parent[root_b] = root_a;
        }
    }
}

fn main() {
    let mut uf = UnionFind::new(6);
    uf.union(0, 1);
    uf.union(1, 2);
    uf.union(3, 4);
    uf.union(4, 5);
    uf.union(2, 5);
    uf.find(5);
    println!("{:?}", uf.parent);
}

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

B [0, 0, 0, 3, 3, 0]

C [0, 0, 0, 0, 3, 3]

D [0, 1, 2, 3, 4, 5]

💡 Hint

Trace unions and remember path compression updates parents during find.

After unions, sets {0,1,2} and {3,4,5} are formed. Then union(2,5) connects these sets with root 0. The find(5) call compresses path, updating parent of 5 to 0. Parent of 4 remains 3 because find(4) was not called. So parent array is [0,0,0,3,3,0].

🧠 Conceptual

expert

Amortized time complexity with path compression

What is the amortized time complexity of find operations in a Union Find data structure with path compression and union by rank?

A O(α(n)) where α is the inverse Ackermann function

B O(n)

C O(1) constant time

D O(log n)

💡 Hint

The inverse Ackermann function grows extremely slowly, almost constant for all practical n.

The combination of path compression and union by rank gives an amortized time complexity of O(α(n)) per find operation, where α(n) is the inverse Ackermann function, which grows very slowly and is practically constant.

Practice

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

easy

A. To merge two sets without checking their roots

B. To speed up future find operations by flattening the tree

C. To delete elements from the Union Find structure

D. To create new sets for each element

Solution

1. Step 1: Understand the role of path compression

   Path compression is used during the find operation to make the tree flatter by pointing nodes directly to the root.

2. Step 2: Effect on future operations

   This flattening reduces the time needed for future find calls, making them faster.

3. Final Answer:

   To speed up future find operations by flattening the tree -> Option B

4. Quick Check:

   Path compression = faster find [OK]

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

Common Mistakes:

• Thinking path compression merges sets
• Confusing path compression with union operation
• Believing it deletes elements

2. Which of the following Rust function signatures correctly represents a find method with path compression in a Union Find struct?

easy

A. fn find(&mut self, x: usize) -> usize

B. fn find(self, x: usize) -> usize

C. fn find(&self, x: usize) -> usize

D. fn find(x: usize) -> usize

Solution

1. Step 1: Identify mutability requirement

   Path compression modifies the parent array, so self must be mutable reference &mut self.

2. Step 2: Check return type and parameters

   The method takes an element index and returns its root as usize.

3. Final Answer:

   fn find(&mut self, x: usize) -> usize -> Option A

4. Quick Check:

   Mutable self needed for path compression [OK]

Hint: Path compression changes state, so use &mut self [OK]

Common Mistakes:

• Using &self which is immutable
• Taking ownership of self
• Missing self parameter

3. Given the following Rust code snippet implementing path compression in Union Find, what will be the output after calling uf.find(3)?

struct UnionFind {
    parent: Vec<usize>,
}

impl UnionFind {
    fn find(&mut self, x: usize) -> usize {
        if self.parent[x] != x {
            self.parent[x] = self.find(self.parent[x]);
        }
        self.parent[x]
    }
}

fn main() {
    let mut uf = UnionFind { parent: vec![0, 0, 1, 2] };
    let root = uf.find(3);
    println!("{}", root);
}

medium

A. 2

B. 3

C. 1

D. 0

Solution

1. Step 1: Trace the parent array before find

   Initial parent: [0, 0, 1, 2]. Element 3 points to 2, 2 points to 1, 1 points to 0.

2. Step 2: Perform find(3) with path compression

   find(3) calls find(2), which calls find(1), which calls find(0). Since 0 is its own parent, root is 0. Path compression sets parent[3] = 0 and parent[2] = 0.

3. Final Answer:

   0 -> Option D

4. Quick Check:

   Root of 3 after compression = 0 [OK]

Hint: Follow parent chain until self-parent, update parents [OK]

Common Mistakes:

• Stopping at immediate parent without recursion
• Not updating parent during compression
• Confusing indices with values

4. Identify the bug in this Rust find method with path compression and select the correct fix:

fn find(&mut self, x: usize) -> usize {
    if self.parent[x] == x {
        self.parent[x] = self.find(self.parent[x]);
    }
    self.parent[x]
}

medium

A. Change == to != in the if condition

B. Remove the recursive call inside if

C. Return self.parent[self.parent[x]] instead

D. Add a loop instead of recursion

Solution

1. Step 1: Analyze the if condition logic

   The condition self.parent[x] == x means x is root, so no recursion needed. The code wrongly recurses when x is root.

2. Step 2: Correct the condition

   It should recurse only if x is not root, so condition must be self.parent[x] != x.

3. Final Answer:

   Change == to != in the if condition -> Option A

4. Quick Check:

   Recurse only if not root [OK]

Hint: Recurse only when parent differs from node [OK]

Common Mistakes:

• Recursing when node is root
• Forgetting base case
• Misusing equality in condition

5. You have a Union Find with 5 elements initialized as parent = [0,1,2,3,4]. After performing unions union(0,1), union(1,2), and union(3,4), what will be the parent array after calling find(2) with path compression if unions always attach the second root to the first root?

hard

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

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

C. [0, 0, 0, 3, 3]

D. [0, 0, 0, 4, 4]

Solution

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

   union(0,1): parent[1] = 0 -> [0,0,2,3,4] union(1,2): find(1)=0, find(2)=2, parent[2] = 0 -> [0,0,0,3,4] union(3,4): parent[4] = 3 -> [0,0,0,3,3]

2. Step 2: Call find(2) with path compression

   find(2) sees parent[2]=0 which is root, no change. Parents remain [0,0,0,3,3].

3. Final Answer:

   [0, 0, 0, 3, 3] -> Option C

4. Quick Check:

   Unions attach second root to first, path compression confirms roots [OK]

Hint: Track unions and compress paths to root [OK]

Common Mistakes:

• Not updating parents during union
• Confusing which root attaches to which
• Ignoring path compression effect