Union-Find (Disjoint Set): Connected Components

Union-Find (Disjoint Set): Connected Components

In the competitive world of software engineering, technical interviews often test your grasp of advanced data structures and algorithms. Among these, the Union-Find or Disjoint Set is a versatile and efficient data structure used to solve problems related to partitioning a set into disjoint subsets and finding connected components. Understanding how to implement and optimize this data structure can be the key to acing interview questions, especially those found on platforms like LeetCode.

Prerequisites

Before diving in, you should be familiar with:

• Basic data structures: arrays and linked lists
• Graph concepts: nodes, edges, and connected components
• Algorithm complexity analysis (Big-O notation)

Understanding Union-Find

The Union-Find data structure supports two primary operations efficiently:

1. Union: Connect two elements; effectively grouping them into the same subset.
2. Find: Determine which subset a particular element is in. This can be used to check if two elements are in the same subset.

Real-World Application

Union-Find is commonly used in network connectivity, image processing (finding connected components), and Kruskal's algorithm for finding the Minimum Spanning Tree (MST) of a graph.

Key Operations and Their Implementations

Basic Structure

The Union-Find data structure can be implemented using an array where each index represents an element, and the value at that index is the parent of the element.

class UnionFind:
    def __init__(self, size):
        self.root = list(range(size))

    def find(self, x):
        while x != self.root[x]:
            x = self.root[x]
        return x

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            self.root[rootY] = rootX

class UnionFind {
    constructor(size) {
        this.root = Array.from({ length: size }, (_, index) => index);
    }

    find(x) {
        while (x !== this.root[x]) {
            x = this.root[x];
        }
        return x;
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            this.root[rootY] = rootX;
        }
    }
}

Optimizations: Path Compression and Union by Rank

To enhance the efficiency of Union-Find operations, two crucial optimizations are applied:

1. Path Compression: Flatten the structure of the tree whenever find is called, making nodes point directly to the root.
2. Union by Rank: Attach the smaller tree under the root of the larger tree to keep the tree as flat as possible.

class OptimizedUnionFind:
    def __init__(self, size):
        self.root = list(range(size))
        self.rank = [1] * size

    def find(self, x):
        if x == self.root[x]:
            return x
        self.root[x] = self.find(self.root[x])  # Path compression
        return self.root[x]

    def union(self, x, y):
        rootX = self.find(x)
        rootY = self.find(y)
        if rootX != rootY:
            if self.rank[rootX] > self.rank[rootY]:
                self.root[rootY] = rootX
            elif self.rank[rootX] < self.rank[rootY]:
                self.root[rootX] = rootY
            else:
                self.root[rootY] = rootX
                self.rank[rootX] += 1

class OptimizedUnionFind {
    constructor(size) {
        this.root = Array.from({ length: size }, (_, index) => index);
        this.rank = Array(size).fill(1);
    }

    find(x) {
        if (x === this.root[x]) return x;
        this.root[x] = this.find(this.root[x]);  // Path compression
        return this.root[x];
    }

    union(x, y) {
        const rootX = this.find(x);
        const rootY = this.find(y);
        if (rootX !== rootY) {
            if (this.rank[rootX] > this.rank[rootY]) {
                this.root[rootY] = rootX;
            } else if (this.rank[rootX] < this.rank[rootY]) {
                this.root[rootX] = rootY;
            } else {
                this.root[rootY] = rootX;
                this.rank[rootX] += 1;
            }
        }
    }
}

Complexity

• Time Complexity: Almost constant time, O(α(N)), due to path compression and union by rank, where α is the Inverse Ackermann function.
• Space Complexity: O(N), for storing root and rank arrays.