Union-Find Explained for Coding Interviews

Union-Find (also called Disjoint Set Union or DSU) is a data structure that tracks elements partitioned into non-overlapping sets. It supports two operations in nearly O(1) time: find (which set does this element belong to?) and union (merge two sets). Use it when you need to track connected components, detect cycles in undirected graphs, or group related elements efficiently.

When to Use Union-Find

Union-Find is the right tool when:

• You need to group elements that share a relationship (e.g., accounts with the same email, islands connected by water)
• You need to detect cycles in an undirected graph by checking if two nodes are already connected before adding an edge
• You need to count connected components dynamically as edges are added
• The problem involves transitive relationships (if A connects to B and B connects to C, then A connects to C)

Trigger signals: "connected components," "groups," "merge," "redundant connection," "accounts," or "islands" in the problem statement.

Why not BFS/DFS? BFS and DFS work for static graphs. Union-Find is better when edges are added dynamically and you need to check connectivity after each addition.

The Data Structure

A Union-Find tracks each element's parent and the rank (approximate depth) of each tree. Two optimizations make it nearly O(1) per operation:

Path Compression

When you find the root of an element, make every node along the path point directly to the root. This flattens the tree for future queries.

Union by Rank

When merging two trees, attach the smaller tree under the larger one. This prevents the tree from becoming a linked list.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.components = n

    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        root_x, root_y = self.find(x), self.find(y)
        if root_x == root_y:
            return False
        if self.rank[root_x] < self.rank[root_y]:
            self.parent[root_x] = root_y
        elif self.rank[root_x] > self.rank[root_y]:
            self.parent[root_y] = root_x
        else:
            self.parent[root_y] = root_x
            self.rank[root_x] += 1
        self.components -= 1
        return True

    def connected(self, x, y):
        return self.find(x) == self.find(y)

Time complexity: O(α(n)) per operation, where α is the inverse Ackermann function. In practice, this is effectively O(1) — the function grows so slowly that it never exceeds 4 for any practical input size.

Space: O(n).

Example 1: Number of Islands (Dynamic)

In the classic Number of Islands problem, you have a grid and need to count connected components of land cells. Union-Find handles the dynamic version where land cells are added one at a time.

def num_islands_dynamic(m, n, positions):
    uf = UnionFind(m * n)
    grid = [[0] * n for _ in range(m)]
    result = []
    count = 0

    for r, c in positions:
        if grid[r][c] == 1:
            result.append(count)
            continue

        grid[r][c] = 1
        count += 1
        idx = r * n + c

        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r + dr, c + dc
            if 0 <= nr < m and 0 <= nc < n and grid[nr][nc] == 1:
                if uf.union(idx, nr * n + nc):
                    count -= 1

        result.append(count)

    return result

Walkthrough:

1. Start with all water, count = 0
2. Add (0,0) → count = 1, no neighbors to merge
3. Add (0,1) → count = 2, merge with (0,0) → count = 1
4. Add (1,0) → count = 2, merge with (0,0) → count = 1
5. Add (1,1) → count = 2, merge with (0,1) and (1,0) → count = 1

Time: O(k × α(m×n)) where k = number of positions. Space: O(m×n).

Example 2: Redundant Connection

Given a graph with n nodes and n edges (one extra edge creating a cycle), find the edge that creates the cycle. Union-Find detects it: if both endpoints are already connected before adding the edge, that edge is redundant.

def find_redundant_connection(edges):
    n = len(edges)
    uf = UnionFind(n + 1)

    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]

    return []

Walkthrough with [[1,2],[1,3],[2,3]]:

1. union(1,2) → True (merge successfully)
2. union(1,3) → True (merge successfully)
3. union(2,3) → False (2 and 3 already connected through 1) → return [2,3]

Time: O(n × α(n)). Space: O(n).

Example 3: Accounts Merge

Given a list of accounts where each account has a name and a list of emails, merge accounts that share at least one email. This is a classic Union-Find application: treat each email as a node and union emails that belong to the same account.

from collections import defaultdict

def accounts_merge(accounts):
    email_to_id = {}
    email_to_name = {}
    id_counter = 0

    for account in accounts:
        name = account[0]
        for email in account[1:]:
            email_to_name[email] = name
            if email not in email_to_id:
                email_to_id[email] = id_counter
                id_counter += 1

    uf = UnionFind(id_counter)

    for account in accounts:
        first_email = account[1]
        for email in account[2:]:
            uf.union(email_to_id[first_email], email_to_id[email])

    groups = defaultdict(list)
    for email, eid in email_to_id.items():
        root = uf.find(eid)
        groups[root].append(email)

    return [[email_to_name[emails[0]]] + sorted(emails) for emails in groups.values()]

Walkthrough with [["John","john@m.com","john@n.com"],["John","john@m.com","john@o.com"]]:

1. Map emails to IDs: john@m.com → 0, john@n.com → 1, john@o.com → 2
2. Union account 1: union(0, 1) → merge
3. Union account 2: union(0, 2) → merge (0 is root for both)
4. Group by root: {0: ["john@m.com", "john@n.com", "john@o.com"]}
5. Result: [["John", "john@m.com", "john@n.com", "john@o.com"]]

Time: O(n × k × α(n)) where k = max emails per account. Space: O(n × k).

Complexity Summary

Common Mistakes

1. Not using path compression. Without path compression, find degrades to O(n) in the worst case. Always use both optimizations.

2. Forgetting to check if already connected before union. The union method returns False when elements are already in the same set. Use this return value to detect cycles or redundant edges.

3. 1-indexed vs 0-indexed confusion. Some problems number nodes from 1 to n. Initialize your parent array accordingly: range(n + 1) for 1-indexed, range(n) for 0-indexed.

4. Not decrementing the component count. When you successfully union two sets, the total number of components decreases by 1. Track this if the problem asks for the number of connected components.

5. Using Union-Find for directed graphs. Union-Find works for undirected connectivity. For directed graphs, use DFS/BFS or topological sort.

Practice Problems

These problems cover the core Union-Find patterns. Solve them in order.

1. Number of Provinces — Count connected components in an adjacency matrix. The simplest Union-Find application.

2. Redundant Connection — Find the edge that creates a cycle. Union-Find detects it by checking if two nodes are already connected.

3. Accounts Merge — Group emails by shared ownership. Union emails that belong to the same account.

4. Number of Islands II — Dynamic island counting as land cells are added. Union-Find handles the dynamic connectivity.

5. Accounts Merge II — Variant with additional constraints. Tests your ability to adapt the pattern.

Practice These Patterns With Alex

Union-Find problems test your ability to choose the right data structure and implement it cleanly. The structure itself is simple — the challenge is recognizing when to use it and mapping the problem to union/find operations. Practice with an AI interviewer who asks you to justify your data structure choice.

Start a mock coding interview →

Frequently Asked Questions