/Projects
Coding patterns · 11 of 15

Union-find

Merge groups and ask 'same group?' almost instantly.

PracticeCoding patternTier 2 · MechanismsApply15 minCore engineering

You will be able to: spot union-find from a problem statement, and code it from memory.

Interview prepCoding patterns

Study with AI

≈ O(α(n)) per operation, effectively constant Watch as reels
Part 1 of 5

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.

Why it works

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.

Connected components that change as edges arriveDetect a redundant edge (cycle in undirected graph)Group accounts or equivalencesKruskal's minimum spanning tree
Part 2 of 5

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.

Problem

A tree with one extra edge added. Return the edge that creates the cycle.

Plan before you code

  1. Process edges in order.
  2. If both ends are already in the same group, this edge closes a cycle.
Part 3 of 5

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

disjoint-set-union.tsTypeScript
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}
23 linesUTF-8TypeScript
  1. Each element starts as its own group.
  2. Find the root, halving the path as we go.
  3. Attach the smaller tree under the bigger root.

3.2Solution

Strict TypeScript, type-checked and tested.

Redundant Connection

redundant-connection.tsTypeScript
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}
7 linesUTF-8TypeScript

Step by step

  1. Every node starts in its own group.
  2. Both ends already joined? This edge closes the cycle.

Complexity: O(n α(n)) time, O(n) space

Part 4 of 5

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?
Union-find shines when edges arrive over time and you keep asking 'are these connected?'. BFS is simpler for one question on a fixed graph.
Why union by size?
Hanging the smaller tree under the bigger one keeps the depth logarithmic, even without path compression.
Can it handle deleting edges?
Not efficiently. If edges are removed, process the operations in reverse as additions, or use a different structure.

4.2Solo practice

Try these without looking; open the hint only when stuck.

HardSwim in Rising Water
Hint

Add cells in height order until start and end connect.

Part 5 of 5

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
Medium

Number of Provinces

Given an adjacency matrix of cities, count connected groups.

  1. Start with n groups.
  2. Every successful union merges two groups into one.
number-provinces.tsTypeScript
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}
11 linesUTF-8TypeScript

Complexity: O(n² α(n)) time

Medium

Accounts Merge

Accounts sharing any email belong to one person. Merge them.

  1. Map each email to the first account that had it.
  2. When an email repeats, union the two accounts.
  3. Group emails by their account's root.
accounts-merge.tsTypeScript
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}
18 linesUTF-8TypeScript

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
AI Engineer · Union-find