Pattern #19

Union Find

Advanced

Dynamic connectivity: merge components and query same-set fast.

When to use

Online unions of elements and frequent 'are a and b connected?' queries, or counting components after merges.

Recognition cues

Number of provinces / graph valid tree
Accounts merge / redundant connection
Union by rank + path compression

Common pitfalls

Forgetting path compression or union by rank (slow chains)
1-index vs 0-index parents
Unioning without checking already-connected (miss cycle detection)

90-second recognition drill

Which pattern fits best?

Number of provinces / graph valid tree
Accounts merge / redundant connection
Union by rank + path compression

GreedyLinked List ManipulationUnion FindDifference Array

Interactive

Mental model

A full worked walkthrough of the invariant. Pause, scrub the dots, or use ← →. Aim to narrate each step yourself.

Step 1 of 8

components = 5

Five elements; each is its own parent.

How to think about it

Each element points to a parent; roots represent components. find flattens paths; union links roots (by rank/size). If find(a)==find(b) before union, adding the edge would create a cycle.

Template shapes

Shape	Core move	Notes
Connectivity	union + find	Components count
Cycle on undirected	Skip if same root	Redundant edge
Weighted / attrs	Store extra on root	Merge accounts

Complexity baseline

Nearly O(α(n)) per op with path compression + union by rank. Space O(n).

From template to problem

parent[i]=i; rank[i]=0; components=n.
find with path compression.
union: link smaller rank under larger; decrement components if merged.
Query connected via find equality.

Template

Same skeleton in TypeScript, Python, and C#. Adapt the invariant; keep the structure.

Union Find · Template

/** Union-Find template: path compression + union by rank. */
export class UnionFind {
  parent: number[];
  rank: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]!);
    return this.parent[x]!;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra]! < this.rank[rb]!) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]!++;
    this.components--;
    return true;
  }
}

/** Union-Find template: path compression + union by rank. */
export class UnionFind {
  parent: number[];
  rank: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.components = n;
  }
  find(x: number): number {
    if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]!);
    return this.parent[x]!;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.rank[ra]! < this.rank[rb]!) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    if (this.rank[ra] === this.rank[rb]) this.rank[ra]!++;
    this.components--;
    return true;
  }
}

Path

Start path View in problem browser →

#ProblemTypeDifficultyDone