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.