Union-Find Pattern: The Template for Connected Components

TL;DR: Union-Find answers two questions about grouping: are these two items in the same group, and merge these two groups. Both run in nearly constant time once you add two short optimizations. It is the right tool whenever edges arrive over time or queries are interleaved with merges, which is exactly the situation where a fresh BFS or DFS per query becomes too slow. One class of about twenty lines covers connected component counting, cycle detection in undirected graphs, account merging, and the sorting step of Kruskal's minimum spanning tree.

This is the twelfth deep dive in our pattern series (the full map lives in the hub), following topological sort. Union-Find is unusual among interview patterns because it is a data structure rather than a traversal, and because the version you should write is genuinely short. Candidates who have not seen it tend to reach for repeated graph traversals and end up with a solution that is correct and too slow, which is a difficult position to recover from late in an interview.

The tell: how to recognize a union-find problem

Suspect this pattern when the question is about grouping items that are connected:

• "how many connected components / groups / provinces"
• "are a and b connected"
• "detect a cycle in an undirected graph"
• "the redundant edge" or the edge that creates a cycle
• edges are added one at a time, or the question asks for an answer after each query
• items that should be treated as equivalent: merging accounts, equal variables, string equivalence
• "minimum cost to connect everything" (minimum spanning tree)

The strongest single signal is incremental structure. If the graph is fixed and you need to count components once, a plain traversal is simpler. If edges keep arriving, or questions are interleaved with merges, union-find is what the problem is built for.

The one insight the whole pattern rests on

Here is the sentence that is the pattern: each group is a tree, and the root of that tree is the group's name.

Nothing else identifies a group. To ask whether two items are together, walk each one up to its root and compare, which is the find operation. To merge two groups, point one root at the other, which is the union operation. The trees carry no meaning beyond connectivity, so their shape is free to change, and the two optimizations below exploit exactly that freedom.

The second half of the insight is the one candidates undervalue: a union that finds both items already sharing a root tells you this edge closes a cycle. You did not run a separate cycle-detection algorithm, you just noticed that the merge was unnecessary. That observation solves an entire class of problems on its own.

The template

Write it as a small class and reuse it verbatim:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))     # every item starts as its own root
        self.rank = [0] * n              # rough tree height, for merge decisions
        self.count = n                   # number of groups right now

    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path compression
            x = self.parent[x]
        return x

    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False                 # already together: this edge is redundant
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a      # attach smaller under larger
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
        self.count -= 1
        return True

Three details do all the work.

Path compression is the single line inside find that repoints each visited node to its grandparent. Every lookup flattens the part of the tree it touched, so repeated queries get faster on their own. Without it, a long chain makes find take O(n) and the solution times out on large inputs.

Union by rank attaches the shorter tree under the taller one, which stops chains from forming in the first place. Some implementations use size instead of rank; either is fine, and you should say which you chose.

Together these give an amortized cost per operation that is effectively constant. The formal bound is the inverse Ackermann function, which is below 5 for any input that fits in memory. Stating "effectively constant, inverse Ackermann amortized" is the complexity answer interviewers are listening for.

union returning a boolean is not decoration. False means the two items were already connected, so the edge you just tried to add closes a cycle. That return value is the entire solution to Redundant Connection and the acceptance test inside Kruskal's algorithm.

The compass: union-find or BFS/DFS?

Both can count connected components, so interviewers probe whether you chose deliberately.

• The graph is fixed and you need the components once. Use BFS or DFS. It is less code and no less efficient.
• Edges arrive over time, or queries are interleaved with merges. Use union-find. Re-running a traversal after each edge is O(V + E) every time and will not pass.
• You need the first edge that creates a cycle in an undirected graph. Use union-find, because a failed union names that edge directly.
• You need the actual path between two nodes, or distances. Use BFS or DFS. Union-find knows only whether two items are grouped, never how they are linked or how far apart they are.

That last limitation is worth stating unprompted. It shows you understand what the structure discards.

Want the whole family taught in order? The union-find chapter of Grokking the Coding Interview builds from Number of Provinces through Accounts Merge and minimum spanning trees with worked traces and code in six languages, then does the same for all 42 patterns (32 common + 10 advanced).

The escalations interviewers actually reach for

• Number of Provinces: the introduction. Union every connected pair, then read count.
• Number of Connected Components in an Undirected Graph: the same problem with edges given as a list rather than a matrix.
• Redundant Connection: return the first edge whose union returns False. Three lines once the class exists.
• Accounts Merge: union accounts that share an email, then group the emails by root. The work is in mapping strings to indices, which is a common wrapper around this pattern.
• Number of Islands II: land appears one cell at a time and you report the island count after each addition. This is the problem that shows why union-find exists, because the traversal approach repeats itself into a timeout.
• Most Stones Removed with Same Row or Column: union stones sharing a row or column, then the answer is total stones minus the number of groups. A good example of translating a question into grouping.
• Satisfiability of Equality Equations: process all the == constraints first to build the groups, then check every != against them. Order matters, and getting it backwards is the trap.
• Min Cost to Connect All Points: Kruskal's algorithm, which is sort the edges by weight and accept any edge whose union succeeds.

The three mistakes that sink candidates

1. Omitting path compression. The code is correct without it and too slow with large inputs. It is one line inside find, so there is no reason to leave it out.

2. Assigning parents without calling find first. Writing parent[b] = a instead of parent[find(b)] = find(a) links two individual items rather than their groups, which quietly corrupts the structure. Always merge roots, never members.

3. Counting groups by scanning the parent array. Two errors hide here. Counting entries where parent[i] == i works only if you never needed compression, and scanning parent[i] directly instead of find(i) reads stale values. Maintain a count field and decrement it inside a successful union, which is O(1) and always correct.

Practice ladder

In order, each rung adding one wrinkle.

1. Number of Provinces (M): the template and the group count.
2. Number of Connected Components in an Undirected Graph (M): the same idea from an edge list.
3. Redundant Connection (M): a failed union as the answer.
4. Most Stones Removed with Same Row or Column (M): translating the question into a grouping rule.
5. Accounts Merge (M): mapping strings to indices around the structure.
6. Satisfiability of Equality Equations (M): constraint ordering.
7. Min Cost to Connect All Points (M): Kruskal's algorithm on top of union-find.
8. Number of Islands II (H): the incremental case that justifies the pattern.
9. Stretch: Swim in Rising Water (H), unioning cells in elevation order.

Then write the tell in your own words ("I should suspect union-find when ___") and move on. Recognition, not volume, is the skill.

The takeaway

One idea (each group is a tree named by its root), two operations (find walks up, union links roots), two optimizations that make it fast (path compression, union by rank), one return value that doubles as a cycle detector (a union that fails), and one boundary worth stating (union-find knows grouping, never paths or distances). The full map of where this sits among the other 41 patterns is in the complete pattern guide. Next in the series: Trie, where prefixes become a tree and autocomplete becomes a walk.

Go deeper: Grokking the Coding Interview teaches all 42 patterns (32 common + 10 advanced) across 300+ sequenced problems, for a one-time $79 with lifetime access. Short on time? Grokking 75 includes the essential graph problems in its 6-week plan.

FAQs

What is union-find in simple terms? A structure that tracks which items belong to the same group. Each group is stored as a tree, and the root of the tree acts as the group's identifier. find walks up to the root to identify an item's group, and union merges two groups by pointing one root at the other.

What are path compression and union by rank? Two optimizations that keep the trees shallow. Path compression repoints the nodes visited during a find so they sit closer to the root, and union by rank attaches the shorter tree beneath the taller one during a merge. With both, each operation costs effectively constant amortized time.

How does union-find detect a cycle? Before merging two nodes you look up both roots. If they already match, the two nodes were connected already, so the edge you are adding creates a cycle. That is why the union method returns a boolean, and it is the complete solution to Redundant Connection.

When should I use union-find instead of BFS or DFS? When edges arrive incrementally or connectivity queries are interleaved with merges, because re-running a traversal after each change is too slow. For a fixed graph where you count components once, BFS or DFS is simpler. Union-find also cannot give you paths or distances, so use a traversal when the question asks for those.

Is union-find asked at FAANG companies? Yes, most often as Number of Provinces, Redundant Connection, and Accounts Merge in screens, with Number of Islands II appearing as a harder follow-up. It is also the backbone of Kruskal's minimum spanning tree, which shows up when a question asks for the minimum cost to connect a set of points.