Union-Find Problem Patterns

DFS and BFS answer connectivity questions in $O(V + E)$ — but only for a graph that is fully built. If edges arrive one at a time and you must answer “are these two connected?” after each one, traversal means re-running the whole search per query.

Union-find (disjoint set union) is the structure for that. It maintains connectivity incrementally, and both operations run in almost constant time.

The Union-Find data structure page covers how it works. This page is about recognising when a problem wants one, and the four shapes those problems take.

What you’ll learn

• The 20-line implementation worth memorising, with both optimisations.
• The union return value that turns the structure into a cycle detector.
• Maintaining a component count for free.
• When union-find beats DFS — and the several cases where it does not.
• Three real LeetCode problems solved in the browser: 547, 684, 1319.

The cue

You are looking at union-find when…

• Edges arrive incrementally and you answer queries between additions — 305, 1101.
• “How many groups / provinces / components” after processing all relations — 547, 323, 1319.
• Detect the edge that creates a cycle in an undirected graph — 684.
• Items must be merged by shared attributes, transitively — 721 Accounts Merge, 839 Similar String Groups.
• Constraints must be checked for consistency — 990 equality equations.
• Kruskal’s MST, where union-find is the mechanism that rejects cycle-forming edges.

The anti-cue — important: union-find only tracks whether things are connected. It cannot give you a path, a distance, or handle deletions. It also does not work naturally on directed graphs. If you need any of those, use BFS/DFS or topological sort instead.

Visual intuition

A union-find structure is a forest of parent pointers, so it draws as a directed graph. Watch two things: the taller tree always adopts the shorter one, and a find rewires the nodes it walks past.

dsuSix elements, five unions: how the forest actually changes shapeunion by rank + path halving

1class DSU:2    def __init__(self, n):3        self.parent = list(range(n))   # everyone is their own root4        self.size = [1] * n5 6    def find(self, x):7        while self.parent[x] != x:8            self.parent[x] = self.parent[self.parent[x]]   # PATH COMPRESSION9            x = self.parent[x]10        return x11 12    def union(self, a, b):13        ra, rb = self.find(a), self.find(b)14        if ra == rb: return False      # already together — a cycle edge15        if self.size[ra] < self.size[rb]: ra, rb = rb, ra16        self.parent[rb] = ra           # UNION BY SIZE: small under large17        self.size[ra] += self.size[rb]18        return True

sets6

setupEvery element starts as its own root — 6 separate sets. Union-find answers only two questions ("are these connected?" and "connect these"), and it answers them in effectively constant time, which is why it beats a graph traversal for dynamic connectivity.

Play‹›1/12⟲

The union(1, 2) step is the one to watch: neither 1 nor 2 is a root, so the operation is really between their roots 0 and 2 — and because both have rank 1, the tie is broken by attaching 2 under 0 and incrementing 0's rank to 2. Nothing else in the forest moves.

The implementation

Two optimisations turn a potentially $O(n)$ tree walk into effectively $O(1)$. Both are one line each and neither is optional in an interview.

dsu.py

class DSU:
    def __init__(self, n):
        self.parent = list(range(n))     # each node starts as its own root
        self.rank = [0] * n              # tree height, for union by rank
        self.components = n              # every node is its own component
 
    def find(self, x):
        while self.parent[x] != x:
            self.parent[x] = self.parent[self.parent[x]]   # path halving
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # ALREADY connected -> this edge is a cycle
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra              # attach the shorter tree under the taller
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.components -= 1
        return True                      # a genuine merge happened
 
    def connected(self, a, b):
        return self.find(a) == self.find(b)

The two optimisations, and why each matters

Path compression (here as path halving: parent[x] = parent[parent[x]]) flattens the tree as you walk it, so later find calls on the same chain are short. Without it, a degenerate chain makes find $O(n)$.

Union by rank attaches the shorter tree under the taller one, so trees never get needlessly deep. Without it, repeatedly unioning in the wrong order builds exactly the chain that path compression then has to repair.

Together they give an amortised cost of $O(\alpha(n))$ where $\alpha$ is the inverse Ackermann function — below 5 for any n you will ever see, so effectively constant. Saying “effectively $O(1)$, formally $O(\alpha(n))$ amortised” is the answer interviewers are listening for.

Path halving is written iteratively above, which avoids recursion-limit problems on large inputs. Full path compression via recursion (parent[x] = find(parent[x])) is equally acceptable and slightly more aggressive.

union returning a boolean is the whole trick

union(a, b) returning False means the two were already connected, so the edge you just tried to add closes a cycle. That single return value turns the structure into a cycle detector, and it is what solves LC 684 in four lines.

It also means you never need a separate connected() check before unioning — just look at what union tells you.

Dry run

DSU(6), then the edge list (0,1) (2,3) (1,2) (4,5) (0,5) (3,0) — the last one closing a cycle, which is the LC 684 question.

operation	roots found	returns	parent	rank	components
start	—	—	[0,1,2,3,4,5]	[0,0,0,0,0,0]	6
union(0,1)	0, 1	True	[0,0,2,3,4,5]	[1,0,0,0,0,0]	5
union(2,3)	2, 3	True	[0,0,2,2,4,5]	[1,0,1,0,0,0]	4
union(1,2)	0, 2	True	[0,0,0,2,4,5]	[2,0,1,0,0,0]	3
union(4,5)	4, 5	True	[0,0,0,2,4,4]	[2,0,1,0,1,0]	2
union(0,5)	0, 4	True	[0,0,0,2,0,4]	[2,0,1,0,1,0]	1
union(3,0)	0, 0	False	[0,0,0,0,0,4] — note index 3	[2,0,1,0,1,0]	1

Four things worth reading off that table:

• union(1,2) is not between 1 and 2. Both are non-roots, so the real operation is between their roots, 0 and 2. Their ranks are equal (both 1), so the tie-break attaches 2 under 0 and increments 0’s rank to 2 — the only path by which a rank ever grows.
• Rank is not depth after compression, and that is fine. After union(0,5), node 5 is two hops from the root but rank[0] is still 2. Rank is an upper bound used only to pick the adoption direction; letting it drift is what keeps union $O(1)$ work of its own.
• The failed union still changed the structure. union(3,0) returns False, yet parent[3] moved from 2 to 0 — path halving inside find(3). Reads are what flatten the tree, which is why the amortised bound needs the whole sequence of operations and not just the unions.
• False is the answer to LC 684. The edge (3,0) joins two nodes already in the same component, so it is the redundant one. No separate cycle detection, no DFS — the return value of union is the entire algorithm.

Sanity check on components: 6 elements, 5 successful merges, so 1 component. The sixth call merged nothing, and components correctly did not move.

Complexity, versus the alternatives

Task	Union-find	DFS / BFS
Count components (static graph)	$O(E \cdot \alpha)$	$O(V + E)$ — equally good
Connectivity query after each new edge	$O(\alpha)$ per query	$O(V + E)$ per query
Find a cycle-creating edge	$O(E \cdot \alpha)$	$O(V + E)$ with parent tracking
Shortest path	❌ impossible	✅ BFS
Handle edge deletion	❌ not supported	✅ rebuild
Directed graphs	❌ not naturally	✅

For a static graph, DFS is just as good and often simpler — LC 547 is perfectly solvable either way. Union-find wins decisively when the graph grows over time.

The variant map

Variant	What you read off	Canonical problem
Count components	dsu.components after all unions	547 · 323
Detect the cycle edge	The first union returning False	684
Count merges needed	components - 1	1319
Merge by shared attribute	Union items sharing a key, then group by root	721 Accounts Merge
Consistency check	Union equalities first, then test inequalities	990
Incremental islands	components maintained as land is added	305
Kruskal’s MST	Union edges in weight order, skipping cycles	MST

Union-find on strings and pairs

The structure indexes by integer, but problems often give strings (emails, variable names) or coordinates. Two standard adapters:

• Map to indices. Keep id = {} and assign id.setdefault(key, len(id)).
• Use a dict-based parent. parent = {} with parent.setdefault(x, x), which grows lazily.

For grid cells, flatten (r, c) to r * cols + c. LC 721 and 990 are mostly exercises in this bookkeeping, with the DSU itself unchanged.

Practice — real LeetCode problems

LC 547 — Number of Provinces · Medium

Problem. Given an n x n adjacency matrix isConnected where isConnected[i][j] == 1 means cities i and j are directly connected, return the number of provinces (connected components).

Constraints. 1 <= n <= 200, the matrix is symmetric with isConnected[i][i] == 1.

Examples. [[1,1,0],[1,1,0],[0,0,1]] gives 2 · [[1,0,0],[0,1,0],[0,0,1]] gives 3 · [[1]] gives 1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Begin with n singleton components and merge each connected pair. Because union only decrements when a genuine merge happens, the counter is exact at the end — no need to count distinct roots afterwards.

Time $O(n^2 \cdot \alpha(n))$ — dominated by reading the $n^2$ matrix. Space $O(n)$.

Two details:

• Upper triangle only. The matrix is symmetric, so j starts at i + 1. This also skips the diagonal, where isConnected[i][i] == 1 would attempt a self-union — harmless (find(i) == find(i), so union returns False) but pointless work.
• components beats counting roots. The alternative, len({find(i) for i in range(n)}), is also correct and is a fine fallback if you did not maintain a counter.

DFS is equally valid here and arguably simpler, since the graph is static: iterate nodes, and for each unvisited one run a DFS marking its whole component, counting how many DFS runs you start. Say this. Union-find is the better answer only if the follow-up adds edges over time.

Follow-ups you should expect: “Do it with DFS” — have it ready. “What if the input were an edge list instead of a matrix?” — $O(E \alpha)$ instead of $O(n^2)$, a strict improvement for sparse graphs. “What if cities could be disconnected later?” — union-find cannot un-merge; you would rebuild, or use a link-cut tree. “Return the size of the largest province?” — maintain a size array alongside rank.

LC 684 — Redundant Connection · Medium

Problem. A tree with n nodes had one extra edge added, creating exactly one cycle. Given the edge list, return the edge that can be removed so the graph is a tree again. If several answers exist, return the one appearing last in the input.

Constraints. 3 <= n <= 1000, nodes are labelled 1..n, no duplicate edges and no self-loops.

Examples. [[1,2],[1,3],[2,3]] gives [2,3] · [[1,2],[2,3],[3,4],[1,4],[1,5]] gives [1,4]

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

A tree on n nodes has exactly n - 1 edges. With one extra edge there is exactly one cycle, and the redundant edge is any edge on that cycle.

Union the edges in the given order. Every edge that merges two distinct components is a genuine tree edge. The first edge whose endpoints are already connected must close the cycle — and because we scan left to right, that first failure is also the last cycle edge in input order, which is exactly what the problem asks for.

Time $O(n \cdot \alpha(n))$. Space $O(n)$.

The tidy part is that “return the last valid answer” needs no extra work: the scan order gives it. If you had instead collected all cycle edges and picked the latest, you would be doing more work for the same result.

1-indexing is the practical trap: sizing the arrays n instead of n + 1 gives an IndexError on node n.

A DFS solution also exists — add edges one at a time and check whether a path already exists between the endpoints — but that is $O(n)$ per edge, so $O(n^2)$ overall. Union-find is the reason this is Medium rather than tedious.

Follow-ups you should expect: “What if the graph were directed (LC 685)?” — genuinely harder, and union-find alone is insufficient: you must also handle a node with two parents, so you consider up to two candidate edges and test each. Knowing that the directed version is a different problem is the useful insight. “What if there were multiple extra edges?” — return all edges whose union fails. “Detect whether a cycle exists at all?” — any failed union.

LC 1319 — Number of Operations to Make Network Connected · Medium

Problem. There are n computers and a list of connections (cables). You may unplug any cable and replug it elsewhere. Return the minimum number of such moves to connect all computers, or -1 if impossible.

Constraints. 1 <= n <= 10^5, 1 <= len(connections) <= min(n * (n - 1) / 2, 10^5), no duplicate connections.

Examples. n = 4, connections = [[0,1],[0,2],[1,2]] gives 1 · n = 6, connections = [[0,1],[0,2],[0,3],[1,2],[1,3]] gives 2 · n = 6, connections = [[0,1],[0,2],[0,3],[1,2]] gives -1

pch.exerciseTag pch.exerciseTitle

Editorial — approach, complexity, follow-ups

Two independent observations, and separating them is the whole solution:

1. Feasibility. A connected graph on n nodes needs at least n - 1 edges. Fewer cables than that and no rearrangement can help, so -1.
2. Cost. With enough cables, union everything and count the remaining components c. Joining c groups into one takes exactly c - 1 moves.

Why the moves are always available: if len(connections) >= n - 1 and there are c components, then some cables must be redundant (inside a component that already spans its nodes). Precisely those spares can be unplugged and used for the c - 1 bridges. So the count of components alone determines the answer — you never need to identify which cables are redundant.

Time $O(E \cdot \alpha(n))$. Space $O(n)$.

(6, [[0,1],[0,2],[0,3],[1,2]]) returning -1 is the feasibility case: 4 cables for 6 computers, and 5 are required.

Follow-ups you should expect: “Prove the spare cables always exist” — the counting argument above; this is the likely probe. “Which cables would you move?” — any edge whose union returned False. “What if cables had lengths and you wanted minimum total?” — that is Kruskal’s MST, with union-find as the engine. “Could you use DFS?” — yes, count components with DFS and subtract one; union-find is not required for a static graph.

LeetCode problem set

Generated from the problem database, so each entry carries its sheet membership and reported companies. Tick them off as you go — progress is saved in this browser, and the Export button writes it to a file you can keep.

LC 990 — order matters, and LC 128 — do not over-engineer

LC 990: you must process all the == equations before testing any !=. Interleaving them can pass an inequality that a later equality would have contradicted. Two passes, in that order.

LC 128: union-find works, but the intended solution is simpler — put everything in a set, then for each value that has no predecessor (v - 1 not in s) walk upward counting. Also $O(n)$, far less code. This is a useful reminder that recognising a pattern is not the same as the pattern being the best tool. Union-find is a hammer; not every connectivity-flavoured problem is a nail.

8 problems

0 easy8 medium0 hard

Work down the ladder. Tick each problem off as you go — progress is saved in this browser, and the Export button in the filter bar writes it to a file you can keep.

AllEasyMediumHard

Unsolved onlyExportImportReset

• ○128Longest Consecutive SequencemediumSolvable with union-find, but a hash set is simpler and also $O(n)$NeetCode 150Blind 75LeetCode Top Interview 150
• ○261Graph Valid TreepremiummediumNeetCode 150Blind 75
• ○399Evaluate DivisionmediumLeetCode Top Interview 150
• ○547Number of ProvincesmediumComponent counting; DFS is equally fine here
• ○684Redundant ConnectionmediumThe first failed `union` is the cycle edgeNeetCode 150
• ○721Accounts MergemediumUnion accounts sharing an email; map strings to indices, then group by root
• ○990Satisfiability of Equality EquationsmediumUnion all `==` first, **then** check every `!=`
• ○1319Number of Operations to Make Network ConnectedmediumCable count for feasibility, component count for cost

Interview follow-ups

They ask	What they’re checking	The answer
“Union-find or DFS?”	Judgement	DFS is equally good on a static graph; union-find wins when edges arrive incrementally and you answer queries between them
“What’s the complexity?”	Precision	$O(\alpha(n))$ amortised per operation with both optimisations — effectively constant, since $\alpha(n) < 5$ for any realistic n
“Name the two optimisations”	Whether you know why it is fast	Path compression (flatten during find) and union by rank/size (attach shorter under taller). Either alone is worse
“How do you detect a cycle?”	The key idiom	A union that finds both endpoints already sharing a root
“Can you delete an edge?”	Knowing the limits	No — union-find is merge-only. Rebuild, or use a link-cut tree
“Does it work on directed graphs?”	Limits again	Not naturally; use topological sort or DFS colouring for directed cycles
“Keys are strings, not ints”	Practical adaptation	Map to indices with a dict, or use a dict-based parent that grows lazily
“Track component sizes?”	Extensibility	Keep a size array and add it during union — cheap and often asked

Edge-case checklist

• Single node — n = 1; one component, zero operations.
• No edges at all — n components; LC 1319 returns -1 unless n == 1.
• All nodes already connected — components == 1; answer 0.
• Self-loops — union(i, i) returns False harmlessly, but do not count it as a cycle if the problem excludes self-loops.
• Duplicate edges — the second one fails its union; whether that counts as a “cycle” depends on the problem.
• 1-indexed nodes — size the arrays n + 1 (LC 684). A frequent IndexError.
• Not enough edges — LC 1319’s feasibility check must come first.
• Ordering of constraints — LC 990 needs all equalities before any inequality.

Self-check

pch.quizTag Union-find — self-check

1. What does `union(a, b)` returning False tell you?

   A That the union failed and must be retried B That a and b were already in the same component — so the edge you just tried to add closes a cycle C That a or b is out of range D That the two trees had equal rank
   pch.quizShowAnswer

   B — That a and b were already in the same component — so the edge you just tried to add closes a cycle — That single return value is the whole solution to LC 684: the first edge whose union returns False is the redundant one. It also means you never need a separate `connected()` call before unioning.

2. In the dry run, `union(1, 2)` merges roots 0 and 2, both of rank 1. What happens to the ranks?

   A Both increment B 2 is attached under 0 and rank[0] becomes 2 — a rank only ever grows when two equal-rank roots merge C Neither changes D rank[2] becomes 0
   pch.quizShowAnswer

   B — 2 is attached under 0 and rank[0] becomes 2 — a rank only ever grows when two equal-rank roots merge — Equal ranks are the only case where the resulting tree is genuinely taller, which is exactly why that is the only case that increments. Unequal ranks attach the shorter under the taller and the taller's rank is already correct.

3. `union(3, 0)` returned False, yet `parent[3]` changed from 2 to 0. Why?

   A A bug — a failed union must not mutate B Path halving inside `find(3)`: reads are what flatten the forest, which is why the amortised bound is over the whole operation sequence rather than over unions alone C Because rank[0] was larger D Because components was already 1
   pch.quizShowAnswer

   B — Path halving inside `find(3)`: reads are what flatten the forest, which is why the amortised bound is over the whole operation sequence rather than over unions alone — This is the point most explanations skip. The compression work is paid by `find`, so a workload of many queries and few unions gets progressively cheaper as the trees flatten.

4. What is the honest complexity statement for m operations on n elements?

   A O(1) per operation, worst case B Effectively O(1) — formally O(α(n)) amortised, where α is the inverse Ackermann function and is below 5 for any realistic n C O(log n) per operation D O(n) per operation with compression
   pch.quizShowAnswer

   B — Effectively O(1) — formally O(α(n)) amortised, where α is the inverse Ackermann function and is below 5 for any realistic n — Saying 'effectively constant, formally O(α(n)) amortised' is the phrasing interviewers listen for. Claiming a worst-case O(1) per operation is wrong; claiming O(log n) means you left out one of the two optimisations.

5. When is DFS the better choice over union-find?

   A Never — union-find is strictly better B When the graph is static and you need one pass (counting components is O(V+E) either way), or when you need paths, distances, direction, or edge deletion — none of which union-find supports C Only on trees D When the graph is dense
   pch.quizShowAnswer

   B — When the graph is static and you need one pass (counting components is O(V+E) either way), or when you need paths, distances, direction, or edge deletion — none of which union-find supports — Union-find wins decisively when edges arrive over time and connectivity is queried between arrivals. For a fixed graph it is a lateral move, and it cannot give you a shortest path at all.

6. You size the arrays `list(range(n))` for a problem with 1-indexed nodes up to n (LC 684). What happens?

   A Nothing, Python handles it B IndexError on node n — 1-indexed inputs need n + 1 slots C Node 0 is double-counted D The component count is off by one
   pch.quizShowAnswer

   B — IndexError on node n — 1-indexed inputs need n + 1 slots — Boring, and it accounts for a large share of failed submissions on this pattern. Read the constraints for the indexing base before writing the constructor. (If you size n+1 for 1-indexed data, remember the unused slot 0 counts as its own component.)

Recall card

• Cue — connectivity questions where edges arrive over time: “are these two connected”, “how many groups”, “which edge creates a cycle”, “merge these accounts”.
• Structure — parent array plus rank; components counter maintained by union.
• find — walk to the root, halving as you go (parent[x] = parent[parent[x]]).
• union — find both roots; equal roots → return False (this edge is a cycle); else attach the lower-rank root under the higher, incrementing rank only on a tie, decrement components, return True.
• Cost — effectively $O(1)$ per operation; formally $O(\alpha(n))$ amortised. Both optimisations are required for that — either one alone leaves $O(\log n)$.
• Cannot do — shortest paths, directed relationships, edge deletion. Those are DFS/BFS or a rebuild.
• Watch — 1-indexed inputs need n + 1 slots; feasibility checks (LC 1319) come before the merging; equality constraints before inequalities (LC 990).

Recap

• Union-find maintains connectivity incrementally in effectively $O(1)$ — formally $O(\alpha(n))$ amortised with both optimisations.
• Path compression plus union by rank are both required; either alone leaves a bad worst case.
• union returning False means a cycle — that boolean solves LC 684 outright.
• Maintain a components counter and decrement per successful merge; no final root-counting pass needed.
• “Join c groups” always costs c - 1 merges.
• For static graphs, DFS is equally good — say so. Union-find’s edge is incremental edges and repeated queries.
• It cannot give paths or distances, cannot delete edges, and does not suit directed graphs. Know those limits before reaching for it.

Next: Shortest Paths — Dijkstra, Bellman-Ford and Floyd-Warshall, for when edges carry weights and you need distances rather than just connectivity.