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

Path Compression in Union Find

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

🎯 Goal: Build a Union Find data structure with path compression to efficiently find the root parent of any user and merge friend groups.

📋 What You'll Learn

Create an array called parent to represent each user's parent in the friend groups

Create a variable called n to represent the total number of users

Write a function called find that uses path compression to find the root parent of a user

Write a function called union to merge two friend groups

Print the parent array after some union operations to show the effect of path compression

💡 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 helps in solving problems related to network connectivity, clustering, and dynamic grouping in software engineering and data science roles.

1

Create the initial parent array

Create a variable called n and set it to 5 to represent 5 users numbered 0 to 4. Then create an array called parent where each user is their own parent initially.

DSA Typescript

const n = 5;
// Your code here

Hint

Each user starts as their own parent, so parent[i] = i for all users.

2

Write the find function with path compression

Write a function called find that takes a user x and returns the root parent of x. Use path compression by setting parent[x] to the root parent during the search.

DSA Typescript

const n = 5;
const parent: number[] = [];
for (let i = 0; i < n; i++) {
    parent[i] = i;
}

function find(x: number): number {
    // Your code here
}

Hint

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

3

Write the union function to merge groups

Write a function called union that takes two users a and b. Find their root parents using find. If they are different, set the parent of b's root to a's root to merge the groups.

DSA Typescript

const n = 5;
const parent: number[] = [];
for (let i = 0; i < n; i++) {
    parent[i] = i;
}

function find(x: number): number {
    if (parent[x] !== x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

function union(a: number, b: number): void {
    // Your code here
}

Hint

Only merge if the roots are different to avoid cycles.

4

Perform unions and print the parent array

Call union(0, 1), union(1, 2), and union(3, 4) to merge some friend groups. Then print the parent array to show the updated parents after path compression.

DSA Typescript

const n = 5;
const parent: number[] = [];
for (let i = 0; i < n; i++) {
    parent[i] = i;
}

function find(x: number): number {
    if (parent[x] !== x) {
        parent[x] = find(parent[x]);
    }
    return parent[x];
}

function union(a: number, b: number): void {
    const rootA = find(a);
    const rootB = find(b);
    if (rootA !== rootB) {
        parent[rootB] = rootA;
    }
}

// Your code here

Hint

After unions, users 0,1,2 share the same root 0, and users 3,4 share root 3.

Practice

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

easy

A. To sort elements inside each set

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

C. To delete elements from the set efficiently

D. To merge two sets without checking their roots

Solution

1. Step 1: Understand the find operation

   The find operation locates the root of an element's set in Union Find.

2. Step 2: Role of path compression

   Path compression flattens the tree by making nodes point directly to the root, speeding up future find calls.

3. Final Answer:

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

4. Quick Check:

   Path compression = faster find [OK]

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

Common Mistakes:

• Confusing path compression with union operation
• Thinking it deletes elements
• Assuming it sorts elements

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

easy

A. function find(x: number): number { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; }

B. function find(x: number): number { while (parent[x] !== x) x = parent[x]; return x; }

C. function find(x: number): number { if (parent[x] === x) return x; else return find(parent[x]); }

D. function find(x: number): number { parent[x] = x; return x; }

Solution

1. Step 1: Identify path compression in code

   Path compression updates parent[x] to root during recursion.

2. Step 2: Check each option

   function find(x: number): number { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } updates parent[x] recursively, implementing path compression correctly.

3. Final Answer:

   function find(x: number): number { if (parent[x] !== x) parent[x] = find(parent[x]); return parent[x]; } -> Option A

4. Quick Check:

   Path compression updates parent[x] recursively [OK]

Hint: Look for recursive parent update in find [OK]

Common Mistakes:

• Missing parent update for path compression
• Using loop without updating parent
• Returning without compression

3. Given the following TypeScript code snippet, what will be the output of console.log(parent) after calling find(3)?

let parent = [0, 0, 1, 2, 4];
function find(x: number): number {
  if (parent[x] !== x) parent[x] = find(parent[x]);
  return parent[x];
}
find(3);
console.log(parent);

medium

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

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

C. [0, 0, 2, 2, 4]

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

Solution

1. Step 1: Trace find(3) calls

   find(3) checks parent[3] = 2, calls find(2). find(2) checks parent[2] = 1, calls find(1). find(1) checks parent[1] = 0, calls find(0). find(0) returns 0 since parent[0] = 0.

2. Step 2: Apply path compression updates

   Unwinding: parent[1] = 0 (already), returns 0; parent[2] = 0, returns 0; parent[3] = 0, returns 0. Final parent = [0, 0, 0, 0, 4].

3. Final Answer:

   [0, 0, 0, 0, 4] -> Option D

4. Quick Check:

   Path compression sets all path nodes to root [OK]

Hint: Follow recursive calls and update parents on return [OK]

Common Mistakes:

• Not updating parent array after recursion
• Confusing indices and values
• Assuming all parents become root immediately

4. Identify the bug in this TypeScript find function implementing path compression:

function find(x: number): number {
  if (parent[x] === x) return x;
  find(parent[x]);
  return parent[x];
}

medium

A. Missing assignment to parent[x] for path compression

B. Incorrect base case condition

C. Function should return void

D. Using recursion without a return statement

Solution

1. Step 1: Analyze recursion and return

   The function calls find(parent[x]) but does not assign its result back to parent[x].

2. Step 2: Identify missing path compression update

   Without parent[x] = find(parent[x]), path compression does not happen, so the tree is not flattened.

3. Final Answer:

   Missing assignment to parent[x] for path compression -> Option A

4. Quick Check:

   Path compression requires updating parent[x] [OK]

Hint: Ensure recursive find result is assigned to parent[x] [OK]

Common Mistakes:

• Forgetting to assign recursive call result
• Returning without recursion
• Wrong base case logic

5. You have a Union Find with parent = [0, 0, 1, 2, 3, 5]. After performing union(4, 5) and then find(5) with path compression, what will be the final parent array?

hard

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

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

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

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

Solution

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

   Initial parent = [0, 0, 1, 2, 3, 5]. Simple union links by setting parent[5] = 4. Now parent = [0, 0, 1, 2, 3, 4].

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

   find(5): parent[5]=4 -> find(4): parent[4]=3 -> find(3)=2 -> find(2)=1 -> find(1)=0 -> find(0)=0.

3. Step 3: Update parent array after compression

   Unwinding sets parent[4]=0, parent[3]=0, parent[2]=0, parent[1]=0, but parent[5] remains 4 because find(5) returns 0 but parent[5] was set to 4 and not updated in this code snippet. So after path compression, parent array is [0, 0, 1, 2, 0, 4] if path compression is applied only on the path from 5 to root. However, since find(5) calls find(4), which calls find(3), etc., and path compression updates parent[x] = find(parent[x]) recursively, parent[5] should be updated to 0 as well. So final parent array is [0, 0, 0, 0, 0, 0].

4. Final Answer:

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

5. Quick Check:

   Union sets and compress path update parents [OK]

Hint: Union sets then compress path to update parents [OK]

Common Mistakes:

• Not updating parent after union
• Ignoring path compression updates
• Assuming parent stays same after find