Home / Blog / Union-Find Interview Pattern: When and How

Union-Find Interview Pattern: When and How

Published 2026-10-09 · Luna Interview

Union-Find (Disjoint Set Union, DSU) is the pattern for “are these in the same group?” and “merge groups as edges arrive.” If you recognize the union find interview pattern early, you avoid reinventing connectivity with repeated BFS. If you force it where a single graph traversal is enough, you look clever for no gain.

This guide covers when to reach for DSU, a battle-tested Python template, talk tracks, and the bugs that flip answers silently.

The 10-second classification

Ask:

1. Do elements start in separate groups and merge over time (online edges, friendships, accounts)?
2. Do you need many same-component? queries interleaved with merges?
3. Is the graph undirected connectivity (or can you model it that way)?
4. Would one DFS/BFS on the final graph already answer everything offline?

Talk track:

“I’ll use Union-Find when connections arrive online and I need fast merge + same-set checks. If the full edge list is known and I only need components once, DFS or BFS is fine.”

When Union-Find shines

Candidates commonly report DSU in medium graph rounds and in “merge similar items” hashing problems. Keep company talk high-level: practice the pattern, do not invent private question banks.

When DSU is the wrong chooser

• Shortest path → BFS / Dijkstra
• Directed reachability with edges only going one way → usually DFS/BFS or topo, not classic DSU
• Need the actual path, not just connectivity → parent pointers in BFS
• Fully static graph, one connectivity query → DFS is enough and easier to explain
• Weighted constraints beyond “connected or not” → other structures

Minimal template (path compression + union by rank)

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

    def find(self, x: int) -> int:
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]  # path halving
            x = self.parent[x]
        return x

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False  # already same set
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        return True

    def connected(self, a: int, b: int) -> bool:
        return self.find(a) == self.find(b)

Narrate:

“find with path compression keeps trees flat. union by rank avoids skinny chains. union returns False when the edge would form a cycle in an undirected sense.”

Recursive find with compression is also fine if you state the recursion depth is fine after compression in practice, or use the iterative form under pressure.

Pattern: count components

def count_components(n, edges):
    dsu = DSU(n)
    for u, v in edges:
        dsu.union(u, v)
    return dsu.components

Alternative: after all unions, len({dsu.find(i) for i in range(n)}). Maintaining components is cleaner for “earliest time connected” problems.

Pattern: detect redundant undirected edge

def find_redundant(edges):
    dsu = DSU(len(edges) + 1)  # adjust indexing to problem
    for u, v in edges:
        if not dsu.union(u, v):
            return [u, v]
    return []

Talk track:

“If two endpoints already share a root, this undirected edge closes a cycle—that’s the redundant one.”

Confirm 0-based vs 1-based nodes before sizing the DSU.

Mapping arbitrary labels to ids

Emails, strings, or sparse ids: map to 0..n-1 first.

id_of = {}
def idx(x):
    if x not in id_of:
        id_of[x] = len(id_of)
    return id_of[x]

Then size DSU after you know n, or use a dict-based parent structure. Interviewers care that you did not assume dense 0..n-1 without checking.

Complexity to say out loud

Almost O(α(n)) per operation with path compression + union by rank—practically constant. Saying “nearly O(1) amortized per find/union” is enough. Build from m edges is ~O(m α(n)).

Common bugs

• Forgetting to find before comparing parents (parent[a] == parent[b] without find is wrong)
• Union without rank/size → still correct but mention you accept skewed trees, or add rank
• Off-by-one n when nodes are 1-indexed
• Using DSU on directed “who reports to whom” as if it were undirected
• Decreasing components even when union was a no-op
• Mutating structures while iterating roots incorrectly

First five minutes

1. Name the elements and the merge rule
2. Decide 0-based size or dict parents
3. Write find + union; state cycle meaning of False
4. Sketch how the answer is derived (count roots, last failing edge, earliest timestamp)
5. Dry-run a 3-node triangle: third edge should fail union

Soft practice note

Union-Find is a composure pattern: the code is short, the classification is the interview. If you want calm timed practice narrating “online merge vs one DFS,” Luna Interview supports structured rehearsal under pressure without turning practice into anything that violates interview rules.

Day-of checklist

• [ ] Online merges / many connectivity checks confirmed
• [ ] find before every comparison
• [ ] Path compression + union by rank (or size)
• [ ] Indexing (0 vs 1) checked
• [ ] components only decrements on real merges
• [ ] Dry-ran a cycle edge returning False

Reach for Union-Find when groups merge over time. If the graph is static and you need one pass, a DFS may be the clearer answer—and saying that is a strength.

Rehearse with an AI interview copilot, then browse commonly reported interview questions.