Union-Find (Disjoint Set Union) — The Complete Guide

Each element starts as its own group (parent = itself).

find(x): Follow parent pointers until you reach the root.
          The root is the "representative" of the group.

union(a, b): Find the roots of a and b.
             If different, make one root point to the other.
             Now both groups are merged.

Example: union(1, 2), union(3, 4), union(2, 3)

Step 1: union(1, 2)     Step 2: union(3, 4)     Step 3: union(2, 3)
  1 ← 2                   1 ← 2   3 ← 4          1 ← 2
                                                    ↑
                                                    3 ← 4

find(1) = 1, find(4) = 1 → same group ✓

Two optimizations make this nearly O(1):
  Path Compression: During find(), point every node directly to the root.
  Union by Rank:    Attach the shorter tree under the taller tree.

class UnionFind {
  parent: number[];
  rank: number[];
  count: number;

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i);
    this.rank = new Array(n).fill(0);
    this.count = n; // each element is its own component
  }

  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // path compression
    }
    return this.parent[x];
  }

  union(a: number, b: number): boolean {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return false; // already same group

    if (this.rank[rootA] < this.rank[rootB]) {
      this.parent[rootA] = rootB;
    } else if (this.rank[rootA] > this.rank[rootB]) {
      this.parent[rootB] = rootA;
    } else {
      this.parent[rootB] = rootA;
      this.rank[rootA]++;
    }

    this.count--;
    return true;
  }

  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}
// Variation: use "size" instead of "rank" (union by size)
// — attach smaller tree under larger, track component sizes.

function countComponents(n: number, edges: number[][]): number {
  const uf = new UnionFind(n);

  for (const [u, v] of edges) {
    uf.union(u, v);
  }

  return uf.count;
}
// Each union that merges two different components decrements count.
// Final count = number of connected components.
// When to use: Number of Provinces, Number of Islands (with coordinate mapping),
// Number of Connected Components

function findRedundantConnection(edges: number[][]): number[] {
  const n = edges.length;
  const uf = new UnionFind(n + 1); // 1-indexed nodes

  for (const [u, v] of edges) {
    if (!uf.union(u, v)) {
      return [u, v]; // this edge creates a cycle!
    }
  }

  return []; // no cycle found
}
// Key insight: if find(u) === find(v) BEFORE adding edge (u, v),
// then u and v are already connected — adding this edge creates a cycle.
// When to use: Redundant Connection, Graph Valid Tree, Kruskal's MST

function numIslands(grid: string[][]): number {
  const rows = grid.length, cols = grid[0].length;
  const uf = new UnionFind(rows * cols);
  let waterCount = 0;

  const dirs = [[0, 1], [1, 0]]; // only right and down to avoid duplicates

  for (let r = 0; r < rows; r++) {
    for (let c = 0; c < cols; c++) {
      if (grid[r][c] === '0') {
        waterCount++;
        continue;
      }
      const idx = r * cols + c;
      for (const [dr, dc] of dirs) {
        const nr = r + dr, nc = c + dc;
        if (nr < rows && nc < cols && grid[nr][nc] === '1') {
          uf.union(idx, nr * cols + nc);
        }
      }
    }
  }

  return uf.count - waterCount;
}
// Map (row, col) → row * cols + col for 1D indexing.
// Only check right and down neighbors to avoid double-counting.
// Subtract water cells from the component count.

function minCostConnectPoints(points: number[][]): number {
  const n = points.length;
  const edges: [number, number, number][] = []; // [weight, u, v]

  // Generate all edges with Manhattan distance
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      const dist = Math.abs(points[i][0] - points[j][0])
                 + Math.abs(points[i][1] - points[j][1]);
      edges.push([dist, i, j]);
    }
  }

  // Sort edges by weight (ascending)
  edges.sort((a, b) => a[0] - b[0]);

  const uf = new UnionFind(n);
  let totalCost = 0;
  let edgesUsed = 0;

  for (const [weight, u, v] of edges) {
    if (uf.union(u, v)) {
      totalCost += weight;
      edgesUsed++;
      if (edgesUsed === n - 1) break; // MST has n-1 edges
    }
  }

  return totalCost;
}
// Time: O(E log E) for sorting + O(E × α(n)) for unions
// Space: O(E + n)
// Key: Kruskal's = sort edges + Union-Find to avoid cycles.
// MST is complete when we've added n-1 edges.

function accountsMerge(accounts: string[][]): string[][] {
  const uf = new UnionFind(accounts.length);
  const emailToAccount = new Map<string, number>(); // email → account index

  // Union accounts that share emails
  for (let i = 0; i < accounts.length; i++) {
    for (let j = 1; j < accounts[i].length; j++) {
      const email = accounts[i][j];
      if (emailToAccount.has(email)) {
        uf.union(i, emailToAccount.get(email)!);
      } else {
        emailToAccount.set(email, i);
      }
    }
  }

  // Group emails by root account
  const groups = new Map<number, Set<string>>();
  for (let i = 0; i < accounts.length; i++) {
    const root = uf.find(i);
    if (!groups.has(root)) groups.set(root, new Set());
    for (let j = 1; j < accounts[i].length; j++) {
      groups.get(root)!.add(accounts[i][j]);
    }
  }

  // Build result
  const result: string[][] = [];
  for (const [root, emails] of groups) {
    result.push([accounts[root][0], ...[...emails].sort()]);
  }

  return result;
}
// Time: O(n × k × α(n) + E log E) where k = emails per account
// Key: Union accounts (not emails) — use email as the "bridge" to find
// which accounts should be merged. Then group emails by root account.

function numIslands2(m: number, n: number, positions: number[][]): number[] {
  const uf = new UnionFind(m * n);
  uf.count = 0; // start with 0 components (no land yet)
  const grid = Array.from({ length: m }, () => new Array(n).fill(false));
  const result: number[] = [];
  const dirs = [[0, 1], [0, -1], [1, 0], [-1, 0]];

  for (const [r, c] of positions) {
    if (grid[r][c]) {
      result.push(uf.count); // duplicate — skip
      continue;
    }

    grid[r][c] = true;
    uf.count++; // new island
    const idx = r * n + c;
    uf.parent[idx] = idx; // initialize this cell

    for (const [dr, dc] of dirs) {
      const nr = r + dr, nc = c + dc;
      if (nr >= 0 && nr < m && nc >= 0 && nc < n && grid[nr][nc]) {
        uf.union(idx, nr * n + nc); // merge with adjacent land
      }
    }

    result.push(uf.count);
  }

  return result;
}
// Time: O(k × α(m×n)) where k = number of positions
// Key: each new land cell starts as its own island (count++),
// then merges with adjacent land (count-- per successful union).
// BFS/DFS would be O(k × m × n) — Union-Find is much faster.

n = 6, edges = [[0,1], [1,2], [3,4], [2,4]]

Initial: parent = [0, 1, 2, 3, 4, 5], rank = [0,0,0,0,0,0], count = 6
         Each node is its own component: {0} {1} {2} {3} {4} {5}

Edge [0, 1]: find(0)=0, find(1)=1 → different roots
  union: parent[1] = 0, rank[0] = 1, count = 5
  parent = [0, 0, 2, 3, 4, 5]
  Components: {0,1} {2} {3} {4} {5}

Edge [1, 2]: find(1)→parent[1]=0→find(0)=0, find(2)=2 → different
  union: parent[2] = 0, count = 4
  parent = [0, 0, 0, 3, 4, 5]
  Components: {0,1,2} {3} {4} {5}

  Path compression: find(1) set parent[1] = 0 (already was 0)
                    find(2) set parent[2] = 0 ✓

Edge [3, 4]: find(3)=3, find(4)=4 → different
  union: parent[4] = 3, rank[3] = 1, count = 3
  parent = [0, 0, 0, 3, 3, 5]
  Components: {0,1,2} {3,4} {5}

Edge [2, 4]: find(2)→parent[2]=0=root, find(4)→parent[4]=3=root
  find(2)=0, find(4)=3 → different
  union: rank[0]=1, rank[3]=1 → equal, parent[3] = 0, rank[0] = 2
  count = 2
  parent = [0, 0, 0, 0, 3, 5]
  Components: {0,1,2,3,4} {5}

Now find(4): parent[4]=3 → parent[3]=0 → root!
  Path compression: parent[4] = 0 (shortcut!)
  parent = [0, 0, 0, 0, 0, 5]

Final: 2 components: {0,1,2,3,4} and {5}

edges = [[1,2], [1,3], [2,3]]  (1-indexed)

Initial: parent = [0, 1, 2, 3], count = 3

Edge [1, 2]: find(1)=1, find(2)=2 → different → union ✓
  parent = [0, 1, 1, 3], count = 2

Edge [1, 3]: find(1)=1, find(3)=3 → different → union ✓
  parent = [0, 1, 1, 1], count = 1

Edge [2, 3]: find(2)→parent[2]=1=root, find(3)→parent[3]=1=root
  find(2)=1, find(3)=1 → SAME ROOT!
  union returns false → THIS EDGE CREATES A CYCLE!

Answer: [2, 3]

Key: Before adding edge (u, v), if find(u) === find(v),
they're already connected — this edge is redundant and creates a cycle.

4 nodes, edges sorted by weight:
  [1, 0,1], [2, 1,2], [3, 0,2], [4, 2,3], [5, 1,3]

Initial: parent = [0,1,2,3], count = 4, totalCost = 0

Edge weight=1, (0,1): find(0)≠find(1) → union ✓
  totalCost = 1, edgesUsed = 1, count = 3

Edge weight=2, (1,2): find(1)≠find(2) → union ✓
  totalCost = 3, edgesUsed = 2, count = 2

Edge weight=3, (0,2): find(0)=find(2) → SAME! Skip (would create cycle)

Edge weight=4, (2,3): find(2)≠find(3) → union ✓
  totalCost = 7, edgesUsed = 3 = n-1 → DONE!

MST edges: (0,1), (1,2), (2,3), total cost = 7

Key: Sort edges by weight. Greedily add the cheapest edge that
connects two different components. Union-Find detects cycles in O(α(n)).
Stop when edgesUsed = n - 1 (MST has exactly n-1 edges).

Does the problem involve grouping/connectivity in an undirected graph?
├── NO  → Not a Union-Find problem
│         → Directed graph? Use DFS/Topological Sort
│         → Shortest path? Use BFS/Dijkstra
│         → Traversal needed? Use BFS/DFS
└── YES → Are edges processed one at a time (online)?
          ├── YES → Union-Find is the best choice
          │         ├── Counting components? → Track uf.count
          │         ├── Detecting cycles? → Check if union returns false
          │         ├── Building MST? → Sort edges + Union-Find (Kruskal's)
          │         └── Grouping by equivalence? → Union elements sharing a property
          └── NO  → Is the graph static (all edges known upfront)?
                    ├── YES → BFS/DFS is simpler for one-time component finding
                    │         (Union-Find also works but is overkill)
                    └── NO  → Union-Find for dynamic edge additions