Why Union Find Disjoint Set Data Structure in DSA Typescript?

The Big Idea

Discover how to instantly know if two things belong together without endless searching!

The Scenario

Imagine you have a group of friends, and you want to quickly find out if two people are in the same friend circle without checking every single connection manually.

The Problem

Manually checking each connection takes a lot of time and is confusing, especially when friend circles grow large and overlap. It's easy to make mistakes and miss connections.

The Solution

The Union Find Disjoint Set Data Structure groups friends into sets and lets you quickly check if two people belong to the same group or join two groups together without checking every connection.

Before vs After

✗ Before

function areFriends(personA, personB, connections) {
  // Check all connections one by one
  for (let connection of connections) {
    if (connection.includes(personA) && connection.includes(personB)) return true;
  }
  return false;
}

✓ After

class UnionFind {
  parent: number[];
  constructor(size: number) {
    this.parent = Array.from({ length: size }, (_, i) => i);
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
    return this.parent[x];
  }
  union(a: number, b: number): void {
    this.parent[this.find(a)] = this.find(b);
  }
  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

What It Enables

It enables fast grouping and checking of connected elements, making complex relationship queries simple and efficient.

Real Life Example

Social networks use it to quickly find if two users are connected through friends or groups without searching the entire network.

Key Takeaways

Manual checking of connections is slow and error-prone.

Union Find groups elements and checks connections efficiently.

It is useful for problems involving grouping and connectivity.