The Fellowship of the Union-Find: From Theory to LeetCode

The Quest Begins (The "Why")

I still remember the first LeetCode problem that made me stare at my screen for an hour: Number of Provinces. The prompt was simple — given an adjacency matrix, tell how many connected components exist. I tried DFS, BFS, even a naïve union‑by‑loop approach, but each solution felt like I was hammering a nail with a sponge. My code passed the tiny examples, but on larger inputs it choked, and I felt that familiar frustration of “I know there’s a smarter way, I just can’t see it.”

That’s when I realized the real dragon wasn’t the input size; it was my mental model of connectivity. I kept thinking in terms of traversing edges, when what I actually needed was a way to merge groups instantly and ask whether two nodes belong to the same group without walking the whole path each time. Enter Union‑Find, also known as Disjoint Set Union (DSU). It sounded like a fancy term from a algorithms textbook, but once I grasped the intuition, it felt like discovering a hidden shortcut in a maze.

The Revelation (The Insight)

Here’s the magic: Union‑Find maintains a forest where each tree represents a connected component. The root of a tree is the representative of that set. Two operations power the whole thing:

1. Find(x) – climbs up parent pointers until it hits a root. With path compression, we make every node on that path point directly to the root, flattening the tree for future queries.
2. Union(x, y) – finds the roots of x and y; if they differ, we attach one tree under the other. Using union by rank (or size) we always attach the shallower tree under the deeper one, keeping the overall height logarithmic.

Why does this give us almost‑constant time? Imagine each Find operation as a shortcut that rewires the path you just walked. After a few finds, the trees become so flat that almost every node points straight to the root. The amortized cost per operation falls into the inverse Ackermann function, α(n), which grows so slowly that for any realistic n it’s ≤ 5. In practice we treat it as O(1).

When I first saw path compression in action, it felt like Neo dodging bullets in The Matrix — every step I took got rewritten instantly, making the next move effortless. That “aha!” moment turned a dreaded O(n²) brute force into something that scales linearly with the number of edges.

Wielding the Power (Code & Examples)

Let’s look at a clean JavaScript implementation (the logic translates easily to any language).

class UnionFind {
  constructor(n) {
    this.parent = new Array(n);
    this.rank   = new Array(n).fill(0);
    for (let i = 0; i < n; i++) this.parent[i] = i; // each node is its own set
  }

  // Find with path compression
  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]); // recursion compresses the path
    }
    return this.parent[x];
  }

  // Union by rank
  union(x, y) {
    const rootX = this.find(x);
    const rootY = this.find(y);
    if (rootX === rootY) return false; // already in same set

    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] += 1;
    }
    return true; // merged two sets
  }

  // Optional: count distinct sets
  countSets() {
    let roots = new Set();
    for (let i = 0; i < this.parent.length; i++) roots.add(this.find(i));
    return roots.size;
  }
}

Common Traps

• Forgetting path compression – If you implement find as a simple loop without updating parents, each query can degrade to O(log n) or worse, turning your supposedly fast algorithm into a sluggish one.
• Union without rank/size – Always attaching y under x can create long chains, again hurting performance. The rank heuristic keeps the tree shallow.

Real Interview Problems

1. Number of Provinces (LeetCode 547)

Given an n x n adjacency matrix isConnected, return the number of connected components.

var findCircleNum = function(isConnected) {
  const n = isConnected.length;
  const uf = new UnionFind(n);
  for (let i = 0; i < n; i++) {
    for (let j = i + 1; j < n; j++) {
      if (isConnected[i][j] === 1) uf.union(i, j);
    }
  }
  return uf.countSets();
};

The double loop is O(n²) in the worst case (dense graph), but the Union‑Find operations are practically O(1), so the overall complexity stays O(n²) — optimal for this representation.

2. Accounts Merge (LeetCode 721)

Each account is a list where the first element is a name, followed by emails. Merge accounts that share any email.

var accountsMerge = function(accounts) {
  const emailToId = new Map();
  const idToEmail = new Map();
  let id = 0;

  // Assign an integer id to each distinct email
  for (const acc of accounts) {
    for (let i = 1; i < acc.length; i++) {
      const email = acc[i];
      if (!emailToId.has(email)) {
        emailToId.set(email, id);
        idToEmail.set(id, email);
        id++;
      }
    }
  }

  const uf = new UnionFind(id);
  // Union all emails belonging to the same account
  for (const acc of accounts) {
    const firstId = emailToId.get(acc[1]);
    for (let i = 2; i < acc.length; i++) {
      const nextId = emailToId.get(acc[i]);
      uf.union(firstId, nextId);
    }
  }

  // Group emails by root
  const groups = new Map(); // root -> list of emails
  for (let i = 0; i < id; i++) {
    const root = uf.find(i);
    if (!groups.has(root)) groups.set(root, []);
    groups.get(root).push(idToEmail.get(i));
  }

  // Build result
  const res = [];
  for (const [root, emails] of groups) {
    const name = accounts.find(acc => acc.includes(emails[0]))[0];
    res.push([name, ...emails.sort()]);
  }
  return res;
};

Again, the heavy lifting is done by Union‑Find; the algorithm runs near‑linear in the total number of emails.

Why This New Power Matters

Mastering Union‑Find changes how you think about connectivity problems. Instead of reaching for DFS/BFS every time you see a graph, you ask: Do I need to know the actual paths, or just whether two nodes belong to the same component? If the latter, Union‑Find gives you a toolbox that’s both simpler to code and faster in practice.

You’ll start spotting it in unexpected places: dynamic connectivity, image processing (pixel labeling), Kruskal’s MST algorithm, even in game development for managing terrain chunks. The confidence that comes from knowing you can flatten a structure with a couple of lines is infectious — it’s like leveling up your problem‑solving avatar.

Your Turn

Grab a Union‑Find template, toss it into your next LeetCode practice session, and watch those “hard” connectivity puzzles melt away. Try implementing it in a language you rarely use — maybe Rust or Go — just to feel the syntax shift while the core idea stays the same.

What’s the first problem you’ll conquer with your newfound DSU superpower? Drop it in the comments; I’d love to hear about your quest! 🚀