Interview Guide: Disjoint Sets Problems and Solutions

Introduction to Disjoint Sets (Union-Find)

Disjoint Set data structure, also known as Union-Find, manages a collection of elements partitioned into disjoint subsets. It supports two primary operations: find to determine which subset an element belongs to, and union to merge two subsets into one. This simple yet powerful structure underpins many graph and connectivity problems.

Core Operations and Optimizations

A typical implementation uses an array parent where parent[i] points to the representative (root) of the set containing i. Initially each element is its own parent. The find operation follows parent pointers until reaching the root. To improve efficiency, two optimizations are essential:

• Path Compression: During find, make each node point directly to the root, flattening the tree.
• Union by Rank/Size: Attach the smaller tree under the larger tree during union, using a rank or size array to guide merging.

Here is a clean Python implementation:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
    
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path compression
        return self.parent[x]
    
    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

The union method returns True if a merge occurred, False if the elements were already in the same set — useful for cycle detection.

Why Disjoint Sets Matter in Coding Interviews

Disjoint Sets appear frequently in technical interviews because they solve graph connectivity problems with near-constant time operations. They are the backbone of:

• Graph connectivity: Counting connected components, checking if two nodes are in the same component.
• Cycle detection: In undirected graphs, adding an edge that connects two nodes already in the same set creates a cycle (e.g., Redundant Connection).
• Kruskal’s Minimum Spanning Tree algorithm: Union-Find efficiently determines if adding an edge forms a cycle.
• Dynamic connectivity: Processing edges online, merging islands or accounts.
• Equivalence relations: Problems like Satisfiability of Equality Equations rely on grouping equal variables.

Mastering the Union-Find pattern lets you convert many medium/hard problems into straightforward implementations, saving time and reducing bugs.

How to Apply Disjoint Sets in Problems

Follow these steps to recognize and apply the pattern:

1. Identify the elements: Determine what the “nodes” are — graph vertices, array indices, email addresses, etc.
2. Define the unions: Which relationships connect two elements? Edges in a graph, shared emails, adjacent cells, equalities in equations.
3. Initialize DSU: Create a UnionFind object with the total number of elements. If elements are not 0-indexed integers, map them first (e.g., strings to indices).
4. Process unions: Iterate through relationships and call union(). Use the return value if you need to detect cycles or count successful merges.
5. Extract results: After all unions, find the root of each element to group them. Use a dictionary or set to collect components.

This template works for a wide range of problems.

Classic Interview Problems and Solutions

Let’s walk through five representative problems, each with a complete solution using the Union-Find structure above.

1. Number of Connected Components in Undirected Graph

Problem: Given n nodes (0 to n-1) and a list of undirected edges, return the number of connected components.

Approach: Initialize DSU with n elements, union all edges, then count distinct roots.

class Solution:
    def countComponents(self, n, edges):
        uf = UnionFind(n)
        for u, v in edges:
            uf.union(u, v)
        roots = set()
        for i in range(n):
            roots.add(uf.find(i))
        return len(roots)

2. Redundant Connection (LeetCode 684)

Problem: Find the edge that creates a cycle in a graph that is a tree plus one extra edge. Return the edge that occurs last in the input if multiple answers exist.

Approach: Process edges in order. The first edge whose union returns False is the redundant one.

class Solution:
    def findRedundantConnection(self, edges):
        # Nodes are 1-indexed, so use size = len(edges) + 1
        uf = UnionFind(len(edges) + 1)
        for u, v in edges:
            if not uf.union(u, v):
                return [u, v]
        return []

3. Accounts Merge (LeetCode 721)

Problem: Given a list of accounts where each account is a name followed by emails, merge accounts that share a common email. Return merged accounts with sorted emails.

Approach: Map each email to the index of the account it first appears in. Union accounts sharing the same email. Group emails by their root account, then sort.

from collections import defaultdict

class Solution:
    def accountsMerge(self, accounts):
        email_to_id = {}
        uf = UnionFind(len(accounts))
        for i, acc in enumerate(accounts):
            for email in acc[1:]:
                if email in email_to_id:
                    uf.union(i, email_to_id[email])
                else:
                    email_to_id[email] = i
        root_to_emails = defaultdict(set)
        for email, idx in email_to_id.items():
            root = uf.find(idx)
            root_to_emails[root].add(email)
        res = []
        for i, emails in root_to_emails.items():
            res.append([accounts[i][0]] + sorted(emails))
        return res

4. Number of Islands (Using Disjoint Sets)

Problem: Given a 2D grid of '1's (land) and '0's (water), count the number of islands (connected groups of '1's).

Approach: Flatten each cell index as i * n + j. Initialize DSU with m * n elements. For each land cell, union with its right and bottom neighbors if they are also land. Keep a counter that decrements on successful union, initially counting all land cells.

class Solution:
    def numIslands(self, grid):
        if not grid:
            return 0
        m, n = len(grid), len(grid[0])
        uf = UnionFind(m * n)
        count = 0
        for i in range(m):
            for j in range(n):
                if grid[i][j] == '1':
                    count += 1
                    idx = i * n + j
                    # Check right and down neighbors
                    for ni, nj in [(i, j+1), (i+1, j)]:
                        if ni < m and nj < n and grid[ni][nj] == '1':
                            if uf.union(idx, ni * n + nj):
                                count -= 1
        return count

5. Satisfiability of Equality Equations (LeetCode 990)

Problem: Given equations like "a==b" or "a!=b", determine if the equations can be satisfied simultaneously.

Approach: First pass: union variables that are equal. Second pass: check inequalities; if any inequality has both variables in the same set, return False.

class Solution:
    def equationsPossible(self, equations):
        uf = UnionFind(26)  # 26 lowercase letters
        for eq in equations:
            if eq[1] == '=':
                x = ord(eq[0]) - ord('a')
                y = ord(eq[3]) - ord('a')
                uf.union(x, y)
        for eq in equations:
            if eq[1] == '!':
                x = ord(eq[0]) - ord('a')
                y = ord(eq[3]) - ord('a')
                if uf.find(x) == uf.find(y):
                    return False
        return True

Best Practices for Interview Success

To maximize your performance with Disjoint Sets, keep these tips in mind:

• Always compress and rank: Never submit a naive implementation without path compression and union by rank/size. Interviewers expect optimized DSU.
• Explain the time complexity: With both optimizations, the amortized time per operation is nearly constant — O(α(n)), where α is the inverse Ackermann function (effectively ≤ 5 for any conceivable input).
• Handle 0-based vs 1-based indexing: Adjust the size of the DSU array accordingly. For nodes numbered 1..n, allocate n+1 elements and ignore index 0.
• Map non-integer elements: If elements are strings (e.g., emails), use a dictionary to map them to integer IDs before initializing the DSU.
• Test edge cases: Empty input, single element, disconnected components, duplicate edges, self-loops. Ensure your code handles these gracefully.
• Use union return value: Leverage the boolean return to detect cycles or count effective unions without extra bookkeeping.
• Consider alternatives: For static graphs, DFS/BFS may be simpler. DSU shines with dynamic connectivity or when processing edges in a specific order (like Kruskal or redundant connection).

Conclusion

Disjoint Sets (Union-Find) is a cornerstone pattern for graph and connectivity problems in coding interviews. By understanding its core operations, optimizations, and common application scenarios, you can turn complex questions into clean, efficient solutions. Practice the template on classic problems like connected components, redundant connection, accounts merge, number of islands, and equality equations. Internalize the best practices, and you'll be ready to demonstrate both clarity and performance under pressure. Good luck!