Union-Find Explained — Path Compression, Union by Rank, Three Walkthroughs

Union-find is the data structure that makes "are these two things in the same group?" feel like O(1). The theoretical bound is the inverse-Ackermann function α(n) — a constant so effectively-constant that even textbooks stop trying to distinguish it from O(1). The trick is two tiny optimisations layered on the plainest tree structure you can imagine. This post is the pattern-recognition guide: when it's the right tool, why the tricks matter, and how to write it in twelve lines.

Recognition — when to reach for it

Union-find is the right tool when all four of these hold:

1. You have a set of elements that get partitioned into groups through some process.
2. The process is online — groups merge over time as edges or relationships are discovered; you can't sort them all up front.
3. The questions you ask are "same group?" or "how many groups are there?" — not "what's the shortest path?" or "what's the total weight?"
4. Speed matters — a scan-based solution would be O(n²) per query, and there are many queries.

The natural home is connectivity under dynamic edge insertion. LC 261 (Graph Valid Tree), LC 547 (Number of Provinces), LC 684 (Redundant Connection), LC 1319 (Number of Operations to Make Network Connected). Kruskal's minimum-spanning-tree algorithm is another canonical use: sort edges, then union-find to reject those that would create cycles.

Mental model — a forest of pointer-to-parent

Every element x has a parent pointer: parent[x]. Follow parents upward until you reach an element whose parent is itself — the root. The root uniquely identifies the group. Two elements are in the same group iff they have the same root.

That's the whole data structure. parent is an array (or dict) mapping x → parent[x], with self-loops at each root. The two operations are:

• find(x): walk parents up to the root, return the root.
• union(a, b): find the roots of both, and if different, hang one under the other.

Without any optimisations, both are O(depth of tree) — up to O(n) worst case if the tree degenerates into a chain. The two tiny optimisations make it nearly O(1).

The two optimisations that make it fast

Path compression (in find)

When walking up to the root, rewrite every visited element's parent to point directly at the root. The next find on any of those elements is O(1).

def find(x):
    root = x
    while parent[root] != root:
        root = parent[root]
    # Second pass: point everyone on the path directly at the root.
    while parent[x] != root:
        parent[x], x = root, parent[x]
    return root

A common shorter form uses one-line recursion:

def find(x):
    if parent[x] != x:
        parent[x] = find(parent[x])
    return parent[x]

Same effect — parents on the path get rewritten to point at the root — but relies on recursion. Iterative is safer for adversarial inputs.

Union by rank (in union)

When merging two trees, hang the shorter one under the taller one. This keeps the tree shallow. Track rank (an upper bound on tree height) per root.

def union(a, b):
    ra, rb = find(a), find(b)
    if ra == rb:
        return False  # already in the same group
    if rank[ra] < rank[rb]:
        parent[ra] = rb
    elif rank[ra] > rank[rb]:
        parent[rb] = ra
    else:
        parent[rb] = ra
        rank[ra] += 1
    return True

A common alternative: union by size (hang the smaller tree under the larger one, by element count). Same asymptotic bound; sometimes more useful because you get "size of the group" as a byproduct.

Together

Path compression + union by rank (or by size) makes each find and union cost O(α(n)) amortised — where α(n) is the inverse-Ackermann function. For every input size that fits in the observable universe, α(n) ≤ 4. Treat it as O(1) in interviews and complexity analyses; if pressed, say "O(α(n)) — effectively constant".

The template

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n              # number of distinct components

    def find(self, x: int) -> int:
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        self.count -= 1
        return True

count tracks the number of components; every successful union merges two into one, so count -= 1. Reading it at the end tells you how many distinct groups remain.

Walkthrough 1 — LeetCode 547, Number of Provinces

Given an n × n symmetric matrix isConnected where isConnected[i][j] == 1 means city i and city j are directly connected, return the number of provinces (connected components).

Recognition. Connected components ✓. Symmetric, undirected. Could be BFS or DFS, could be union-find. Union-find is the natural fit because we're told the edges; we don't have to scan a graph structure.

def findCircleNum(isConnected: list[list[int]]) -> int:
    n = len(isConnected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i + 1, n):     # symmetric — only upper triangle
            if isConnected[i][j] == 1:
                uf.union(i, j)
    return uf.count

Every edge is one union call. Reading uf.count at the end gives the answer directly. O(n² α(n)) total — dominated by the double loop over the matrix, not by union-find itself.

Walkthrough 2 — LeetCode 684, Redundant Connection

Given a graph that started as a tree with n nodes and had one extra edge added, return the extra edge (the one that creates a cycle).

Recognition. Cycle detection under dynamic edge insertion ✓. Union-find shines: process edges one by one, and the first edge whose endpoints are already in the same group is the redundant one.

def findRedundantConnection(edges: list[list[int]]) -> list[int]:
    n = len(edges)
    uf = UnionFind(n + 1)             # nodes are 1-indexed
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]
    return []

uf.union(u, v) returns False when the two are already connected — that's the cycle-creating edge, and by problem constraint there's exactly one. The whole solution is five lines with the template above.

Walkthrough 3 — LeetCode 200, Number of Islands

Given an m × n grid of '1' (land) and '0' (water), return the number of islands.

The default solution is DFS or BFS (see the BFS vs DFS post); union-find is an alternate solution that shines when the grid is very sparse or when you need to handle online land additions (LC 305 Number of Islands II).

Idea: treat each land cell as its own group initially. Walk the grid; for every '1' cell, union it with its up and left neighbours (if they're also land). At the end, count the distinct roots among the land cells.

def numIslands(grid: list[list[str]]) -> int:
    if not grid or not grid[0]:
        return 0
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)
    land = 0

    def idx(r, c):
        return r * cols + c

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] != '1':
                continue
            land += 1
            for dr, dc in ((-1, 0), (0, -1)):    # up and left only
                nr, nc = r + dr, c + dc
                if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                    if uf.union(idx(r, c), idx(nr, nc)):
                        land -= 1   # merged — one fewer distinct island

    return land

Every successful union merges two land counts into one, so land -= 1 on each successful union tracks the current island count. For a static grid, DFS is shorter; for LC 305's online variant, union-find is the only viable approach.

Common bugs

• Union without path compression, or find without union by rank. Either alone still degrades to O(n) worst case on adversarial inputs (a long chain). You need both to hit α(n).
• Comparing parent[a] == parent[b] instead of find(a) == find(b). Only find guarantees the root. Two elements can share a direct parent without both being at the root — you need to walk up.
• Forgetting to check ra == rb before hanging trees. Without this check, unioning two elements already in the same group re-parents a root under itself and can corrupt the structure.
• Recursive find on a chain of 10⁵ nodes without path compression on the first pass. Python's recursion limit bites. The iterative two-pass form is safer for adversarial inputs.

When union-find is not the tool

• Shortest-path queries. Union-find only knows which group; it doesn't know distances. Reach for BFS (unweighted) or Dijkstra (weighted).
• Edge deletions. Union-find doesn't support "split a group back into two". If your problem removes edges over time, reverse the process — process deletions in reverse as additions — or use link-cut trees.
• Weighted union with aggregated statistics. If you need "sum of values across the group" or "max value in the group", augment the structure to carry the info on the root, and update on every union. Doable but easier to overlook.
• The problem gives you a static graph with one connectivity query. DFS is a five-liner and arguably clearer.

How the Algotrek tutor would prompt you here

When a learner opens a union-find problem on Algotrek, the tutor doesn't reveal the template. It asks three questions:

1. "What are the elements, and what does 'same group' mean?" — Naming the elements (cells, edges, students) and the equivalence relation (connected, in the same club) is what turns an abstract problem into a concrete UnionFind(n) call.
2. "When two elements are merged, do you also need aggregate info about the group?" — Element count? Sum? Max? If yes, augment the root; if no, the plain template is enough.
3. "Are edges ever removed, or only added?" — Union-find is add-only. If deletions matter, the technique isn't the tool.

Answer all three and the twelve-line template is the whole solution.

Where to go next

• LC 1319, Number of Operations to Make Network Connected. Same shape as LC 547 but you compute the minimum number of edge moves — a lovely follow-up that combines union-find with a counting insight.
• LC 305, Number of Islands II. LC 200's online variant. Union-find is the only clean solution — DFS/BFS would rescan the whole grid on every insertion.
• Kruskal's Minimum Spanning Tree. Sort edges by weight, then union-find to reject cycles. LC 1584 (Min Cost to Connect All Points) is the interview-classic.
• LC 990, Satisfiability of Equality Equations. Union-find on characters, with an equality/inequality pass separation. The "process one class first, then check the other" pattern generalises.

Cross-reference the sliding-window, two-pointer, binary-search, monotonic-stack, backtracking, and BFS vs DFS posts. Those six were about processing linear or graph structures in a single pass. Union-find is different — it's a maintained data structure that answers a specific question (same group?) across many updates. The pattern-recognition still applies: name the invariant (partition into groups), pick the tool (union-find), and cash in on the α(n) bound.

For the α(n) claim — and the specialised-structures row that lists union-find alongside segment tree and Fenwick — see the Big-O cheat sheet.