Union Find Disjoint Set Data Structure in DSA Typescript - Build from Scratch

Union Find Disjoint Set Data Structure

📖 Scenario: Imagine you have a group of friends, and you want to know which friends are connected directly or through other friends. We will use a Union Find Disjoint Set data structure to keep track of these friend groups.

🎯 Goal: You will build a simple Union Find Disjoint Set structure in TypeScript to group friends and check if two friends are in the same group.

📋 What You'll Learn

Create an array called parent to represent each friend's parent in the group.

Create a variable called size to store the number of friends.

Write a function called find that finds the root parent of a friend.

Write a function called union that connects two friends' groups.

Print the parent array after some unions to show the groups.

💡 Why This Matters

🌍 Real World

Union Find is used in social networks to find friend groups, in computer networks to find connected devices, and in games to manage connected regions.

💼 Career

Understanding Union Find helps in solving problems related to grouping, connectivity, and network design, which are common in software engineering and data science roles.

1

Create the parent array for 5 friends

Create an array called parent with 5 elements where each element is its own parent (0 to 4).

DSA Typescript

// Your code here

Hint

Each friend starts as their own group, so parent[i] should be i.

2

Write the find function

Write a function called find that takes a number x and returns the root parent of x by following the parent array until parent[x] === x.

DSA Typescript

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

// Write the find function below
// Your code here

Hint

Keep moving up the parent until you find the root where parent[x] equals x.

3

Write the union function

Write a function called union that takes two numbers a and b. Use find to get their root parents. If roots are different, set the parent of b's root to a's root to connect the groups.

DSA Typescript

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

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

// Write the union function below
// Your code here

Hint

Connect the root of one group to the root of the other if they are different.

4

Perform unions and print the parent array

Call union(0, 1), union(1, 2), and union(3, 4). Then print the parent array using console.log(parent).

DSA Typescript

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

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

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

// Perform unions and print the parent array
// Your code here

Hint

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