Union-Find: The Complete Interview Guide

What is Union-Find?

Union-Find (also called Disjoint Set Union or DSU) is a data structure that tracks a set of elements partitioned into non-overlapping subsets. It supports two operations efficiently: find (which set does an element belong to?) and union (merge two sets). With path compression and union by rank, both operations run in nearly O(1) amortized time.

When to Use Union-Find

• Connected components: Are two nodes in the same component?
• Cycle detection: Does adding this edge create a cycle?
• Minimum spanning tree: Kruskal's algorithm uses Union-Find
• Dynamic connectivity: Elements are being connected over time
• Accounts merge / grouping: Group items by shared properties

Implementation with Path Compression + Union by Rank

class UnionFind {
  parent: number[]
  rank: number[]
  count: number  // number of connected components

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

  // Find the root of x with path compression
  find(x: number): number {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]) // path compression
    }
    return this.parent[x]
  }

  // Union two sets by rank
  union(x: number, y: number): boolean {
    const rootX = this.find(x)
    const rootY = this.find(y)

    if (rootX === rootY) return false // already in same set

    // Attach smaller tree under larger tree
    if (this.rank[rootX] < this.rank[rootY]) {
      this.parent[rootX] = rootY
    } else if (this.rank[rootX] > this.rank[rootY]) {
      this.parent[rootY] = rootX
    } else {
      this.parent[rootY] = rootX
      this.rank[rootX]++
    }

    this.count--
    return true
  }

  connected(x: number, y: number): boolean {
    return this.find(x) === this.find(y)
  }
}

// Time complexity: O(α(n)) per operation ≈ O(1) amortized
// α = inverse Ackermann function, grows incredibly slowly
// For all practical purposes, it's constant time

Pattern 1: Number of Connected Components

Problem: Given n nodes and a list of edges, find the number of connected components.

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

  for (const [a, b] of edges) {
    uf.union(a, b)
  }

  return uf.count
}

// Example: n=5, edges=[[0,1],[1,2],[3,4]]
// Components: {0,1,2}, {3,4} → returns 2

Pattern 2: Redundant Connection (Cycle Detection)

Problem: Given a graph that is a tree with one extra edge, find that extra edge. The extra edge is the one that creates a cycle.

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 union returns false, u and v are already connected
    // → this edge creates a cycle
    if (!uf.union(u, v)) {
      return [u, v]
    }
  }

  return [] // shouldn't reach here
}

// Key insight: process edges in order.
// First edge that connects already-connected nodes = the cycle edge.

Pattern 3: Accounts Merge (LeetCode 721)

Problem: Given a list of accounts where each account has a name and emails, merge accounts that share any email.

function accountsMerge(accounts: string[][]): string[][] {
  const uf = new UnionFind(accounts.length)
  const emailToAccount = new Map<string, number>()

  // Step 1: 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)
      }
    }
  }

  // Step 2: 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])
    }
  }

  // Step 3: Format result
  const result: string[][] = []
  for (const [root, emails] of groups) {
    const name = accounts[root][0]
    result.push([name, ...[...emails].sort()])
  }

  return result
}

Pattern 4: Number of Islands II (Dynamic Connectivity)

Problem: Given a grid, land cells are added one at a time. After each addition, return the number of islands.

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

  for (const [r, c] of positions) {
    const idx = r * n + c
    if (grid[idx]) { // already land
      result.push(uf.count)
      continue
    }

    grid[idx] = true
    uf.count++ // new island

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

    result.push(uf.count)
  }

  return result
}

// Why Union-Find over BFS/DFS?
// BFS/DFS: re-traverse entire grid after each addition → O(k * m * n)
// Union-Find: O(1) per merge operation → O(k * α(m*n)) ≈ O(k)

Union-Find vs BFS/DFS

Problems to Practice

• Number of Connected Components (LeetCode 323) — Classic Union-Find starter
• Redundant Connection (LeetCode 684) — Cycle detection
• Accounts Merge (LeetCode 721) — Real-world grouping problem
• Number of Islands II (LeetCode 305) — Dynamic connectivity
• Longest Consecutive Sequence (LeetCode 128) — Creative Union-Find application
• Minimum Spanning Tree (LeetCode 1584) — Kruskal's with Union-Find