Union-Find Interview Questions

Mohammed Islam Hadjoudj

Expert Operations Research Engineer

1. What a union-find question is actually testing

Union-find is the rare interview topic where the implementation is not the difficulty. Fifteen lines, two optimisations, no edge cases worth arguing about. Interviewers know that, which is why the questions are built somewhere else entirely.

They test three things. Do you recognise a connectivity question? Anything phrased as "are these two in the same group", "how many groups are there", or "which change merges two groups" is union-find, even when the words are accounts, stones, equations or cables. Do you know when it beats a traversal? A single static graph can be swept by BFS or DFS just as fast; union-find wins when the edges arrive one at a time and the answer is needed after each one. Can you choose the elements? This is where the hard questions live, and where section 7 spends its time.

The eight problems below are the ones that recur, each with the solution, the follow-up, and the error that loses the offer. Every worked example on this page was executed by script. If you want the data structure itself derived from scratch rather than recapped, that is the guide to union-find.

2. The template, and the two lines that matter

Write this without thinking. Two optimisations, one line each, and interviewers ask about both by name.

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.count = n                       # number of components, free of charge

    def find(self, x):
        root = x
        while self.parent[root] != root:
            root = self.parent[root]
        while self.parent[x] != root:        # PATH COMPRESSION: flatten the walk
            self.parent[x], x = root, self.parent[x]
        return root

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                     # already together: nothing to merge
        if self.size[ra] < self.size[rb]:    # UNION BY SIZE: small tree under big
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        self.count -= 1
        return True

Three details to say out loud while you type them. union returns a boolean, and that return value answers half the questions on this page: False means the two were already connected, which means the edge you just tried closes a cycle. count is maintained by the merges, so component counting never needs a second pass. And the find above is iterative, which matters on a chain of a hundred thousand elements where the recursive version dies on the call stack.

Why both optimisations? Union by size alone bounds the depth at O(log n), because a tree only gets taller when two trees of equal size merge. Path compression alone also gives O(log n) amortised. Together they give O(α(n)) amortised per operation, which is section 11. If you can only remember one, remember path compression: it is one line and it does most of the work in practice.

One implementation note worth volunteering: union by rank and union by size are interchangeable for the bound. Rank stores an upper bound on the height, size stores the element count. Size is more useful in interviews because half the follow-ups ask for the size of the resulting component, and you already have it.

3. Counting connected components

The question. Given n nodes and a list of undirected edges, how many connected components are there? The classic phrasing is LeetCode 323, and Number of Provinces is the same question with an adjacency matrix.

With the template above there is no algorithm left to write.

def count_components(n, edges):
    dsu = DSU(n)
    for a, b in edges:
        dsu.union(a, b)
    return dsu.count

On the running example, ten elements and the eight unions (0,1) (2,3) (1,2) (4,5) (6,7) (5,6) (0,3) (8,9) leave three components: {0,1,2,3}, {4,5,6,7} and {8,9}, of sizes 4, 4 and 2. Seven unions merged; union(0, 3) did not, because 0 and 3 were already in the same tree by then.

Run one find on every element afterwards and the structure ends up as parent = 0 0 0 0 4 4 4 4 8 8: every element points straight at the root of its component, so every later query is a single hop. That flattening is path compression paying for itself.

The follow-up: why not just run DFS? On a static graph, do. Both are linear and DFS needs no extra structure, so reaching for union-find on a fixed edge list is a small red flag rather than a plus. The honest answer is that union-find earns its place when the edges arrive over time, when you need the answer after each arrival, or when the graph is too large to hold as an adjacency list but the pairs stream past. Saying this unprompted separates you from candidates who pattern-match on the word "components".

The trap. Returning len(set(find(v) for v in range(n))) without calling find, and instead counting distinct values of parent. Before compression the parent array holds intermediate nodes, not roots, so the count comes out too high. Maintain count in union and the question does not arise.

4. Redundant Connection: the edge that closes a cycle

The question. A tree on n nodes has had one extra edge added. Find the edge that can be removed, and if several qualify, return the one that appears last in the input.

This is the boolean returned by union, and nothing else.

def find_redundant(edges):
    dsu = DSU(len(edges) + 1)
    for a, b in edges:
        if not dsu.union(a, b):          # a and b were already connected
            return [a, b]                # so this edge closes a cycle

Process the edges in order and the first one whose union returns False is the answer. It is also automatically the last such edge in the input, because a tree plus one edge has exactly one cycle, so exactly one edge fails. On [[1,2],[2,3],[3,4],[1,4],[1,5]] the answer is [1,4], and on the triangle [[1,2],[1,3],[2,3]] it is [2,3].

The follow-up: what if the graph is directed? That is Redundant Connection II, and it is a genuinely harder problem rather than a variation. A directed version can fail in two ways: a node with two parents, or a cycle, and it can have both at once. The technique is to find the node with in-degree two, tentatively remove each of its two candidate edges, and test whether the rest forms a valid rooted tree with union-find. Knowing that the directed case splits into cases is enough; interviewers rarely make you write it.

The trap. Using DSU(n) when the nodes are labelled 1 to n. Every union-find bug of this class is an off-by-one on the array size, and it surfaces as an index error on the very last node rather than as a wrong answer. Allocate n + 1 and ignore slot zero.

5. Islands II: why BFS loses when the grid changes

The question. An empty m × n grid of water. Land is added one cell at a time. After each addition, report how many islands exist.

This is the question that justifies the whole data structure, so treat it as the one to get right. Counting islands on a fixed grid is a flood fill, and it costs O(mn). Doing that after every one of k additions costs O(k × mn), which is quadratic and will time out. Union-find turns each addition into a constant amount of work, because adding land can only ever merge islands, never split them.

def num_islands2(m, n, positions):
    dsu, seen, out, count = {}, set(), [], 0
    for r, c in positions:
        if (r, c) in seen:               # a repeated position adds nothing
            out.append(count)
            continue
        seen.add((r, c))
        dsu[(r, c)] = (r, c)             # a new island of one cell
        count += 1
        for dr, dc in ((1,0), (-1,0), (0,1), (0,-1)):
            nb = (r + dr, c + dc)
            if nb in seen and union(dsu, (r, c), nb):
                count -= 1               # merged with a neighbour
        out.append(count)
    return out

Each new cell starts as its own island, then merges with at most four neighbours, so each step costs O(α) and the whole run is O(k α(mn)). On a 3 by 3 grid with land added at (0,0), (0,1), (1,2), (2,1) the answers are 1, 1, 2, 3: the second cell joins the first, then the next two are isolated. Add (1,1) as a fifth move and it touches all three, so the sequence ends 1, 1, 2, 3, 1.

The follow-up: what if land can also be removed? Say plainly that union-find does not support deletion, because there is no way to undo a merge once the paths are compressed. The real answers are to process the operations offline in reverse, turning deletions into additions, or to use a union-find with rollback, which keeps an undo stack and therefore gives up path compression in exchange for union by rank alone at O(log n). Naming "offline reversal" is usually enough.

The trap. Forgetting that the same position can appear twice in the input. Adding land where land already exists must not increment the count, and the guard is one line. It is also the only hidden test case in this problem.

6. Accounts Merge: when the elements are not integers

The question. Each account is a name followed by a list of emails. Two accounts belong to the same person when they share any email. Merge them and return the emails of each person, sorted.

The structure is trivially union-find. What the question really tests is the plumbing: your elements are strings, and the array-based DSU needs integers.

ids = {}
for account in accounts:
    for mail in account[1:]:
        if mail not in ids:
            ids[mail] = len(ids)         # assign each email a dense integer
        owner[mail] = account[0]

dsu = DSU(len(ids))
for account in accounts:
    first = ids[account[1]]
    for mail in account[2:]:
        dsu.union(first, ids[mail])      # chain every mail to the first one

Union every email in an account to the first email of that account, which is enough to make the whole account one component, then bucket the emails by root and sort each bucket. Merging John [a, b], John [c, b], Mary [m] and a second John [z] gives three people: John with a, b, c, Mary with m, and a different John with only z.

That last group is the point of the question. The name is not the identity. Two accounts with the same name and no shared email are two different people, and a candidate who unions by name gets a plausible wrong answer that the sample input is deliberately built to catch.

The follow-up: could you avoid the id mapping? Yes, by storing parent as a dictionary keyed by the string itself, which costs a hash per access instead of an array index. It is cleaner to write and slower to run, and saying which trade-off you are making is what is being marked. In a language without dictionaries in the hot path, or when the same structure is reused millions of times, the dense integer mapping wins.

The trap. Building the name lookup from the root's email rather than keeping a map from email to name. After compression the root can be any email in the group, and if you recorded the name against a specific one you will attach the wrong name to a merged account.

7. Most Stones Removed: choosing what to union

The question. Stones sit on a grid. You may remove a stone if it shares a row or a column with another remaining stone. What is the maximum number you can remove?

Two insights, and the second is the one that makes it a good interview question.

First, from any connected group of stones you can remove all but one. Remove them in the reverse of the order a spanning tree of the group is built, taking leaves first, and the last stone standing keeps the group legal at every step. So the answer is total stones - number of components, and the whole problem reduces to counting components.

Second, and this is the part that is hard under pressure: do not union the stones. Union the rows and the columns.

Each stone at (r, c) becomes a single union(row r, column c). Two stones end up connected exactly when they share a row or a column, or are linked by a chain of stones that do, which is the relation the problem describes. It also turns an O(k2) pairwise comparison into O(k α). On the six-stone example the whole board collapses to one component and the answer is 5. On [[0,0],[0,2],[1,1],[2,0],[2,2]] there are two components and the answer is 3.

The follow-up: how do you keep rows and columns from colliding? They live in the same structure, so row 2 and column 2 must be different elements. Offset the columns by a constant larger than any row index, commonly c + 10001 for the stated limits, or use a dictionary keyed by ("r", r) and ("c", c). Mentioning the collision before the interviewer does is worth a lot on this problem.

The trap. Counting components over all rows and columns that exist rather than only those that actually hold a stone. Empty rows are isolated elements and each one inflates the component count, so the answer comes out too small. Only create an element the first time a stone needs it.

8. Evaluate Division: weighted union-find

The question. You are given equations such as a / b = 2.0 and b / c = 3.0 and asked to answer queries such as a / c, returning -1 when the answer cannot be determined.

Most candidates build a graph and run a DFS multiplying edge weights along the path, which is a perfectly good answer. The stronger answer is weighted union-find: store, alongside each parent pointer, the ratio of the child's value to the parent's value. Then find returns both the root and the accumulated ratio to it, and any query is one division.

def find(x):                              # returns (root, value of x / value of root)
    if parent[x] == x:
        return x, 1.0
    root, wp = find(parent[x])
    weight[x] *= wp                       # rescale while the path is flattened
    parent[x] = root
    return root, weight[x]

With a / b = 2 and b / c = 3, the queries come out as a / c = 6, b / a = 0.5, c / a = 1/6, a / a = 1, and -1 for anything mentioning a symbol that never appeared, which is why x / x is -1 rather than 1 in the standard problem. That last case is a deliberate trick and it catches people who special-case equal arguments before checking that the symbol exists.

The follow-up: how do you detect a contradiction? If union(a, b, v) finds that a and b already share a root, do not merge; compare the implied ratio against v instead. A mismatch beyond floating point tolerance means the input is inconsistent. The same structure with addition instead of multiplication answers "is this set of offset constraints satisfiable", which is how the technique appears in scheduling problems.

The trap. Compressing the path without updating the weight, which is the mistake the figure warns about. The pointers stay correct, every subsequent query silently returns a wrong number, and the bug survives any test that only checks connectivity.

9. Equality equations: the order you process them in

The question. Given equations such as "a==b" and "b!=c" over single lowercase letters, decide whether they can all be true at once.

The solution is four lines and one idea: two passes, equalities first.

dsu = DSU(26)
for e in equations:
    if e[1] == '=':
        dsu.union(ord(e[0]) - 97, ord(e[3]) - 97)
for e in equations:
    if e[1] == '!':
        if dsu.find(ord(e[0]) - 97) == dsu.find(ord(e[3]) - 97):
            return False
return True

Equality is an equivalence relation, so it partitions the letters into groups that must hold the same value. Inequality is not an equivalence relation and cannot be unioned at all; it can only be checked against the finished partition. Process them in one interleaved pass and the answer depends on the input order, which is the bug this question exists to catch: ["a!=b", "a==b"] would be accepted, because the inequality is tested before the union that contradicts it.

Verified outputs: ["a==b","b!=a"] is False, ["a==b","b==c","a==c"] is True, ["a==b","b!=c","c==a"] is False, and the single equation ["a!=a"] is False because a letter is always equal to itself.

The follow-up: what if the variables were not single letters? Exactly the id mapping from section 6: hash each name to a dense integer, or key the parent dictionary by the name. Nothing else changes, which is a good thing to point out because it shows you see the structure as separate from the encoding.

The trap. Allocating the DSU over the letters that appear rather than over all 26. It works, and it costs you the two minutes you spend building the mapping for an alphabet that is already dense and tiny. Read the constraints before writing generic code.

10. Kruskal: union-find inside a spanning tree

The question. Connect all the points at minimum total cost, where the cost between two points is their Manhattan distance. This is LeetCode 1584, and it is a minimum spanning tree wearing a hat.

Union-find is not the answer here, it is the component that makes the answer work. Kruskal's algorithm sorts every candidate edge by weight and accepts an edge exactly when it joins two different components, which is the boolean returned by union.

edges.sort()                              # by weight
dsu, total, used = DSU(n), 0, 0
for w, a, b in edges:
    if dsu.union(a, b):                   # only if it connects two components
        total += w
        used += 1
        if used == n - 1:                 # a spanning tree has n-1 edges
            break

On the five points [[0,0],[2,2],[3,10],[5,2],[7,0]] there are 10 candidate edges, Kruskal keeps four of them with weights 3, 4, 4 and 9, and the total is 20. The early exit at n - 1 edges matters on dense inputs, where the candidate list is O(n2) and most of it is never needed.

The follow-up: Prim or Kruskal here? For a complete graph on n points, Kruskal builds and sorts n(n-1)/2 edges, which is O(n2 log n), while Prim with an array scan runs in O(n2) and never materialises the edge list. On a dense instance Prim is the better answer, and knowing that Kruskal is the sparse-graph algorithm is the point of the question. The trade-off is worked through in minimum spanning trees and in Kruskal's algorithm.

The trap. Adding the weight before testing the union, so rejected edges still contribute to the total. It produces a number that is close enough to look right on the sample and wrong on everything else.

11. The complexity answers

This is the one topic where the honest answer is slightly awkward, and interviewers ask precisely because of that.

α is the inverse Ackermann function, and it grows so slowly that α(n) ≤ 4 for every n that could be stored in any physical computer. So the practical answer is "effectively constant", and the correct answer is "O(α(n)) amortised, which is not the same as O(1)". The distinction is real: Fredman and Saks proved in 1989 that no structure of this kind can do better, so the α is not an artefact of the analysis.

Two more numbers worth having. Space is O(n), two integer arrays. And the amortisation is per sequence, not per call: a single find can still walk a long path, it is the total over m operations that is bounded. Interviewers sometimes push on that, and "amortised, not worst case per operation" is the phrase they want.

As a sanity check on how flat the trees really get: after 200,000 random unions over 100,000 elements and one find on every element, the deepest tree in the structure is one pointer. Every element points directly at its root.

12. Mistakes that fail the interview

Ordered by how often they appear; the first three account for most rejected solutions.

• Comparing elements instead of roots. if a == b where if find(a) == find(b) was meant. It compiles, it runs, and it answers a different question.
• Skipping union by size. Path compression alone usually passes, so this survives testing and then degrades on adversarial input. Both optimisations are one line each; write both.
• Recursive find on deep input. A hundred thousand chained unions is a hundred thousand stack frames. Write the iterative version, or say why the recursion depth is safe here.
• Off-by-one on the array size. Nodes labelled 1 to n need DSU(n + 1). This is the single most common crash in these problems.
• Unioning the wrong things. Stones instead of rows and columns, accounts instead of emails, names instead of identities. When the pairwise version looks quadratic, the elements are usually wrong.
• Interleaving equalities and inequalities. Constraints that merge must all be applied before any constraint that only checks. Two passes, always.
• Forgetting that union-find cannot delete. If the problem removes edges, say so immediately and offer offline reversal or a rollback structure. Trying to patch deletion into a compressed structure is a dead end.
• Not maintaining the component count. Recomputing it with a loop over find after every operation turns a linear solution into a quadratic one, which is exactly the failure mode Islands II is built to expose.
• Quoting O(1). It is O(α(n)) amortised. Say "effectively constant, formally inverse Ackermann" and the follow-up disappears.

The habit that prevents most of these: before writing anything, say what one element represents and what it means for two of them to be in the same set. If you cannot finish both halves of that sentence, you have not modelled the problem yet, and the fifteen lines will not save you.

14. References

The papers that introduced these techniques and the texts that analyse them, in chronological order.

1. Kruskal, J. B. (1956). “On the shortest spanning subtree of a graph and the traveling salesman problem.” Proceedings of the American Mathematical Society, 7(1), 48–50.
2. Galler, B. A. and Fischer, M. J. (1964). “An improved equivalence algorithm.” Communications of the ACM, 7(5), 301–303.
3. Hopcroft, J. E. and Ullman, J. D. (1973). “Set merging algorithms.” SIAM Journal on Computing, 2(4), 294–303.
4. Tarjan, R. E. (1975). “Efficiency of a good but not linear set union algorithm.” Journal of the ACM, 22(2), 215–225.
5. Tarjan, R. E. and van Leeuwen, J. (1984). “Worst-case analysis of set union algorithms.” Journal of the ACM, 31(2), 245–281.
6. Fredman, M. and Saks, M. (1989). “The cell probe complexity of dynamic data structures.” Proceedings of the 21st Annual ACM Symposium on Theory of Computing, 345–354.
7. Cormen, T. H., Leiserson, C. E., Rivest, R. L. and Stein, C. (2009). Introduction to Algorithms, 3rd edition, Chapter 21. MIT Press.
8. Sedgewick, R. and Wayne, K. (2011). Algorithms, 4th edition, Section 1.5. Addison-Wesley.
9. McDowell, G. L. (2015). Cracking the Coding Interview, 6th edition. CareerCup.
10. Skiena, S. S. (2020). The Algorithm Design Manual, 3rd edition, Chapter 8. Springer.