Union Find
- Implement Union Find with path compression and union by rank, and explain why find modifies the parent array without changing component membership
- Detect cycles in undirected graphs by checking whether both endpoints already share a component representative before adding the edge
- Solve entity grouping problems using the three-phase pattern: scan for shared attributes and union, group by root, format output
- Choose between Union Find and DFS/BFS based on whether the problem needs repeated connectivity queries on a changing graph or path information
Union Find tracks which elements belong to the same component and answers connectivity queries after incremental merges. Each merge and each query runs in effectively O(1) amortized time with both optimizations applied. The implementation is 15 lines of code. The difficulty is recognizing which problems reduce to merge and query operations on disjoint sets.
What Union Find Actually Does
Without Union Find, answering "are A and B connected?" requires a full DFS or BFS traversal from A. If you add edges one at a time and need the connectivity answer after each addition, you must re-traverse after every edge. With n edges and n queries, the total cost is O(n * (V + E)).
Union Find (also called Disjoint Set Union, or DSU) eliminates that repeated traversal. It maintains a partition of elements into non-overlapping sets. Each set has a representative (root) that identifies the set. Two elements are in the same set if and only if they have the same root. Adding an edge is a union operation. Checking connectivity is a find-and-compare operation. Both run in amortized O(1) with path compression and union by rank.
Union Find: Build a Forest
Five isolated nodes. Each node is its own root: parent[i] = i. Five components.
This is the initial state. Every element starts in its own set.
The data structure is a parent array. Each element points to its parent. The root of a set points to itself: parent[root] = root. To find which set an element belongs to, follow parent pointers until you reach the root.
Initially, every element is its own set: parent[i] = i for all i. This means n elements start in n separate singleton sets.
Without optimizations, this naive version can degenerate to O(n) per operation. If you always attach the second root under the first, you can build a chain: 0 ← 1 ← 2 ← ... ← n-1. Finding the root of element n-1 requires walking n-1 steps. The two optimizations, path compression and union by rank, prevent this degeneration.
How Components Are Tracked
Union Find maintains a forest of trees. Each tree is one component. The root of each tree is the component representative. Two elements are connected if and only if their trees share the same root.
find(x) follows parent pointers from x until it reaches a node whose parent is itself. That node is the root, and the root identifies the component. union(a, b) finds the roots of a and b, then attaches one root under the other. Every node that was reachable from either root is now reachable from the surviving root. connected(a, b) calls find on both and compares the results.
The Union Find Invariant
Every element can reach exactly one root by following parent pointers. That root identifies the component. Two elements are in the same component if and only if they reach the same root.
This invariant constrains every operation in the data structure.
Union must operate on roots. If you write parent[a] = b instead of parent[find(a)] = find(b), you redirect a non-root node. Other nodes that previously reached the correct root through a now lose their path. The tree breaks, and find returns the wrong representative for those nodes.
The component count only changes on actual merges. If find(a) == find(b), the two elements are already in the same component. No merge happens, and decrementing the count would undercount the true number of components. The union method must check whether the roots differ before decrementing.
Find must return the root, not just any ancestor. The root is the canonical representative. Two nodes might share a common ancestor that is not the root, but that does not mean they are in the same component. Only the root comparison is valid.
First Walkthrough
Start with 5 nodes (0 through 4), each in its own component. Process edges one at a time and track the parent array and component count after each operation.
| Operation | Parent Array | Components | What Changed |
|---|---|---|---|
| Initial state | [0, 1, 2, 3, 4] | 5 | Every node is its own root |
| union(0, 1) | [0, 0, 2, 3, 4] | 4 | Node 1's root attached under node 0 |
| union(2, 3) | [0, 0, 2, 2, 4] | 3 | Node 3's root attached under node 2 |
| union(1, 3) | [0, 0, 0, 2, 4] | 2 | find(1)=0, find(3)=2. Node 2 attached under 0. Nodes 0,1,2,3 now share root 0 |
| connected(0, 3) | [0, 0, 0, 2, 4] | 2 | find(0)=0, find(3)=0. Same root, so connected. Returns true |
| connected(0, 4) | [0, 0, 0, 2, 4] | 2 | find(0)=0, find(4)=4. Different roots, so not connected. Returns false |
Notice that union(1, 3) does not connect nodes 1 and 3 directly. It finds their roots (0 and 2) and connects the roots. After that, every node that previously pointed to root 2 now reaches root 0. The component count dropped from 3 to 2 because two distinct components merged into one.
Also notice that connected(0, 3) works even though node 3 still points to node 2 in the parent array, not to node 0. find(3) follows parent[3] = 2, then parent[2] = 0, then parent[0] = 0 (root found). The chain eventually reaches the shared root. Path compression would flatten this chain so future lookups are faster.
Path Compression
Without path compression, find can walk O(n) parent pointers on a degenerate chain. Path compression fixes this. During a find call, after reaching the root, every node on the path is updated to point directly to the root. The first call pays for the full walk, but every subsequent find on those same nodes is a single lookup.
Path Compression
A degenerate chain: 0 -> 1 -> 2 -> 3 -> 4. Root is 4. find(0) must traverse 4 edges.
Without path compression, find() is O(n) on a chain. This is the worst case.
The implementation is a single line of recursion:
Walk through what happens with a chain 0 ← 1 ← 2 ← 3 when we call find(3):
- find(3) calls find(2) because parent[3] = 2
- find(2) calls find(1) because parent[2] = 1
- find(1) calls find(0) because parent[1] = 0
- find(0) returns 0 because parent[0] = 0 (root)
- On the way back: parent[1] = 0, parent[2] = 0, parent[3] = 0
After this single find call, nodes 1, 2, and 3 all point directly to 0. Any subsequent find on these nodes is a single lookup.
There is also an iterative variant called path halving, where each node skips its parent: parent[x] = parent[parent[x]]. Both achieve the same amortized complexity.
Union by Rank
Without union by rank, repeatedly attaching one root under the other in the same direction can build a chain of length n. Union by rank prevents this by always attaching the shorter tree under the taller tree. The rank is an upper bound on the tree height.
Union by Rank
Two trees before union. Left tree: height 1 (3 nodes). Right tree: height 2 (5 nodes).
We want to merge these trees. The order matters for performance.
Consider merging sets one at a time in order. If we always attach the new root under the existing root, we get a chain of length n. With union by rank, we always attach the smaller tree under the larger one, keeping the height logarithmic.
Rank only increases when two trees of equal rank are merged. If one tree is already taller, the merged tree has the same height as the taller tree, because the shorter tree becomes a subtree that does not extend beyond the existing height. Only when both trees are the same height does attaching one under the other create a tree one level taller.
An alternative is union by size, where you track the number of elements in each set instead of rank. You attach the smaller set under the larger one. Both approaches yield the same time complexity. Union by size has the advantage that the size array always contains meaningful values (actual set sizes), while rank becomes an approximation after path compression.
The Complete Template
This is the full Union Find implementation with both optimizations. Every Union Find problem uses this same class. The problem-specific logic is always outside it: which elements to union, when to query find, and what to do with the component count.
The components counter starts at n (each element is its own component). Every successful union decrements it by 1. This gives you the number of connected components at any point in O(1).
| Method | Time | Description |
|---|---|---|
| __init__(n) | O(n) | Initialize n elements in n separate sets |
| find(x) | O(α(n)) | Return the root of the set containing x |
| union(a, b) | O(α(n)) | Merge sets of a and b, return True if they were different |
| connected(a, b) | O(α(n)) | Return True if a and b are in the same set |
| components | O(1) | Number of disjoint sets (read the field directly) |
Why the Runtime Works
With both path compression and union by rank, every find and union operation runs in O(α(n)) amortized time, where α is the inverse Ackermann function. For any input that fits in the physical universe, α(n) ≤ 4. This means every operation is effectively O(1).
Why path compression helps: each find call pays for a tree walk once but makes all future finds on those same nodes a single lookup. The work is front-loaded. A single expensive find amortizes its cost across every subsequent find on the same path. Over a sequence of operations, the total work is nearly linear.
Why union by rank helps: it prevents the tree from growing taller than O(log n) even without path compression. A tree of rank r has at least 2^r nodes. Since there are n nodes total, the rank can never exceed log n. Combined with path compression, the height stays almost flat.
For k operations on n elements, the total time is O(k * α(n)), which is effectively O(k). This is why Union Find can handle 10^5 or 10^6 operations without any performance concern.
Connected Components
Connected component tracking is the most common Union Find problem family. The pattern is always the same: start with n components, process connections, and track the count. Each union that actually merges two different components reduces the count by exactly one. A union that finds the roots are already the same does nothing.
For static graphs, DFS or BFS is simpler. But when edges are added dynamically and you need the component count after each addition, Union Find handles this directly. Number of Islands II is the canonical example: land cells are added one at a time, and the answer is the component count after each addition.
Number of Islands II
Empty 4x4 grid. All water. Zero components. We will add land cells one at a time and track connectivity.
Number of Islands II: each addLand call adds a cell, unions it with neighbors, and reports the component count.
The key technique for grid problems is 2D-to-1D mapping. Given a grid with rows rows and cols columns, cell (r, c) maps to index r * cols + c.
When a new land cell appears, we increment the component count by 1 (it starts as its own island). Then we check all four neighbors. For each neighbor that is already land, we union our new cell with it. Each successful union decrements the component count. If the new cell connects two previously separate islands, the count goes down by the number of bridges minus one.
Time complexity: O(k * α(m*n)) for k position additions. Space: O(m*n) for the parent and rank arrays.
row * cols + col, not row * rows + col. When the grid is not square (rows != cols), using rows instead of cols causes index collisions. For a 3x5 grid, cell (1, 0) maps to 1*5+0=5, not 1*3+0=3. Double-check your dimensions.Cycle Detection
Union Find detects cycles in undirected graphs directly. Process edges one by one. Before adding edge (u, v), check whether u and v are already in the same component by comparing find(u) and find(v). If they are already connected, this edge creates a second path between them, which is a cycle.
Cycle Detection
5 nodes, 5 edges. Process edges one by one. Before each union, check: are the endpoints already connected?
If find(u) == find(v) before union, adding edge (u,v) creates a cycle.
The Redundant Connection problem asks: given a tree with one extra edge, find the edge that creates the cycle. The approach is direct. Process edges in order, and the first edge where both endpoints are already connected is the answer.
This works because union returns False when the two nodes are already in the same set. That is exactly the cycle condition: if two nodes are already connected through previous unions, adding another edge between them creates a cycle.
For directed graphs, Union Find alone is not sufficient. You need to handle cases where a node has two parents (in-degree 2). Redundant Connection II requires checking for both cycle and two-parent cases, making it significantly harder.
Entity Grouping
Given a list of accounts where each has a name and one or more emails, merge every account that belongs to the same person. Two accounts belong to the same person if they share any email. If account A shares an email with B, and B shares a different email with C, all three are the same person even though A and C share nothing directly. These chains can be arbitrarily long, so simple pairwise matching will not work.
Union Find handles this directly. Each account starts as its own group, and as you scan through the emails, every time two accounts share an email you merge their groups. After union(1, 0) and union(3, 1), accounts 0, 1, and 3 are all in the same group regardless of which pairs actually shared emails. By the time every email has been processed, every account that should be merged already is.
You could union emails (strings), but then you need a HashMap as your parent structure and you still need to map back to account names at the end. It is more practical to union account indices. Maintain a map from each email to the first account index that contained it, and when a later account contains an email you have already seen, union those two account indices. Since accounts are integers in [0, n), the Union Find uses a simple array, and the account index gives you direct access to the name for the output.
Time: O(n * k * α(n) + E log E) where n is accounts, k is average emails per account, and E is total unique emails. The E log E comes from sorting each group's emails at the end. Space: O(n + E) for the Union Find and the email map.
Why Union Find over DFS/BFS? With DFS you would first build an adjacency list (email to list of account indices), then traverse it to find connected components. That is two separate passes over two data structures. Union Find does it in one pass: each shared email triggers a union call, and the groups form as a side effect of scanning the input. You never build an explicit graph.
account_idx instead of find(account_idx), you will put some of John's emails under index 0, others under index 1, and others under index 3. Three separate groups instead of one. Always call find() to get the actual root before grouping.Variant: HashMap Union Find
The solution above unions account indices (integers). But some problems give you strings or objects that do not map naturally to [0, n). For those, you can build Union Find on top of a HashMap instead of an array. In Accounts Merge, this means unioning emails directly. For each account, union every email with the first email in that account. No index mapping needed.
If the problem gives you elements that are already integers (account indices, node IDs, array positions), use array Union Find. If the elements are strings, coordinates, or other types, use HashMap Union Find. The array version has lower constant factors because array lookups are faster than hash lookups, but functionally they are identical.
The Entity Grouping Pattern
Accounts Merge is the template for a family of problems that all have the same shape: entities that share some attribute, where sharing can chain, and you need to find all the groups. The solution is always the same three phases: scan for shared attributes and union, then group by root, then format output.
- Sentence Similarity II: Words linked by synonym pairs. Union the words, then check if two sentences match word by word via find(). Same HashMap UF pattern.
- Evaluate Division: Variables linked by equations with ratios. Union Find with weighted edges (store the ratio along the path). Harder variant that extends basic UF.
- Smallest String With Swaps: Characters at positions linked by allowed swap pairs. Union the positions, group characters by component, sort within each group. Identical structure to Accounts Merge.
- Similar String Groups: Strings linked by the "similar" relation (differ by exactly one swap). Union similar strings, count components. The challenge is efficiently checking similarity.
When This Pattern Breaks
Union Find is designed for one operation: merging sets and querying membership. Several common problem requirements fall outside what it can do.
Splitting components. Once two sets are merged, they cannot be separated. The parent pointers encode the merged state, and there is no operation to undo a union. If you need to disconnect components, consider processing edges in reverse order (turning deletions into additions) or using a different data structure like Link-Cut Trees.
Finding paths. Union Find tells you whether two nodes are connected, but not how. It stores no path information, only component membership. If the problem asks for the actual path between two nodes, use DFS or BFS.
Directed graph connectivity. Union Find treats every edge as undirected. If you union A and B, both A and B can reach the same root regardless of which direction the edge pointed. For directed reachability, you need algorithms like Tarjan's or Kosaraju's for strongly connected components.
Shortest path queries. Union Find has no concept of distance or edge weight. It answers "are these two nodes in the same component?" but nothing about the cost of reaching one from the other. Use BFS (unweighted) or Dijkstra (weighted) for shortest paths.
Edge deletion. Standard Union Find does not support removing edges. If you need deletion, sometimes you can solve the problem offline by processing edges in reverse order. What would have been a deletion in forward order becomes an addition in reverse, and Union Find handles additions.
Union Find vs DFS/BFS
Both Union Find and DFS/BFS can solve connectivity problems. The choice depends on the problem constraints.
| Criterion | Union Find | DFS/BFS |
|---|---|---|
| Static graph, single query | Works but overkill | Simpler and preferred |
| Dynamic edges (add over time) | Process edges incrementally | Must rebuild from scratch |
| Multiple connectivity queries | O(α(n)) per query after setup | O(V+E) per query unless preprocessed |
| Need shortest path | Cannot do this | BFS gives shortest unweighted path |
| Need all nodes in a component | Must iterate all nodes to collect | DFS/BFS collects during traversal |
| Cycle detection (undirected) | find(u) == find(v) before union | Also works: back edge detection |
| 10^5+ queries on same graph | Much faster | Too slow without preprocessing |
| Grid problems (static) | Works but more code | DFS flood fill is simpler |
| Grid problems (dynamic) | Handles edge additions directly | Must re-flood-fill each change |
| Minimum Spanning Tree | Kruskal's algorithm | Not applicable |
If you see dynamic connectivity (edges being added over time with queries interspersed), Union Find is almost always the right tool. If you need to find a path or process nodes in a specific order, DFS/BFS is the right tool.
Debugging Union Find
When your Union Find code produces wrong answers, check these common failure points in order.
parent = [0] * n sets parent[i] = 0 for all i, meaning every node already points to node 0. All nodes start in the same component. The correct initialization is parent = list(range(n)) so parent[i] = i and each node is its own root.parent[a] = b instead of parent[find(a)] = find(b) breaks the data structure. Non-root nodes should not have their parent changed except through path compression. Always find the roots before performing a union.find(a) == find(b), the nodes are already in the same set. Performing the union anyway can corrupt the rank array and double-decrement the component count. Always check and return early.row * rows + col instead of row * cols + col causes index collisions when the grid is not square. For a 3x5 grid, cell (1, 0) should map to 5, not 3.Practice Problems
These problems are ordered by complexity. The foundation set builds comfort with the template. The later problems test whether you can map unfamiliar scenarios to union/find operations.
Foundation
| Problem | Difficulty | Approach |
|---|---|---|
| Number of Provinces | Medium | Union cities that share a direct connection. Start with n components and decrement on each successful union. The final count is the answer. |
| Redundant Connection | Medium | Process edges one at a time. The first edge where both nodes already share a root creates a cycle. That edge is the redundant one. |
| Number of Islands | Medium | Treat each land cell as a node. Union adjacent land cells using 4 directional checks. Count remaining components. Compare with DFS flood fill for trade offs. |
| Longest Consecutive Sequence | Medium | For each number, union it with its neighbor (num+1) if the neighbor exists in the set. Track component sizes during union and return the largest. |
Intermediate
| Problem | Difficulty | Approach |
|---|---|---|
| Accounts Merge | Medium | Union emails that belong to the same account. After all unions, group emails by their root representative and sort each group alphabetically. Attach the name from any account in the group. |
| Number of Islands II | Hard | Start with all water. For each land addition, create a new component and union with any adjacent land cells. Track component count dynamically after each operation. |
| Evaluate Division | Medium | Build a weighted union find where edges store ratios. On query, trace both variables to their roots and compute the answer from the accumulated weights along each path. |
| Surrounded Regions | Medium | Connect all border O cells to a virtual node. Union interior O cells with their O neighbors. Any O not connected to the virtual node is surrounded and gets flipped to X. |
| Satisfiability of Equality Equations | Medium | Process all == equations first by unioning the two variables. Then check each != equation. If both sides share a root, the system is unsatisfiable. |
Advanced
| Problem | Difficulty | Approach |
|---|---|---|
| Redundant Connection II | Hard | Three cases: no double parent, double parent without cycle, double parent with cycle. Track the two candidate edges from the node with two parents and test by removing one. |
| Min Cost to Connect All Points | Medium | Sort all possible edges by Manhattan distance. Greedily add the cheapest edge connecting two different components. This is Kruskal's MST. Stop after n-1 edges. |
| Smallest String With Swaps | Medium | Union all indices that can be swapped (transitivity means the whole group is interchangeable). Group characters by root, sort within each group, and place them back in order. |
| Similar String Groups | Hard | Two strings are similar if they differ in exactly 0 or 2 positions. Check all pairs (or use smart bucketing for large inputs), union similar ones. Answer is the component count. |
| Couples Holding Hands | Hard | Model each couple as a node. If seat neighbors belong to different couples, union those couples. Total swaps needed equals n minus the number of connected components. |
Reference Templates
Compact code shapes for quick recovery. Each template includes the context that determines when to use it.
Standard array Union Find with path compression, union by rank, and component count.
HashMap Union Find for strings or object keys. Auto-initializes on first access.
Cycle detection loop for undirected graphs. Returns the first edge that creates a cycle.
Connected components count. Start with n components, decrement on actual merges.
2D grid mapping. Convert (row, col) to a 1D index for array-based Union Find.
Dynamic grid addition. Add land cells one at a time, union with adjacent land.
Entity grouping three-phase pattern. Scan and union, group by root, format output.
Pattern Recap
Connected component tracking starts with n components. Each edge triggers a union, and each successful union (where roots differ) decrements the count by one. The count is always available in O(1). For dynamic grids, increment the count when new land appears, then union with adjacent land to merge.
Cycle detection processes edges in order and checks whether both endpoints already share a root. If they do, the edge connects two nodes that are already in the same component, which means there is already a path between them. Adding the edge creates a second path, forming a cycle. This only works for undirected graphs.
Entity grouping follows three phases. First, scan through entities and union any pair that shares an attribute. Second, group all attributes by calling find() on each owner to get the actual root. Third, format the output using the root's identity (name, index, or key). Transitive chains resolve automatically because each union merges entire component trees, not just pairs.
The data structure is always the same 15-line class. What changes is what you union (edge endpoints, shared-attribute entities, adjacent grid cells), what triggers a union (edge processing, attribute collision, neighbor check), and what you query (component count, same-root check, group membership).
Rebuilding the Pattern
When Union Find feels unclear, start with the question: does the problem involve grouping elements where connections can chain transitively? If A connects to B and B connects to C, does that mean A and C should be in the same group? If so, the groups are components, and Union Find tracks them.
After recognizing the pattern, decide what elements to union. In graph problems, union the endpoints of each edge. In entity grouping problems, union entities that share an attribute. In grid problems, union adjacent cells that share a property (both are land, both have the same value, etc.).
Then decide what to query. If the answer is "how many groups," track a component counter that starts at n and decrements on each actual merge. If the answer is "which group does this element belong to," call find() and use the root as the group identifier. If the answer is "does adding this connection create a cycle," check whether both endpoints already share a root before performing the union.
The data structure never changes. Write the 15-line class once at the top, then focus entirely on the problem-specific decisions: what to union, what triggers a union, and what to do with the result of find or the component count.
Check Your Understanding
Use these questions to check whether you can reason through the pattern without looking at the template.
Take Assessment
Ready to test it?
12 questions covering Union Find operations, path compression, cycle detection, and component tracking.
Practice this pattern
Apply the guide to complete interview problems with explanations and code.
Learn Union Find in a guided sequence
The Interview Course connects this pattern to its prerequisites, worked lessons, and progressively harder problems.