What Is Path Compression? The Union-Find Trick Behind Near-O(1)

You wrote Union-Find. It passed the small test cases. Then it timed out on the large input, and you stared at the submit button like it personally let you down.

That timeout is almost always the same bug: find without path compression.

The fix is one line. When you call find(x) to locate the root of x's group, you traverse a chain of parent pointers. Path compression makes every node on that walk point directly to the root, so the next find on any of those nodes costs one step instead of many.

Without it, a badly ordered sequence of unions turns your Union-Find into a linked list where find costs O(n). With path compression and union by rank together, the amortized cost per operation drops to O(α(n)), where α is the inverse Ackermann function. α(n) ≤ 5 for every input you will ever see in practice. Treat it as constant.

Without Path Compression, Union-Find Has No Memory

Union-Find tracks which elements belong to the same group using a parent array. Each element points to its parent, and the root of a tree points to itself. Finding which group an element belongs to means walking up to the root:

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

This works. The problem is it forgets everything it just did. Suppose a sequence of unions built this chain:

1 -> 2 -> 3 -> 4 -> 5

find(1) walks four hops to reach 5. Call it again: four hops again. The tree never flattens, because nothing tells it to. Specific union orderings force this consistently, making every find O(n) on a structure you were counting on being fast.

One Recursive Assignment Fixes It

The compression is a single assignment added to the recursive call:

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

Here is what happens. The recursive call finds the root all the way at the top of the tree. Before returning from each stack frame, it sets parent[x] to that root. Every node on the path gets its parent pointer updated from "some ancestor" to "the root directly." The chain collapses on the way back up.

The key insight is that find was already traversing the path, so updating pointers on the way back costs nothing asymptotically. You're charging the cleanup to work you were already paying for.

What a Single Call Actually Does

Six elements. After several unions, the parent array looks like this:

parent = [0, 0, 1, 2, 3, 4]  (0-indexed)

Which represents the chain:

5 -> 4 -> 3 -> 2 -> 1 -> 0

You call find(5). The algorithm unwinds:

find(5) calls find(4)
  find(4) calls find(3)
    find(3) calls find(2)
      find(2) calls find(1)
        find(1) calls find(0)
          parent[0] == 0, return 0
        parent[1] = 0, return 0
      parent[2] = 0, return 0
    parent[3] = 0, return 0
  parent[4] = 0, return 0
parent[5] = 0, return 0

After this single call, the parent array is:

parent = [0, 0, 0, 0, 0, 0]

The tree is completely flat:

  0
 /|\ \ \
1 2 3 4 5

Path compression before and after: deep chain collapses to a flat star in one find call

Every subsequent find on any of these nodes is one step. The chain will never reform because future unions always use compressed roots.

Three Variants, Same Bound

Full path compression (shown above) uses two passes: one down the tree to find the root, one back up to update every pointer. It produces the flattest possible tree but requires recursion or an explicit two-pass loop.

Path halving is the iterative version most competitive programmers and library implementors actually ship:

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

Each node skips one level on every access. The tree does not become fully flat immediately, but each call makes progress. No recursion, no stack overhead.

Path splitting updates every pointer to the grandparent in a single pass:

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

All three variants achieve the same amortized O(α(n)) complexity when paired with union by rank. Path halving is marginally faster in practice because it does half the pointer updates per call. Pick it unless you enjoy explaining your aesthetic choices to a rubric-based interview scorer.

How Low Does the Complexity Actually Go?

Optimizations	Worst-case per `find`
Neither	O(n)
Union by rank only	O(log n)
Path compression only	O(log n) amortized
Both together	O(α(n)) amortized

Robert Tarjan proved the O(α(n)) bound in 1975. He also proved it tight: you cannot do asymptotically better with pointer-based algorithms of this type. That second proof is the annoying one.

The inverse Ackermann function α(n) grows so slowly that α(9876!) = 5. For any n you will encounter in an interview, a production system, or honestly anywhere in the observable universe, α(n) ≤ 5. The O(α(n)) notation is the formal way of saying "yes, constant, but we don't want to write O(1) and lie to Tarjan." The amortized cost per operation is constant in every meaningful sense.

Space is O(n) for parent plus O(n) for rank. Path compression adds nothing.

One Structure, Every Language

A complete Union-Find with path compression and union by rank. The union function returns true if the two elements were in different groups (i.e., a merge happened) and false if they were already connected.

class UnionFind:
    def __init__(self, n: int) -> None:
        self.parent = list(range(n))
        self.rank = [0] * n

    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, x: int, y: int) -> bool:
        rx, ry = self.find(x), self.find(y)
        if rx == ry:
            return False
        if self.rank[rx] < self.rank[ry]:
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        return True

Which Interview Problems Actually Need This

Interviewers rarely ask you to design Union-Find from scratch. They hand you a graph problem and expect you to recognize the shape. The pattern: you need to answer "are these two nodes connected?" efficiently, and connectivity changes as edges are added.

Problems that reward path compression:

LeetCode 200 (Number of Islands): most solutions use DFS or BFS, but Union-Find handles dynamic variants more cleanly
LeetCode 547 (Number of Provinces): textbook connected components counting
LeetCode 684 (Redundant Connection): adding an edge between two already-connected nodes creates the cycle; union returning false detects it
LeetCode 721 (Accounts Merge): non-integer elements; map strings to integers first, then apply Union-Find
LeetCode 1319 (Number of Operations to Make Network Connected): check if enough edges exist before counting components

For a deeper problem list, the guide on Union-Find problems ranks them by pattern.

The common mistake is writing Union-Find without path compression, timing out on the large test case, and spending ten minutes convinced it's a runtime environment issue before finally checking the find function. If your find is recursive and doesn't have parent[x] = find(parent[x]), you do not have path compression. The two versions look identical at a glance. One of them is O(n) and will fail.

The second mistake: adding path compression but skipping union by rank. Each optimization helps independently. Together they hit O(α(n)). Without rank, adversarial inputs still force O(log n) per operation, which is fine for most problems but technically wrong if you told the interviewer you're running at α(n).

Practice the Explanation Out Loud

Writing Union-Find is one skill. Explaining it under pressure is another. Interviewers want to hear "without compression, find degrades to O(n) on chains" and "compression flattens the tree on every traversal so future lookups are essentially free." That sentence does not come out clean the first time you try to say it live.

SpaceComplexity runs voice-based mock interviews where the AI implements Union-Find alongside you and follows up on the complexity claims. Worth one rep before your actual interview, if only to avoid the "so what is the inverse Ackermann function exactly" follow-up.