Union-Find: The Force Awakens of Disjoint Sets

The Quest Begins (The “Why”)

I still remember the first time I stared at a LeetCode problem that asked me to merge groups of friends as new connections appeared. I tried a naïve approach: keep an array of lists, scan through them every time a union was requested, and honestly, it felt like trying to herd cats while blindfolded. The solution timed out on the biggest test case, and I walked away thinking, “There’s got to be a smarter way.”

That frustration led me down a rabbit hole of data‑structures, and eventually I stumbled upon the Union‑Find (also called Disjoint Set Union, DSU). At first glance it looked like just another array‑based trick, but once I grasped why it works, it felt like unlocking a secret level in a game. Suddenly, problems that once seemed like grinding through endless loops turned into quick, elegant victories.

If you’ve ever felt stuck trying to keep track of connected components while edges keep getting added, you’re in the right place. Let’s turn that frustration into power.

The Revelation (The Insight)

What Union‑Find Actually Does

Imagine you have n isolated islands. Over time, bridges are built between pairs of islands. At any moment you want to answer two questions quickly:

1. Are two islands already connected (directly or indirectly)?
2. Merge the groups containing two islands.

A naïve solution would scan all islands each time, leading to O(n²) in the worst case. Union‑Find sidesteps that by storing, for each element, a pointer to its “parent” – the representative of its set. The magic lies in two simple ideas:

1. Path Compression – When we look up the root of an element, we make every node on the path point directly to the root. Future lookups become almost instantaneous.
2. Union by Rank (or Size) – When merging two trees, we attach the smaller tree under the root of the larger one. This keeps the overall tree shallow.

Why does this give us near‑constant time? Think of each find operation as a quest to the kingdom’s capital. With path compression, every traveler we meet along the way gets a teleportation portal straight to the capital. The next time anyone from that village needs to go, they zip there in a heartbeat. Union by rank ensures we never build a ridiculously tall tower; we always keep the kingdom’s hierarchy balanced.

The amortized cost of a sequence of m find and union operations on n elements is O(m α(n)), where α is the inverse Ackermann function – a number that grows so slowly it’s practically ≤ 5 for any conceivable input. In interview land we treat it as O(1) per operation.

Why It Works (The Intuition)

The parent array essentially encodes a forest where each tree’s root is the “label” of its set. When we union two sets, we’re just picking one root to become the parent of the other. Path compression doesn’t change the logical grouping; it merely rewires the pointers so that future find calls skip unnecessary hops.

If you’re still skeptical, picture a line of people passing a bucket down the line. Without compression, each bucket has to travel the whole line every time. With compression, after the first pass everyone grabs a shortcut to the front, so the bucket arrives instantly thereafter.

Wielding the Power (Code & Examples)

Below is a compact, production‑ready Union‑Find class in Python. I’ve added comments that highlight the two optimizations.

class UnionFind:
    def __init__(self, n: int):
        self.parent = list(range(n))   # each node is its own parent
        self.rank    = [0] * n         # approximate tree depth

    def find(self, x: int) -> int:
        # Find root with path compression
        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:
        # Union by rank; returns True if a merge happened
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False                 # already in the same set
        if self.rank[xr] < self.rank[yr]:
            self.parent[xr] = yr
        elif self.rank[xr] > self.rank[yr]:
            self.parent[yr] = xr
        else:
            self.parent[yr] = xr
            self.rank[xr] += 1
        return True

Common Traps (The “Boss Fight” Mistakes)

1. Forgetting path compression – If you implement find as a simple loop without updating parents, each operation can degrade to O(log n) or worse, and you’ll miss the near‑constant benefit.
2. Union without rank/size – Always attaching one tree to another arbitrarily can produce long chains, turning the structure into a linked list in the worst case.

Real Interview Problems

Problem 1: Number of Islands (LeetCode 200)

Given a 2‑D grid of '1's (land) and '0's (water), count the number of islands. Adjacent lands horizontally or vertically belong to the same island.

Union‑Find solution: Treat each cell as a node. Scan the grid; for every land cell, union it with its top and left neighbours (if they are also land). At the end, the number of distinct roots among land cells equals the island count.

def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    uf = UnionFind(m * n)
    count = sum(cell == '1' for row in grid for cell in row)

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                idx = i * n + j
                if i > 0 and grid[i-1][j] == '1':
                    if uf.union(idx, (i-1)*n + j):
                        count -= 1
                if j > 0 and grid[i][j-1] == '1':
                    if uf.union(idx, i*n + (j-1)):
                        count -= 1
    return count

Why it shines: Instead of running a DFS/BFS for each new land cell (which could revisit cells many times), each union/find is practically O(1). The overall runtime is O(m·n) with tiny constant factors.

Problem 2: Redundant Connection (LeetCode 684)

In a tree with n nodes labeled 1…n, one extra edge is added, creating a single cycle. Return that edge.

Union‑Find solution: Iterate through edges; for each edge (u, v), if find(u) == find(v) then adding this edge would create a cycle → it’s the redundant one. Otherwise, union the sets.

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

Again, the algorithm runs in O(E α(V)) ≈ O(E) time and O(V) space — optimal for this problem.

Why This New Power Matters

Mastering Union‑Find isn’t just about passing a LeetCode test; it’s about acquiring a mental tool for any scenario where connectivity evolves over time. Think of dynamic networks, percolation studies, image processing, or even building a social‑network feature that tells you whether two users are in the same community as friendships form.

When you can answer “are these two elements connected?” in almost constant time, you free yourself from the quadratic traps that cripple many naïve solutions. You start seeing problems through a lens of sets and merges, and suddenly the seemingly daunting becomes straightforward.

I still get a grin when I watch my code zip through a giant test case in a blink — it feels like watching the Millennium Falcon jump to lightspeed after a tedious sub‑light crawl.

Your Turn

Pick a problem you’ve struggled with that involves grouping or connectivity — maybe “Friend Circles” (LeetCode 547) or “Accounts Merge” (LeetCode 721). Try reframing it with Union‑Find. Notice how the code shrinks, the runtime improves, and your confidence spikes.

What’s the first connectivity problem you’ll conquer with your new DSU super‑power? Drop your answer in the comments — let’s keep the quest going!