Union-Find (Disjoint Set): How to Code It in an Interview

Union-Find, also called a disjoint set, is a data structure that tracks which elements belong to the same group and lets you merge two groups together, both in close to constant time per operation once you add two specific optimizations. It answers one narrow question well: given a set of elements and a stream of "these two belong together" instructions arriving one at a time, which elements end up in the same group, and can you tell instantly whether two elements are already connected. A breadth-first search rebuilds the whole connectivity picture from scratch every time you ask, while Union-Find keeps a running answer and updates it incrementally, which is why it beats BFS or DFS on any problem where the graph changes over the course of the algorithm instead of sitting still. What follows is how to recognize the pattern from the way an interviewer phrases the problem, the two versions of the code, a full walkthrough of an interview-style problem, and the mistakes that cost candidates the follow-up questions.

What Is Union-Find, and What Problem Does It Solve?

Union-Find solves the problem of tracking connected groups, called disjoint sets, as new connections get added one at a time, without recomputing the whole structure from the ground up. Every element starts in its own group. Each time a "union" instruction arrives, you merge the two groups those elements belong to, and each time a "find" instruction arrives, you return an identifier for the group an element currently belongs to, so two elements are connected exactly when their identifiers match.

The data structure represents each group as a small tree, not a list or a set object. Every element points to a parent, and the element at the top of the tree, the one that points to itself, is the representative for the whole group. Finding an element's group means walking up parent pointers until you hit that self-pointing root, and merging two groups means pointing one root at the other, folding an entire tree under a different tree in a single pointer update instead of copying or scanning either group's members. That single design choice, a group represented by its root instead of its full membership list, is what makes both operations cheap.

How Do You Recognize a Union-Find Problem in an Interview?

You recognize a Union-Find problem when the prompt describes relationships arriving incrementally and asks about grouping, connectivity, or cycles, rather than asking you to explore a graph that is already fully built and static.

A few phrasings tend to point at Union-Find specifically:

• "Given a list of connections, determine how many separate groups exist."
• "Given a list of edges added one at a time, find the edge that creates the first cycle."
• "Accounts belong to the same person if they share an email. Merge accounts that belong to the same person."
• "Two cities are in the same province if they are connected directly or through other cities."
• "As each pair gets connected, report how many groups remain after each step."

That last phrasing, an answer requested after every single addition, is the strongest tell, because Union-Find's whole advantage over BFS or DFS is that it updates cheaply instead of rebuilding from scratch on every query. If a problem hands you the full graph up front and asks one question about it once, BFS or DFS is usually simpler and just as fast; if the graph grows incrementally and you need the answer at multiple points along the way, that is when Union-Find starts paying for itself.

How Do You Implement Union-Find With Path Compression and Union by Rank?

You implement Union-Find as a parent array plus two functions, find and union, then add path compression and union by rank, because the plain version degrades to a straight line under bad input and turns every operation into an O(n) walk. Here is the version that works but is not fast enough for an interview:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))

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

    def union(self, a, b):
        root_a = self.find(a)
        root_b = self.find(b)
        if root_a != root_b:
            self.parent[root_a] = root_b

This version is correct: every find walks up parent pointers to the root, and every union attaches one root to the other. The problem is that nothing stops the tree from growing tall. Union elements in a chain, 0 into 1, 1 into 2, 2 into 3, and you build a straight line n elements long, so a find on the far end costs O(n), which turns a loop of n unions into an O(n squared) algorithm and defeats the reason you reached for Union-Find.

Path compression rewrites every node on the path to point directly at the root the moment you find it, so the next find on any of those nodes is instant. Union by rank attaches the shorter tree under the taller one instead of picking a direction arbitrarily, keeping the trees from growing tall to begin with. Here is the version an interviewer actually wants to see:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * 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, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
        return True

Two details here matter beyond the two optimizations themselves. First, union returns a boolean: false when the two elements were already in the same group, true when it merged two separate groups. That return value is the single most reusable piece of this pattern, since it directly answers "did this connection just create a cycle" and "did the group count just drop by one" with no extra bookkeeping. Second, rank only increases when two trees of equal rank merge, never on every union, because attaching a shorter tree under a taller one should not change the taller tree's height.

Why Is the Time Complexity Nearly O(1) per Operation?

Union-Find with both optimizations runs in O(alpha(n)) amortized time per operation, where alpha is the inverse Ackermann function, a quantity that grows so slowly it stays under 5 for any input size you could ever construct in practice, which is why people round it down to "essentially constant time" in an interview answer. Without path compression but with union by rank alone, the bound is O(log n) per operation, since trees stay balanced but paths can still be logarithmically long, and combining both optimizations is what pushes the bound down to the inverse Ackermann result.

You do not need to derive that bound by hand, and most interviewers will not ask you to. What they want is the shape of the argument: union by rank keeps the trees shallow to begin with, and path compression flattens whatever height remains every time you touch a path, so the two optimizations attack the same problem, tree height, from two directions, and the combination beats either alone. Stating that relationship, rather than just quoting "inverse Ackermann," tells an interviewer you understand why the optimizations exist and not just that they exist.

How Do You Solve Number of Provinces With Union-Find?

You solve Number of Provinces, one of the most common Union-Find interview problems, by unioning every pair of directly connected cities and counting how many separate groups remain once every connection has been processed. The setup: an n by n matrix where a 1 at row i, column j means city i and city j are directly connected, and a province is any group of cities reachable from each other, directly or through other cities in between.

Start every city in its own group, so the province count begins at n, then walk every pair the matrix marks as directly connected and call union on that pair. Because the union function above returns true only when it actually merges two previously separate groups, every true return means two provinces just became one, so you decrement the count exactly once per real merge and ignore every union call that returns false because the two cities were already in the same province.

def find_circle_num(is_connected):
    n = len(is_connected)
    uf = UnionFind(n)
    provinces = n

    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j] == 1:
                if uf.union(i, j):
                    provinces -= 1

    return provinces

Walk a small example by hand: three cities where city 0 connects to city 1, and city 1 connects to city 2, but city 0 does not connect directly to city 2, so provinces starts at 3, drops to 2 once union of 0 and 1 succeeds, and drops to 1 once union of 1 and 2 succeeds. The matrix never lists 0 and 2 as directly connected, but by the time you would check that pair, find already resolves both to the same root, since path compression already folded them into one tree. The answer, 1 province, matches what a slower BFS over all three cities would return, but Union-Find gets there without a queue, a visited set, or a separate traversal per starting city.

When Should You Use Union-Find Instead of BFS or DFS?

Use Union-Find when connections arrive incrementally and you need repeated connectivity answers as the graph grows, and use BFS or DFS when you get the full graph up front and only need to answer a connectivity question once. This distinction gets skipped in most write-ups, which present Union-Find as strictly better than graph traversal, but that is not true in practice, and an interviewer who hears you claim it usually pushes back.

Redundant Connection is the clearest example of Union-Find's real advantage: you get a list of edges one at a time, and need to find the exact edge that, when added, creates the first cycle. Union-Find handles this in one pass, since a union call returning false is precisely the moment a cycle formed, while the same thing with BFS means re-running a full traversal after every edge addition, turning an O(n) pass into an O(n squared) one for no benefit.

Number of Islands, on the other hand, hands you the entire grid at once with no incremental updates, so a straightforward BFS or DFS flood fill is simpler to write and just as fast. Reaching for Union-Find here adds code without adding speed, and an interviewer who watches you overcomplicate a static problem will not score that in your favor. Watch whether the problem implies a static, fully known graph, where BFS or DFS is the right default, or one that changes as the algorithm runs, where Union-Find earns its keep.

Which LeetCode Problems Use This Pattern, and Why?

A handful of well-known problems teach the range of what Union-Find is actually for, and knowing why each one needs it, not just that it uses the pattern, separates memorized code from an understood tool. Number of Provinces, covered above, is the direct application: count connected groups from a static adjacency matrix. Redundant Connection extends the same idea to finding the first edge that closes a cycle, using the union return value directly instead of the province count.

Accounts Merge adds a wrinkle: instead of numeric nodes, you union accounts that share an email address, so you need a mapping from email to account index before the standard logic applies at all, and this trips candidates who only ever practiced on integer indices, since half the real work is building that mapping correctly. Graph Valid Tree asks whether a set of edges forms exactly one tree with no cycles and no disconnected pieces, so every union call must succeed and the final group count must equal exactly one. Smallest String With Swaps unions indices connected through a chain of allowed swaps, then sorts the characters within each group independently, a good example of Union-Find as a preprocessing step feeding a different algorithm.

Working through these four in order covers the range from the most direct application to the ones that dress the pattern up in different vocabulary.

What Mistakes Sink a Union-Find Answer in an Interview?

Skipping path compression is the most common mistake, and it usually survives testing on small examples because the tree never grows tall enough on a five-element test case to expose the O(n) find. The bug only shows up on the interviewer's larger hidden test, or when they ask directly what the worst-case complexity is and you cannot back your claimed O(alpha(n)) answer with code that actually earns it.

Comparing the two elements directly instead of comparing their roots is the second common failure. Writing "if a == b" checks whether the two input values are literally equal, not whether they belong to the same group, an easy slip under time pressure since the code compiles and looks reasonable. The correct check is always "if find(a) == find(b)", comparing the roots, never the raw inputs.

Forgetting to initialize rank, or initializing it to anything other than zero, breaks the union-by-rank optimization silently: the comparison in the union function picks the wrong tree to attach under the other one and slowly degrades the expected balance. This does not throw an error, it just quietly loses the performance guarantee while still returning correct answers, one of the harder bugs to catch without specifically testing for it.

Using recursion for find without a base case that terminates, or recursing on a self-referential root never properly set during initialization, causes an infinite loop or a stack overflow on malformed input. Every element must start as its own parent in the constructor, self.parent[i] equal to i for every i, or the first find call on an uninitialized index breaks immediately.

What Should You Say Out Loud While You Solve One?

Name why Union-Find fits before you write any code: the specific detail in the problem, connections arriving incrementally, or a cycle check needed at each step, that ruled out a simpler BFS or DFS. That sentence tells the interviewer you chose the pattern deliberately.

As you write the class, narrate the two optimizations as you add them: say you are compressing the path so future finds on these nodes become instant, and attaching by rank so the tree never grows tall enough to need compression. Trace a small example by hand once the code is on the screen, and watch for the interviewer's reaction when a find resolves instantly on a node that was three levels deep before compression touched it. Our guide to analyzing time complexity goes deeper on defending an amortized bound like this one under follow-up questions.

Then connect the pattern back to the graph-traversal alternative, stating when you would reach for BFS or DFS instead and why this problem does not fit that case. Our BFS vs DFS breakdown covers that decision further, and our guide to Kahn's algorithm and topological sort is the other graph pattern most likely to come up alongside this one.

Our curated question bank pulls from real onsite reports, so the Union-Find problems you find there reflect what companies are currently asking rather than a static public list from several years ago. And for the full map of how this pattern relates to sliding window, monotonic stack, two pointers, and the rest of the core set, our guide to spotting patterns before you code covers that signal-recognition habit across every pattern this site treats in depth.

Frequently Asked Questions

What is the Union-Find algorithm used for?

The Union-Find algorithm, also called a disjoint set, tracks which elements belong to the same group as new connections get added over time, and answers whether two elements are already connected without rebuilding the whole structure on every query. It shows up most in problems about counting connected components, detecting the first edge that creates a cycle, and merging records that share an identifying field.

Is Union-Find the same as a disjoint set?

Union-Find and disjoint set refer to the same data structure. "Disjoint set" describes what it represents, a collection of non-overlapping groups, and "Union-Find" describes the two operations it supports, merging groups together and finding which group an element belongs to. Both names show up interchangeably in interview problems and in most textbooks.

What is the time complexity of Union-Find with path compression and union by rank?

With both optimizations, Union-Find runs in O(alpha(n)) amortized time per operation, where alpha is the inverse Ackermann function, a value that stays below 5 for any practically sized input, so most interview answers round it to essentially constant time. Without either optimization, a single find can degrade to O(n) in the worst case if elements happen to be unioned in a long chain.

When should I use Union-Find instead of BFS or DFS?

Use Union-Find when connections arrive incrementally and you need the connectivity answer at multiple points as the graph grows. Use BFS or DFS when the entire graph is known up front and you only need one connectivity answer, since a traversal is simpler to write and just as fast for that case.

Why does my Union-Find solution work on small tests but time out on large ones?

The likely cause is a missing path compression step, which means find walks the full height of the tree on every call instead of resolving instantly after the first compression. Small test cases rarely build a tree tall enough to expose this, but a large randomized test or an adversarial chain of unions will, so add the recursive path-compression line inside find if it is missing.

Do I need to memorize the inverse Ackermann function to use Union-Find in an interview?

You do not need to derive it. You need to know that path compression and union by rank together push the amortized time down to what is commonly described as essentially constant, and be able to explain why each optimization helps: keeping trees shallow to begin with, and flattening them further on access. Interviewers test whether you understand that relationship, not whether you can derive the bound from scratch.