Engineering Notes
Home/Algorithms & Coding Interviews/Graphs/Union-Find
Algorithms & Coding Interviews · Graphs

Union-Find

Union-find tracks merging groups with near-constant-time find and union. Learn the parent-array structure, path compression and union by size, where it beats DFS (incremental edges, cycle-closing edges, Kruskal), and watch the parent array evolve and a redundant edge get caught.

🧮 Algorithms & Coding Interviews● Intermediate⏱ 13 min read▶ 2 interactive🛠️ 4 exercises

🎯 What you'll learn

  • find, union and the parent array
  • Path compression and union by size (α(n))
  • Components, cycle detection and Kruskal's MST
  • Six LeetCode problems with animated walkthroughs

📚 Before you start

Part 1The Pattern

Union-find (disjoint set union, DSU) tracks which items belong to the same group while groups keep merging. It supports two operations: find(x) returns the representative ("root") of x's group, and union(a, b) merges two groups. With path compression and union by size/rank, both run in α(n) amortized time, effectively constant (α grows so slowly it's ≤ 4 for any input that fits in the universe).

Each group is a tree; find follows parent pointers to the root
Each group is a tree; find follows parent pointers to the root

1When to Use It

  • "are these two nodes connected?" asked repeatedly while edges are added over time
  • count connected components / groups (provinces, islands with dynamic land, merging accounts)
  • detect the edge that creates a cycle in an undirected graph (Redundant Connection, valid tree)
  • Kruskal's minimum spanning tree: add cheapest edges that join different components
  • equations/relations: "a == b", "a != b" consistency checks

DFS/BFS can also count components, but union-find shines when edges arrive incrementally and you need answers after each one.

2Template

typescript
class DSU {
  parent: number[];
  size: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n;
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }
}

function dsuDemo(n: number, edges: number[][]): any[] {
  const d = new DSU(n);
  const merged = edges.map(([a, b]) => d.union(a, b));
  return [merged, d.components];
}
python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    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
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

def dsu_demo(n, edges):
    d = DSU(n)
    merged = [d.union(a, b) for a, b in edges]
    return [merged, d.components]
  • Path compression (parent[x] = parent[parent[x]], or full compression with recursion) flattens trees during finds.
  • Union by size attaches the smaller tree under the larger, keeping trees shallow.
  • union returning False means the endpoints were already connected: in an undirected graph, that edge closes a cycle.

3Kruskal's Minimum Spanning Tree

Sort edges by weight; for each edge, union its endpoints if they're in different components and add its weight. Stop after n − 1 edges. O(E log E) for the sort; union-find makes each cycle check near-constant.

Under the HoodWhy α(n)▾

Without either optimization a sequence of unions can build a chain, making find O(n). Union by size alone guarantees trees of height O(log n) (a node's tree at least doubles in size every time its depth increases). Adding path compression gives the inverse-Ackermann bound proved by Tarjan: amortized O(α(n)) per operation. In interviews, "near O(1) amortized, with path compression and union by rank" is the expected answer.

⚠️ Common Pitfalls

  1. Comparing parent[a] == parent[b] instead of find(a) == find(b).
  2. Forgetting path compression or union by size, leading to O(n) chains.
  3. Using union-find on directed graphs for cycle detection: it only handles undirected connectivity.
  4. Mapping non-integer items (emails, coordinates): give each a numeric id or use a dict-based parent map.
  5. Off-by-one with 1-indexed nodes: allocate n + 1 slots.

📋 Quick Reference

text
parent[i] = i; find: while parent[x] != x: parent[x] = parent[parent[x]]; x = parent[x]
union: ra, rb = find(a), find(b); if same → False (cycle); attach smaller under larger
components: start n, decrement per successful union
Kruskal: sort edges; add if union succeeds; stop at n-1 edges
α(n) ≈ O(1) amortized
Part 2Interview Problems

Six problems: counting components, catching the cycle-closing edge, validating trees, grouping by shared identifiers, and Kruskal's minimum spanning tree.

1Number of Connected Components in an Undirected Graph (LeetCode 323)

🟠 Medium. Given n nodes and an edge list, return the number of connected components.

text
n = 5, [[0,1],[1,2],[3,4]] → 2

Approach. Start with n components; each successful union merges two of them.

Complexity. O(E · α(n)) time, O(n) space.

typescript
class DSU {
  parent: number[];
  size: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n;
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }
}

function countComponents(n: number, edges: number[][]): number {
  const d = new DSU(n);
  for (const [a, b] of edges) d.union(a, b);
  return d.components;
}
python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    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
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

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

2Redundant Connection (LeetCode 684)

🟠 Medium. A tree with one extra edge added is given as an edge list (nodes 1..n). Return the edge that can be removed to make it a tree (the last such edge in the input).

text
[[1,2],[1,3],[2,3]] → [2,3]

Approach. Union the endpoints of each edge in order; the first edge whose endpoints are already connected closes the cycle and is the answer.

Complexity. O(n · α(n)).

typescript
class DSU {
  parent: number[];
  size: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n;
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }
}

function findRedundantConnection(edges: number[][]): number[] {
  const d = new DSU(edges.length + 1);
  for (const [a, b] of edges) if (!d.union(a, b)) return [a, b];
  return [];
}
python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    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
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

def find_redundant_connection(edges):
    d = DSU(len(edges) + 1)
    for a, b in edges:
        if not d.union(a, b):
            return [a, b]
    return []

3Graph Valid Tree (LeetCode 261)

🟠 Medium. Given n nodes and undirected edges, return true if they form a valid tree.

text
n = 5, [[0,1],[0,2],[0,3],[1,4]] → true

Approach. A tree has exactly n − 1 edges and no cycle. Check the edge count first, then union every edge; any failed union means a cycle.

Complexity. O(n · α(n)).

typescript
class DSU {
  parent: number[];
  size: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n;
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }
}

function validTree(n: number, edges: number[][]): boolean {
  if (edges.length !== n - 1) return false;
  const d = new DSU(n);
  return edges.every(([a, b]) => d.union(a, b));
}
python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    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
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

def valid_tree(n, edges):
    if len(edges) != n - 1:
        return False
    d = DSU(n)
    return all(d.union(a, b) for a, b in edges)

4Number of Provinces (LeetCode 547)

🟠 Medium. isConnected[i][j] = 1 if cities i and j are directly connected. Return the number of provinces (connected groups).

text
[[1,1,0],[1,1,0],[0,0,1]] → 2

Approach. Union every connected pair (upper triangle of the matrix) and count components. DFS over the matrix works equally well.

Complexity. O(n² · α(n)).

typescript
class DSU {
  parent: number[];
  size: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n;
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }
}

function findCircleNum(isConnected: number[][]): number {
  const n = isConnected.length, d = new DSU(n);
  for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++) if (isConnected[i][j]) d.union(i, j);
  return d.components;
}
python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    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
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

def find_circle_num(is_connected):
    n = len(is_connected)
    d = DSU(n)
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j]:
                d.union(i, j)
    return d.components

5Accounts Merge (LeetCode 721)

🟠 Medium. Each account is [name, email1, email2, …]. Accounts sharing any email belong to the same person. Merge them; return each person's name followed by their sorted emails.

text
two John accounts sharing johnsmith@mail.com merge into one

Approach. Give every email an id. Union all emails within one account (with its first email). Then group emails by root, sort each group, and prepend the owner's name.

Complexity. O(E log E) for E emails (sorting dominates).

typescript
class DSU {
  parent: number[];
  size: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n;
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }
}

function accountsMerge(accounts: string[][]): string[][] {
  const ids = new Map<string, number>(), owner = new Map<string, string>();
  for (const acc of accounts) for (const email of acc.slice(1)) {
    if (!ids.has(email)) { ids.set(email, ids.size); owner.set(email, acc[0]); }
  }
  const d = new DSU(ids.size);
  for (const acc of accounts) for (const email of acc.slice(2)) d.union(ids.get(acc[1])!, ids.get(email)!);
  const groups = new Map<number, string[]>();
  for (const [email, i] of ids) {
    const r = d.find(i);
    if (!groups.has(r)) groups.set(r, []);
    groups.get(r)!.push(email);
  }
  return [...groups.values()].map((g) => [owner.get(g[0])!, ...g.sort()]);
}
python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    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
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

def accounts_merge(accounts):
    ids, owner = {}, {}
    for acc in accounts:
        for email in acc[1:]:
            if email not in ids:
                ids[email] = len(ids)
                owner[email] = acc[0]
    d = DSU(len(ids))
    for acc in accounts:
        first = ids[acc[1]]
        for email in acc[2:]:
            d.union(first, ids[email])
    groups = {}
    for email, i in ids.items():
        groups.setdefault(d.find(i), []).append(email)
    return [[owner[g[0]]] + sorted(g) for g in groups.values()]

6Min Cost to Connect All Points (LeetCode 1584)

🟠 Medium. Points on a plane; connecting two costs their Manhattan distance. Return the minimum cost to connect all points (a minimum spanning tree).

text
[[0,0],[2,2],[3,10],[5,2],[7,0]] → 20

Approach. Kruskal: build all O(n²) edges, sort by cost, and add each edge whose endpoints are in different components until n − 1 edges are added. (Prim's algorithm with an O(n²) array scan is also great here since the graph is complete.)

Complexity. O(n² log n) with Kruskal, O(n²) with array-based Prim.

typescript
class DSU {
  parent: number[];
  size: number[];
  components: number;
  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.size = new Array(n).fill(1);
    this.components = n;
  }
  find(x: number): number {
    while (this.parent[x] !== x) {
      this.parent[x] = this.parent[this.parent[x]];
      x = this.parent[x];
    }
    return x;
  }
  union(a: number, b: number): boolean {
    let ra = this.find(a), rb = this.find(b);
    if (ra === rb) return false;
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra];
    this.parent[rb] = ra;
    this.size[ra] += this.size[rb];
    this.components--;
    return true;
  }
}

function minCostConnectPoints(points: number[][]): number {
  const n = points.length, edges: [number, number, number][] = [];
  for (let i = 0; i < n; i++) for (let j = i + 1; j < n; j++)
    edges.push([Math.abs(points[i][0] - points[j][0]) + Math.abs(points[i][1] - points[j][1]), i, j]);
  edges.sort((a, b) => a[0] - b[0]);
  const d = new DSU(n);
  let total = 0, used = 0;
  for (const [cost, i, j] of edges) {
    if (d.union(i, j)) { total += cost; if (++used === n - 1) break; }
  }
  return total;
}
python
class DSU:
    def __init__(self, n):
        self.parent = list(range(n))
        self.size = [1] * n
        self.components = n

    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
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra                               # attach smaller under larger
        self.size[ra] += self.size[rb]
        self.components -= 1
        return True

def min_cost_connect_points(points):
    n = len(points)
    edges = sorted((abs(points[i][0] - points[j][0]) + abs(points[i][1] - points[j][1]), i, j)
                   for i in range(n) for j in range(i + 1, n))
    d, total, used = DSU(n), 0, 0
    for cost, i, j in edges:
        if d.union(i, j):
            total += cost
            used += 1
            if used == n - 1:
                break
    return total

🧠 Key takeaways

  • DSU = find (root of a group) + union (merge two groups).
  • Path compression + union by size → amortized α(n) ≈ O(1).
  • A failed union on an undirected edge means that edge closes a cycle.
  • Use it for incremental connectivity, component counts and Kruskal's MST.

🛠️ Practice exercises

Each exercise is a file in this topic folder. Code exercises are self-checking: run them and make the checks pass.

#1
algo_union_find_exercise_1.py
TSPY
#2
algo_union_find_exercise_2.py
TSPY

✅ Check yourself

Answer the questions — feedback is instant.

1. union(a, b) returns false. What does that tell you?
Same root.
2. Which pair of optimizations gives near-constant time?
Tarjan's bound.
3. Number of components after processing all edges equals…
Each success merges two.
4. Is union-find suitable for detecting cycles in a DIRECTED graph?
It models undirected connectivity.

Source: algo_union_find_theory_1.md, algo_union_find_theory_2.md · generated by tools/build_lessons.py