VocalHyre
Sign up

DSA · Patterns, not puzzles

How does union-find work?

Hardunion-finddisjoint-setsgraphsUpdated Oct 2026
Quiz this track

Short answer

Union-find tracks disjoint sets with a parent array. Path compression flattens the tree on find, and union by rank keeps it shallow, giving near-constant amortized operations.

The structure answers two questions: which set contains this element, and are these two elements connected? Each set is a tree, and the root identifies the set. Find walks to the root; union links two roots. Without optimisations, a chain of unions can make find linear.

js
class UnionFind {
  constructor(size) {
    this.parent = Array.from({ length: size }, (_, i) => i);
    this.rank = new Array(size).fill(0);
  }

  find(x) {
    if (this.parent[x] !== x) {
      this.parent[x] = this.find(this.parent[x]);
    }
    return this.parent[x];
  }

  union(a, b) {
    const rootA = this.find(a);
    const rootB = this.find(b);
    if (rootA === rootB) return false;
    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] += 1;
    }
    return true;
  }
}
Path compression rewrites parent pointers during find, while rank keeps unions balanced.

Where it is used

  • Kruskal's minimum spanning tree algorithm
  • Detecting cycles in an undirected graph
  • Counting connected components
  • Grouping accounts or transactions that belong together
  • Dynamic connectivity as edges are added

Union-find only supports adding connections, not removing them. If edges are deleted, you need a different structure or an offline algorithm. For directed reachability or weighted shortest paths, it is the wrong tool.

With both path compression and union by rank, the amortized cost per operation is O(alpha(n)), where alpha is the inverse Ackermann function and is effectively constant for practical inputs.

Follow-ups you should expect

Interviewers use these to check whether the first answer was understanding or memorisation.

  1. 1How does path compression work?
  2. 2Why does union by rank help?
  3. 3How do you detect a cycle in an undirected graph with union-find?
  4. 4What is the complexity of union-find?

Say it in the interview

Union-find represents each set as a tree with a root, so find walks to the root and union links two roots together. Path compression points nodes directly at the root during find, and union by rank attaches the shorter tree under the taller one, which makes operations effectively constant amortized. I use it for Kruskal and undirected cycle detection, but not when edges need to be removed.

Use this as a model, not a script. Saying it in your own words is what makes it survive follow-up pressure.

Related questions

MediumHow do you detect a cycle in a graph?HardHow do you find a minimum spanning tree?EasyHow do you represent a graph?

Reading is step one

Now say it out loud.

Understanding an answer and delivering it under pressure are different skills. Rehearse this topic in a live DSA mock interview and get scored feedback on depth, clarity and confidence.

Start a free DSA interviewBrowse all questions