Solution

We are building a structure that keeps a pile of elements sorted into non-overlapping groups and can merge two groups, or check whether two elements share a group, in almost constant time.

The problem, in plain English

Imagine a social network with a million accounts. You keep getting told "these two people are now friends," and every so often someone asks "are these two in the same friend circle?" You do not care who connects them or how far apart they are — only whether some chain of friendships joins them at all. Union-Find answers exactly that: union(x, y) records a new connection, connected(x, y) asks whether two elements share a group, and count() reports how many separate groups are left. The same structure detects cycles in a graph and drives Kruskal's minimum-spanning-tree algorithm.

The mental model

Represent each set as a tree. Every element points to a parent, and the one element that points to itself is the set's root — its representative. Two elements are in the same set when climbing parent pointers from each of them lands on the same root. find(x) does that climb; union(x, y) finds both roots and, if they differ, hangs one root under the other so the two trees become one.

A first attempt

The most direct version keeps a parent array, walks up to a root in find, and in union just hangs the first root under the second:

function unionFindNaive(n) {
  const parent = Array.from({ length: n }, (_, i) => i);

  function find(x) {
    // Climb until we hit a node that is its own parent — the root.
    while (parent[x] !== x) x = parent[x];
    return x;
  }

  function union(x, y) {
    // Always hang x's root under y's root, ignoring how tall either tree is.
    parent[find(x)] = find(y);
  }

  return { find, union };
}

This returns correct answers, but it can get slow. Because union never looks at how tall the trees are, a run of merges can build one long chain: union(0, 1), union(1, 2), union(2, 3), and so on leaves 0 → 1 → 2 → 3 → …, a straight line. Now find(0) has to step through every node to reach the root, so a single lookup costs O(n), and answering m queries costs O(n · m). Nothing bounds the height of the tree.

Two well-known fixes cut the height down, and together they make the operations almost free:

• Union by rank — when merging, attach the shorter tree under the taller tree's root. A short tree tucked under a tall one does not make it any taller, so heights grow only very slowly.
• Path compression — while find climbs to the root, repoint every node it passes straight at the root, so the next find on any of them is a single hop.

The working solution

function unionFind(n) {
  // parent[i] is i's parent in its set-tree; a root points at itself.
  const parent = new Array(n);
  // rank[i] is an upper bound on the height of the tree rooted at i.
  const rank = new Array(n).fill(0);
  // How many disjoint sets exist right now. Every element starts on its own.
  let sets = n;
  for (let i = 0; i < n; i++) parent[i] = i;

  function find(x) {
    // First pass: walk up to the root.
    let root = x;
    while (parent[root] !== root) root = parent[root];
    // Second pass — path compression: repoint every node on the path
    // directly at the root, so a later find on any of them is one hop.
    while (parent[x] !== root) {
      const next = parent[x];
      parent[x] = root;
      x = next;
    }
    return root;
  }

  function union(x, y) {
    const rx = find(x);
    const ry = find(y);
    // Already in the same set: nothing merges, so report false and keep count.
    if (rx === ry) return false;
    // Union by rank: hang the lower-rank root under the higher-rank one.
    if (rank[rx] < rank[ry]) {
      parent[rx] = ry;
    } else if (rank[rx] > rank[ry]) {
      parent[ry] = rx;
    } else {
      // Equal ranks: pick either as the new root; its rank goes up by one.
      parent[ry] = rx;
      rank[rx]++;
    }
    sets--; // two different sets just became one
    return true;
  }

  function connected(x, y) {
    // Same set exactly when the two climbs reach the same root.
    return find(x) === find(y);
  }

  function count() {
    return sets;
  }

  return { find, union, connected, count };
}

module.exports = { unionFind };

Three shifts from the naive version. find now makes a second pass that flattens the path it just walked, so trees never stay deep. union compares the two roots' rank and always tucks the shorter tree under the taller, so a merge barely changes the height. And union looks before it leaps: it compares the roots, returns false without touching anything when they already match, and decrements sets only when two genuinely different sets merge. Together, path compression and union by rank pin the amortized cost of find and union at O(α(n)) — where α is the inverse Ackermann function, a quantity so slow-growing it never exceeds 4 for any n you could store.

Walking through one call

Start with unionFind(5) and merge a few elements:

• unionFind(5) — five singleton sets {0} {1} {2} {3} {4}; count() is 5, and every element is its own root.
• union(0, 1) — the roots 0 and 1 differ, so one is hung under the other. {0,1} is now one tree and count() drops to 4.
• union(2, 3) — same on the other side: {2,3} becomes a tree and count() is 3.
• union(1, 3) — find(1) climbs to root 0 and find(3) climbs to root 2. They differ, so the two trees merge into {0,1,2,3}; union by rank hangs one root under the other so the result stays shallow, and count() drops to 2.

What is left is one four-element set and the untouched singleton {4} — two disjoint sets in all. That last merge is the rank rule in action: it attaches one whole tree under the other tree's root.

Gotchas

• Compress inside find, do not just return the root — if find climbs to the root but leaves the nodes pointing where they were, the tree stays as deep as union left it and every later find re-walks the whole path. Repoint each visited node straight at the root on the way out.
• Attach the shorter tree under the taller — this is the entire job of rank. Skip it and hang trees together blindly, and a run of unions rebuilds the same O(n) chain the naive version suffered from. Compare the roots' ranks and tuck the lower under the higher.
• Only decrement count when the roots differ — call find on both first. If they already share a root, return false and leave the count alone. Dropping the count on every union call makes it drift below the real number of sets.
• Compare roots, never raw parents — connected and union must compare find(x) with find(y), not parent[x] with parent[y]. Two elements deep in the same tree can have different immediate parents but the same root; only the root identifies the set.

Going further

• Union by size instead of rank — track how many elements each set holds and attach the smaller set under the larger. It gives the same asymptotic guarantee and hands you each set's size for free, which is handy when a problem asks for the largest group.
• The α(n) analysis — the amortized O(α(n)) bound is Tarjan's result, and it needs both optimizations: path compression or union by rank on its own gives only O(log n) per operation. The inverse Ackermann function α grows so slowly it stays at or below 4 for any conceivable input size.
• Rollback / persistent DSU — some offline query problems need to undo a union. A variant that drops path compression and records each rank and parent write to a stack can pop back to an earlier state, at the cost of a slower O(log n) find.
• Weighted union-find — store each node's offset relative to its parent so find can also report where x sits relative to its root. That answers "is A exactly d units from B?" constraint problems, not just "are A and B connected?"