Union-find: every group has a leader

Keep an array where each item points towards the leader of its group. Two items are in the same group exactly when they lead to the same leader. Joining two groups is one write: point one leader at the other.

Think of it like this: clubs at a school. Every student knows one person to ask, and asking up the chain always ends at the club captain. To check if two students are in the same club, compare their captains. When two clubs merge, the smaller club's captain starts answering to the bigger club's captain. Nobody else has to change anything.

How to spot it

Words and constraints in a problem that point to this pattern:

• Connections that arrive one at a time: “after each new friendship”, “cables are added in this order”, “process the edges in order”
• “Are these two in the same group?” or “how many groups are there?”, with no need for the actual path between them
• “Find the edge that creates a loop” or “which connection was unnecessary?”
• Things that merge when they share something: accounts with a common email, words with a common synonym
• “Connected components” on a list of edges where you never need distances or the shortest path

Watch it work

The template

class UnionFind {
  private parent: number[]; // parent[i] = the item i points to; a leader points to itself
  private size: number[];   // size[leader] = how many items are in that leader's group
  count: number;            // how many separate groups there are right now

  constructor(n: number) {
    this.parent = Array.from({ length: n }, (_, i) => i); // everyone starts as their own leader
    this.size = new Array(n).fill(1);                      // every group starts with 1 item
    this.count = n;                                        // n groups of one
  }

  // Return the leader of x's group.
  find(x: number): number {
    let root = x;
    while (this.parent[root] !== root) root = this.parent[root]; // walk up to the leader
    while (this.parent[x] !== root) {   // path compression: walk the same path again...
      const next = this.parent[x];
      this.parent[x] = root;            // ...pointing each item straight at the leader
      x = next;
    }
    return root;
  }

  // Join the groups of a and b. Returns false if they were already together.
  union(a: number, b: number): boolean {
    let ra = this.find(a);
    let rb = this.find(b);
    if (ra === rb) return false;                    // same leader: already one group
    if (this.size[ra] < this.size[rb]) [ra, rb] = [rb, ra]; // make ra the bigger group
    this.parent[rb] = ra;                           // smaller leader now answers to the bigger one
    this.size[ra] += this.size[rb];                 // the bigger group absorbed the smaller
    this.count--;                                   // two groups became one
    return true;
  }

  // Are a and b in the same group?
  connected(a: number, b: number): boolean {
    return this.find(a) === this.find(b);
  }
}

Worked example

1. The first idea comes from the graphs lesson. After each new friendship, add it to an adjacency list (a list of each person's friends). Then count the groups again with a full search from every unvisited person. That gives the right numbers.

   // After adding each friendship, recount from scratch.
   for (const [a, b] of friendships) {
     graph.get(a)!.push(b);
     graph.get(b)!.push(a);
     answer.push(countGroupsWithSearch(graph)); // visits every person and every friendship again
   }
   

2. Notice the waste. Each recount visits all n people and every friendship so far. Then it throws that work away. With 100,000 people and 100,000 friendships, that's about 100,000 × 200,000 = 20 billion steps. Yet each new friendship changes very little. It either joins two groups into one, or it links two people who were already in the same group.

3. That's exactly what union-find tracks. Start with count = n, since everyone is alone. For each friendship, call union(a, b). If it joins two different groups, the count drops by 1. If the two were already in one group, nothing changes. The class above already keeps count up to date.

4. The finished code is short, because the class does the work.

   function groupsAfterEach(n: number, friendships: [number, number][]): number[] {
     const uf = new UnionFind(n);
     const answer: number[] = [];
     for (const [a, b] of friendships) {
       uf.union(a, b);         // joins two groups, or does nothing if they're already one
       answer.push(uf.count);  // the number of groups right now
     }
     return answer;
   }
   

5. Check it: [0, 1] joins two people, so 5 → 4. [1, 2] brings 2 into that group: 3. [3, 4] makes a second pair: 2. [0, 2] links two people who already share leader 0. So union returns false and the count stays 2. [2, 3] merges the two groups: 1. Result [4, 3, 2, 2, 1]. Edge cases: no friendships returns []. A friendship of a person with themself, like [3, 3], finds the same leader twice and changes nothing.

Common mistakes

• Setting parent[a] = b instead of parent[find(a)] = find(b). This moves one item, not its whole group. The rest of a's old group is left behind, and later answers are wrong.
• Comparing parents instead of leaders, as in parent[a] === parent[b]. Two items can be in the same group but point to different parents. Then connected says false when it should say true. Always compare find(a) with find(b).
• Lowering the group count on every union call. When the two items already share a leader, nothing merged, so the count drops too far. Only count down when union actually joins two groups.
• Skipping both union by size and path compression. Unions along a chain build one long line, and every find walks the whole line. With 100,000 items the program is slow. A recursive find can also overflow the stack.
• Forgetting to give string items a number first. parent is an array, so parent["ana@home.io"] silently creates a property instead of an entry. Map each string to an index with a Map before calling union.

Cost

In interviews