Basics
The idea behind the pattern, why it is correct, and the clues in a question that point to it.
1.1Core idea
What the pattern does, in plain words.
Every element points to a parent; the root names the group. Union joins two roots. Path compression and union by size keep trees almost flat.
Each group is a tree whose root names the group. find walks up to the root; union hangs one root under the other. Path halving and union by size keep the trees almost flat, so each operation is close to O(1) in practice.
Typical cost: ≈ O(α(n)) per operation, effectively constant
1.2Recognition signals
If a question has one of these clues, try this pattern first.
Question
A classic interview problem from this family. Read it carefully and plan the approach before writing any code.
2.1Redundant Connection
The problem statement, then the plan you would say out loud.
A tree with one extra edge added. Return the edge that creates the cycle.
Plan before you code
- Process edges in order.
- If both ends are already in the same group, this edge closes a cycle.
Detailed answer
First the reusable template, then the worked solution built from it and a walk through it one step at a time.
3.1Template
Memorise this shape. Most problems in this family are this code plus one twist.
Disjoint set union
1class DSU {2 parent: number[];3 size: number[];4 constructor(n: number) {5 this.parent = Array.from({ length: n }, (_, i) => i);6 this.size = new Array<number>(n).fill(1);7 }8 find(x: number): number {9 while (this.parent[x] !== x) {10 this.parent[x] = this.parent[this.parent[x]]; // path halving11 x = this.parent[x];12 }13 return x;14 }15 union(a: number, b: number): boolean {16 let ra = this.find(a), rb = this.find(b);17 if (ra === rb) return false;18 if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];19 this.parent[rb] = ra;20 this.size[ra] += this.size[rb];21 return true;22 }23}1class DSU(n: Int) {2 private val parent = IntArray(n) { it }3 private val size = IntArray(n) { 1 }4 5 fun find(x0: Int): Int {6 var x = x07 while (parent[x] != x) {8 parent[x] = parent[parent[x]] // path halving9 x = parent[x]10 }11 return x12 }13 14 fun union(a: Int, b: Int): Boolean {15 var ra = find(a)16 var rb = find(b)17 if (ra == rb) return false18 if (size[ra] < size[rb]) { val t = ra; ra = rb; rb = t }19 parent[rb] = ra20 size[ra] += size[rb]21 return true22 }23}1class DSU {2 int[] parent, size;3 4 DSU(int n) {5 parent = new int[n];6 size = new int[n];7 for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; }8 }9 10 int find(int x) {11 while (parent[x] != x) {12 parent[x] = parent[parent[x]]; // path halving13 x = parent[x];14 }15 return x;16 }17 18 boolean union(int a, int b) {19 int ra = find(a), rb = find(b);20 if (ra == rb) return false;21 if (size[ra] < size[rb]) { int t = ra; ra = rb; rb = t; }22 parent[rb] = ra;23 size[ra] += size[rb];24 return true;25 }26}- Each element starts as its own group.
- Find the root, halving the path as we go.
- Attach the smaller tree under the bigger root.
3.2Solution
Strict TypeScript, type-checked and tested.
Redundant Connection
1function findRedundantConnection(edges: [number, number][]): number[] {2 const dsu = new DSU(edges.length + 1);3 for (const [a, b] of edges) {4 if (!dsu.union(a, b)) return [a, b];5 }6 return [];7}1fun findRedundantConnection(edges: List<Pair<Int, Int>>): List<Int> {2 val dsu = DSU(edges.size + 1)3 for ((a, b) in edges) {4 if (!dsu.union(a, b)) return listOf(a, b)5 }6 return emptyList()7}1static int[] findRedundantConnection(int[][] edges) {2 DSU dsu = new DSU(edges.length + 1);3 for (int[] e : edges) {4 if (!dsu.union(e[0], e[1])) return e;5 }6 return new int[0];7}Step by step
- Every node starts in its own group.
- Both ends already joined? This edge closes the cycle.
Complexity: O(n α(n)) time, O(n) space
Q&A
What interviewers ask once your code works, and problems to try on your own.
4.1Interview questions
Answer out loud, then open.
Union-find or BFS for connectivity?
Why union by size?
Can it handle deleting edges?
4.2Solo practice
Try these without looking; open the hint only when stuck.
Hint
Add cells in height order until start and end connect.
Extra depth
More fully worked problems in the same family, and the mistakes that cost offers.
5.12 more worked problems
Each one: the problem, the plan, the code and its cost.
Show detailsHide details
Number of Provinces
Given an adjacency matrix of cities, count connected groups.
- Start with n groups.
- Every successful union merges two groups into one.
1function findCircleNum(isConnected: number[][]): number {2 const n = isConnected.length;3 const dsu = new DSU(n);4 let groups = n;5 for (let i = 0; i < n; i++) {6 for (let j = i + 1; j < n; j++) {7 if (isConnected[i][j] && dsu.union(i, j)) groups--;8 }9 }10 return groups;11}Complexity: O(n² α(n)) time
Accounts Merge
Accounts sharing any email belong to one person. Merge them.
- Map each email to the first account that had it.
- When an email repeats, union the two accounts.
- Group emails by their account's root.
1function accountsMerge(accounts: string[][]): string[][] {2 const dsu = new DSU(accounts.length);3 const owner = new Map<string, number>();4 accounts.forEach(([, ...emails], i) => {5 for (const e of emails) {6 const j = owner.get(e);7 if (j === undefined) owner.set(e, i);8 else dsu.union(i, j);9 }10 });11 const groups = new Map<number, string[]>();12 for (const [e, i] of owner) {13 const root = dsu.find(i);14 if (!groups.has(root)) groups.set(root, []);15 groups.get(root)!.push(e);16 }17 return [...groups].map(([root, emails]) => [accounts[root][0], ...emails.sort()]);18}Complexity: O(E log E) for E emails (sorting dominates)
5.2Traps
Bugs and misreadings that come up again and again with this pattern.
Show detailsHide details
- Comparing elements instead of roots
- Forgetting path compression on deep inputs