Union-find (disjoint set)

How does Union-find (disjoint set) work?

Each element starts as its own group. Its parent pointer points at itself.

find walks up the parent chain until it reaches a root. The root is the group's name.

union takes two elements, finds both roots, and hangs one under the other. One call merges two groups.

Path compression rewrites every node on the walk to point straight at the root. The next find is one hop.

Union by rank hangs the shorter tree under the taller one. That stops the chains from growing.

With both, a find or a union costs near constant time. Nothing here needs the edges kept.

1. [0, 1, 2, 3, 4]Five elements, five groups. Each one is its own parent.
2. [0, 0, 2, 3, 4]union(0, 1) hangs 1 under 0. Two elements now share a root.
3. [0, 0, 2, 2, 4]union(2, 3) hangs 3 under 2. A second group forms.
4. [0, 0, 0, 2, 4]union(1, 2) finds roots 0 and 2. Root 2 hangs under root 0.
5. [0, 0, 0, 0, 4]find(3) walks 3 to 2 to 0. Compression points 3 straight at 0.

class UnionFind {
    constructor(n) {
        this.parent = Array.from({ length: n }, (_, i) => i);
        this.rank = new Array(n).fill(0);
    }
    find(x) {
        if (this.parent[x] !== x) this.parent[x] = this.find(this.parent[x]);
        return this.parent[x];
    }
    union(x, y) {
        const rx = this.find(x), ry = this.find(y);
        if (rx === ry) return false;
        if (this.rank[rx] < this.rank[ry]) this.parent[rx] = ry;
        else if (this.rank[rx] > this.rank[ry]) this.parent[ry] = rx;
        else { this.parent[ry] = rx; this.rank[rx]++; }
        return true;
    }
}

A worked example of Union-find (disjoint set)

Redundant connection

You get a graph that was a tree, plus one extra edge. Find the edge that closes a cycle.

Edges arrive in order. Return the last one joining two nodes already connected.

Walk the edges in order and union each one.

When both ends already share a root, the edge adds nothing. It closes a cycle.

Keep the last such edge. That is the answer.

function findRedundantConnection(edges) {
    const parent = Array.from({ length: edges.length + 1 }, (_, i) => i);

    function find(x) {
        while (parent[x] !== x) {
            parent[x] = parent[parent[x]]; // path halving
            x = parent[x];
        }
        return x;
    }

    let answer = [];
    for (const [a, b] of edges) {
        const rootA = find(a);
        const rootB = find(b);
        if (rootA === rootB) {
            answer = [a, b]; // both ends were already connected
        } else {
            parent[rootA] = rootB;
        }
    }

    return answer;
}

When should you use Union-find (disjoint set)?

These phrases in a problem statement point here:

• •are these two in the same group
• •merge/union facts arrive one at a time
• •dynamic connectivity as edges are added
• •account/friend merging over time
• •adding this edge would create a cycle

What is Union-find (disjoint set) confused with?

• Connected components: Flood fill counts groups in a graph that is already complete. Union-find answers while the edges are still arriving.
• Graph BFS / DFS: A traversal visits neighbours, so it needs an adjacency list. Union-find never stores the edges at all.
• Topological sort: Topological order needs directed edges and a DAG. Union-find treats every edge as undirected.
• Hash set / map: A map groups by a key you already know. Union-find discovers the groups as facts merge them.

Common mistakes with Union-find (disjoint set)

• Comparing elements instead of roots

  Two elements can sit in one group with different parents. Compare find(a) with find(b).

• Union without find

  Writing parent[a] = b joins two elements, not two groups. Always hang one root under the other.

• Skipping path compression

  Without it a chain can grow to n links. A single find then costs O(n).

• Sizing the array by edge count

  The array is indexed by element, not by edge. An off-by-one here reads undefined for the last node.

Which interview problems use Union-find (disjoint set)?

• Number of provinces: Union every connected pair, then count the distinct roots.
• Redundant connection: The first edge whose two ends already share a root.
• Accounts merge: Emails link accounts. Union on a shared email, then group by root.
• Number of islands: Union neighbouring land cells. Useful when the grid arrives in pieces.
• Most stones removed: Stones sharing a row or a column belong to one group.
• Satisfiability of equality equations: Union the equals first. Then test every not-equals against the roots.
• Smallest string with swaps: Swappable indices form a group. Sort the letters inside each group.

What is the time and space complexity of Union-find (disjoint set)?

near O(1) per op

n up to 1e6 elements with m interleaved queries gives O(m alpha(n)). Alpha is under 5 for any n you will meet.