# Union-Find — Part 2: Interview Problems

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

## 1. Number 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
```

## 2. Redundant 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 []
```

## 3. Graph 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)
```

## 4. Number 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
```

## 5. Accounts 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()]
```

## 6. Min 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
```