Path Compression in Union Find in DSA Java - Build from Scratch

Path Compression in Union Find

📖 Scenario: Imagine you are managing a social network where people form friend groups. You want to quickly find out if two people are in the same friend group and efficiently merge groups when new friendships form.

🎯 Goal: You will build a Union Find data structure with path compression to efficiently manage friend groups. This will help quickly find the leader (representative) of any group and merge groups when needed.

📋 What You'll Learn

Create an integer array called parent to represent each person's group leader.

Create an integer variable called size to store the number of people.

Write a find method that uses path compression to find the leader of a person.

Write a union method to merge two groups by connecting their leaders.

Print the parent array after some unions to show the compressed paths.

💡 Why This Matters

🌍 Real World

Union Find with path compression is used in social networks to quickly find connected friend groups and merge them efficiently.

💼 Career

Understanding Union Find is important for jobs involving graph algorithms, network connectivity, and optimization problems.

1

Create the parent array for 5 people

Create an integer array called parent of size 5 where each element is initialized to its own index (0 to 4). This means each person is initially their own group leader.

DSA Java

// Create the parent array for 5 people
// Your code here

Hint

Use a for loop from 0 to 4 and set parent[i] = i.

2

Add the find method with path compression

Add a static method called find that takes an integer x and returns the leader of x. Use path compression by setting parent[x] to the result of find(parent[x]) when x is not its own leader.

DSA Java

public class UnionFind {
    static int[] parent = new int[5];

    public static int find(int x) {
        // Your code here
    }

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            parent[i] = i;
        }
    }
}

Hint

Use recursion to find the leader and update parent[x] to compress the path.

3

Add the union method to merge groups

Add a static method called union that takes two integers a and b. Find their leaders using find. If the leaders are different, set the leader of b's group to be the leader of a's group.

DSA Java

public class UnionFind {
    static int[] parent = new int[5];

    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public static void union(int a, int b) {
        // Your code here
    }

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            parent[i] = i;
        }
    }
}

Hint

Use find to get leaders and connect one leader to the other.

4

Perform unions and print the parent array

In the main method, perform union(0, 1), union(1, 2), and union(3, 4). Then print the parent array elements separated by spaces on one line.

DSA Java

public class UnionFind {
    static int[] parent = new int[5];

    public static int find(int x) {
        if (parent[x] != x) {
            parent[x] = find(parent[x]);
        }
        return parent[x];
    }

    public static void union(int a, int b) {
        int rootA = find(a);
        int rootB = find(b);
        if (rootA != rootB) {
            parent[rootB] = rootA;
        }
    }

    public static void main(String[] args) {
        for (int i = 0; i < 5; i++) {
            parent[i] = i;
        }
        // Your code here
    }
}

Hint

Call union three times and then print the leader of each element using find.

Practice

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

easy

A. To merge two sets by size

B. To speed up the find operation by flattening the tree structure

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 make future queries faster by making nodes point directly to the root.

2. Step 2: Identify the effect on the tree structure

   This flattens the tree, reducing the height and speeding up subsequent find calls.

3. Final Answer:

   To speed up the find operation by flattening the tree structure -> Option B

4. Quick Check:

   Path compression = flatten tree for faster find [OK]

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

Common Mistakes:

• Confusing path compression with union by size/rank
• Thinking it merges sets instead of optimizing find
• Assuming it initializes data structures

2. Which of the following is the correct Java method signature for the find function implementing path compression in Union Find?

easy

A. public int find(int x)

B. public void find(int x)

C. public boolean find(int x)

D. public int find()"

Solution

1. Step 1: Understand the return type of find

   The find method returns the representative (root) of the set containing element x, so it returns an integer.

2. Step 2: Check method parameters

   The method must accept the element x as input to find its root.

3. Final Answer:

   public int find(int x) -> Option A

4. Quick Check:

   find returns root index as int [OK]

Hint: find returns int root and takes int parameter [OK]

Common Mistakes:

• Using void return type for find
• Missing parameter for element to find
• Returning boolean instead of int

3. Consider the following Java code snippet implementing path compression in Union Find:

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

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

System.out.println(find(4));
System.out.println(Arrays.toString(parent));

What is the output?

medium

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

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

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

D. 0
[0, 0, 1, 2, 0]

Solution

1. Step 1: Trace find(4) call with path compression

   parent[4]=3 -> find(3); parent[3]=2 -> find(2); parent[2]=1 -> find(1); parent[1]=0 -> find(0)=0 (base); parent[1]=0; parent[2]=0; parent[3]=0; parent[4]=0. Returns 0.

2. Step 2: Update parent array after path compression

   Entire path flattens: parent = [0, 0, 0, 0, 0].

3. Final Answer:

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

4. Quick Check:

   find(4) = 0, all path nodes point to root 0 [OK]

Hint: Path compression flattens entire path to root [OK]

Common Mistakes:

• Thinking only leaf updates (partial compression)
• Expecting no change in parent array
• Misreading recursion depth or base case

4. The following find method is intended to implement path compression but has a bug:

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

What is the bug and how to fix it?

medium

A. Missing path compression assignment; fix by adding parent[x] = find(parent[x]);

B. Incorrect base case; fix by changing parent[x] == x to parent[x] != x

C. Wrong return type; fix by changing return type to void

D. No bug; code is correct

Solution

1. Step 1: Identify missing path compression step

   The method recursively finds the root but does not update parent[x] to root, so no path compression happens.

2. Step 2: Fix by assigning compressed parent

   Adding parent[x] = find(parent[x]); before returning compresses the path.

3. Final Answer:

   Missing path compression assignment; fix by adding parent[x] = find(parent[x]); -> Option A

4. Quick Check:

   Assign parent[x] = find(parent[x]) for compression [OK]

Hint: Always assign parent[x] = find(parent[x]) to compress path [OK]

Common Mistakes:

• Forgetting to update parent[x]
• Changing base case incorrectly
• Returning void instead of int

5. Given a Union Find structure with parent = {0, 0, 1, 2, 4, 5} and rank = {0, 1, 2, 3, 4, 5}, after performing union(4, 5) and then find(5) with path compression, what will be the updated parent array?

hard

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

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

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

D. [0, 0, 1, 2, 5, 5]

Solution

1. Step 1: Perform union(4, 5) by rank

   Ranks: rank[4]=4, rank[5]=5. Since rank[5] > rank[4], parent[4] = 5. But ranks given are increasing, so actually rank[5] is highest, so parent[4] = 5.

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

   find(5) returns 5 (root). Path compression updates parent of 5 to itself (no change). But parent[4] points to 5, so parent array is [0,0,1,2,5,5].

3. Step 3: Check options

   [0, 0, 1, 2, 4, 4] shows parent[5] = 4, which contradicts union by rank. [0, 0, 1, 2, 3, 4] no change. [0, 0, 1, 2, 3, 3] parent[5]=3 incorrect. [0, 0, 1, 2, 5, 5] parent[4]=5 and parent[5]=5 matches expected.

4. Final Answer:

   [0, 0, 1, 2, 5, 5] -> Option D

5. Quick Check:

   Union by rank sets parent of lower rank to higher [OK]

Hint: Union by rank attaches lower rank root to higher rank root [OK]

Common Mistakes:

• Confusing which parent to update in union
• Ignoring rank comparison
• Assuming parent array unchanged after union