medium

20 minMostly mid / senior

When to use. Merge groups over time; “are these two connected?” after a stream of unions.

Complexity. Time Almost O(1) per op with path compression + union by rank (Ackermann inverse). Space O(n) parent (and rank) arrays.

Who gets asked. Interns can survive with DFS components. Union-find is the mid/senior shortcut for dynamic connectivity.

Prereq. Graphs at the “components” level.

Union-Find

A forest of trees representing disjoint groups. find(x) returns the root; union(a, b) merges groups. With path compression and union by rank, operations are effectively constant.

The idea

parent[i] = i at the start. find walks to the root and flattens the path (path compression). union links the shorter tree under the taller (rank or size).

Use it when edges arrive over time: “now a and b are connected — how many components left?” DFS from scratch each time is too slow.

Interns can answer component-count with DFS. Union-find is the mid/senior tool, and the Kruskal MST backbone.

Worked example

Components after undirected edges

n nodes labeled 0..n−1 and a list of undirected edges. How many connected components? Example: n = 5, edges [[0,1],[1,2],[3,4]] → 2.

Start with n components.
For each edge, if find(a) !== find(b), union and decrement.
If they already share a root, the edge is redundant.

function componentCount(n, edges) {
  const parent = Array.from({ length: n }, (_, i) => i);
  const rank = Array(n).fill(0);
  function find(x) {
    if (parent[x] !== x) parent[x] = find(parent[x]);
    return parent[x];
  }
  function union(a, b) {
    a = find(a);
    b = find(b);
    if (a === b) return false;
    if (rank[a] < rank[b]) [a, b] = [b, a];
    parent[b] = a;
    if (rank[a] === rank[b]) rank[a] += 1;
    return true;
  }
  let parts = n;
  for (const [a, b] of edges) {
    if (union(a, b)) parts -= 1;
  }
  return parts;
}

Time Almost O(n + m) for m edges. Space O(n).

Practice shapes

Original prompts — same family as interview questions, not copied statements.

Equality equations
A list of “a == b” and “a != b” on variables. Are the equations consistent? Union the equals, then reject any inequality whose sides share a root.
Aim: Almost O(n) with 26 letters or n variables
Redundant connection
n nodes, n edges, originally a tree plus one extra edge. Which edge created the cycle if you add in order?
Aim: Almost O(n)
Accounts merge
People with lists of emails. If two lists share an email, they are the same person. Group emails per person.
Aim: Almost linear in emails after unions; sort each group

Saved in this browser. No account.

PreviousGraphs

NextDynamic Programming