Union Find: Complete Guide with Interview Examples

Union Find is the data structure for questions about who is connected to whom. It keeps a partition of elements into disjoint groups, merges two groups in near-constant time, and answers whether two elements share a group in near-constant time. Interviewers reach for it in connected component problems, cycle detection in undirected graphs, and minimum spanning tree construction, and the whole structure is small enough to write from memory in an interview.

Definition: every group has one representative, called its root. Two elements are in the same group exactly when their roots are equal. The structure supports two operations. find(x) returns the root of the group containing x. union(x, y) merges the groups containing x and y.

Real-World Analogy

Imagine you are at the door of a class reunion checking people in. People arrive alone or in small groups, and it quickly turns out that many of them know each other through some chain of friends. You cannot memorize every friendship. So you give each friend group a spokesperson. When someone arrives, you ask who speaks for their group. If two newcomers have different spokespeople, their groups merge under one spokesperson. Later, when two people meet and wonder whether they already share a network, you compare spokespeople. The same spokesperson means the same group.

The reunion works fine as long as every group has a leader. Nobody needs to know everyone in their group, and two people can be checked in seconds without tracing the whole web of friendships. That is exactly the tradeoff Union Find makes. It trades detailed knowledge of a group for a fast way to answer one question: are these two elements in the same group?

Visual Explanation

The union operation is where the structure earns its name. It resolves two roots, decides which tree hangs under which, and keeps the trees shallow so future lookups stay fast.

    graph TD
    U["union(x, y)"] --> F1["rootX = find(x)"]
    U --> F2["rootY = find(y)"]
    F1 --> C{"rootX == rootY?"}
    F2 --> C
    C -->|"Yes"| S["Same group. Nothing to merge"]
    C -->|"No"| R{"rank[rootX] < rank[rootY]?"}
    R -->|"Yes"| A["Attach rootX under rootY"]
    R -->|"No"| B["Attach rootY under rootX. Bump rank on ties"]
    A --> D["One tree. Height stays low"]
    B --> D
  

Two details in this flow do the heavy lifting. find walks up the tree from an element to its root, and it flattens the path as it goes, pointing every node it passes directly at the root. union compares the roots of the two elements, and when they differ, it attaches the shorter tree under the taller one. The first detail is path compression. The second is union by rank. Together they keep the trees so shallow that each operation is effectively constant time.

When to Use This Pattern

• The problem asks for the number of connected components in an undirected graph or grid, like provinces, friend circles, or islands.
• Edges are added over time and you must answer connectivity questions between insertions. The graph is not fixed at the start.
• You need to detect a cycle in an undirected graph while processing its edges in order, and the answer is the edge that closes the first cycle.
• You are building a minimum spanning tree with Kruskal’s algorithm, which needs a cheap way to reject an edge whose endpoints are already connected.
• The elements you are grouping are not integers, like email addresses or strings, and two elements are equivalent when they share any common member.

Complexity Analysis

The α(N) in the table is the inverse Ackermann function. It grows so slowly that for any input you will ever see, it is effectively constant. That bound only holds because of the two optimizations. Path compression keeps trees flat by rewiring nodes to the root during every find. Union by rank keeps trees short by attaching the smaller tree under the larger one. Without either, a sequence of unions can build a long chain, and each find walks the full length of that chain, which turns a set of operations into quadratic work.

Common Mistakes

Comparing parent values instead of roots. A common first attempt checks parent[x] === parent[y] to test connectivity. That is wrong because parent[x] stores the immediate parent of x, and that value goes stale the moment a union happens. Only the root of a group has itself as its own parent. The check must be find(x) === find(y). To catch this during practice, run two unions and then print the parent array. You will see internal nodes still pointing at old parents, and the direct comparison will fail even though the elements are connected.

Skipping the optimizations. Union Find works without path compression and union by rank, and it will pass small examples. The failure shows up at scale. A sequence like union(0,1), union(1,2), union(2,3) builds a chain, and each find then walks the full chain length. To catch this during practice, feed a chain of n unions into the naive version and count the number of parent lookups in a find. It grows with n, where the optimized version stays flat.

Indexing off by one. Two modeling mistakes appear constantly. Problems that number nodes from 1, like Redundant Connection, need a parent array of size n+1, because node n must fit. Grid problems need the cell (r, c) flattened to a single index with r * cols + c, and every neighbor check must verify the neighbor is inside the grid before unioning. To catch this during practice, trace the first union on paper. An index that falls outside the array is the tell.

Using Union Find when the problem needs a path or an order. Union Find answers one question: are two elements in the same group? It cannot return the path between them, a traversal order, or anything about directed graphs. To catch this before you start, read the problem for what it asks. If it asks for a route or a visit order, use graph traversal. If it asks repeated connectivity questions, Union Find is the right tool.

Related Patterns

• Graph Traversal . DFS and BFS also find connected components, and they can return the actual path between nodes. Use them when you need to visit nodes or recover a route. Use Union Find when you only need fast connectivity answers.
• Cycle Detection . Union Find detects cycles in undirected graphs while edges are added. The cycle detection page covers Floyd’s algorithm and DFS state tracking, which handle linked lists and directed graphs where Union Find does not apply.
• Greedy Algorithms . Kruskal’s minimum spanning tree algorithm is greedy: it always takes the cheapest edge that does not close a cycle. The greedy page explains why that strategy is safe and where it fails.

Next Steps

The concept only helps once the code is automatic. Grab the code templates in six languages, then work through the practice problems from connectivity checks to Kruskal’s MST.