Union-Find: The Fellowship of the Set

The Quest Begins (The "Why")

I still remember the first time I stared at a LeetCode problem that asked me to count how many separate groups of friends existed in a social network. My first impulse was to throw a nested loop at it, compare every pair, and mark visited nodes. The code worked on the tiny examples, but as soon as the input size crept past a few thousand, my solution started to feel like trying to move a mountain with a teaspoon—slow, painful, and doomed to timeout.

That frustration sparked a question: Is there a way to keep track of “who’s with whom” without repeatedly scanning the whole list? The answer turned out to be a data structure that feels almost magical when you first see it: Union‑Find (also called Disjoint Set Union, DSU). It’s the kind of tool that, once you grasp it, makes a whole class of graph‑connectivity problems click into place.

The Revelation (The Insight)

What the structure actually stores

Imagine each element starts off in its own isolated house. We want two operations:

1. Find(x) – tell me which house (the “representative”) x currently belongs to.
2. Union(x, y) – merge the houses of x and y so they become part of the same group.

If we could answer Find in near‑constant time and Union in near‑constant time, we could process a sequence of connections in almost linear time overall.

Why path compression works

The naive Find simply follows parent pointers up to the root. In the worst case (think a linked list), that’s O(n) per call. Path compression changes the game: every time we walk up to find a root, we make each node we passed point directly to that root.

Think of it like a shortcut in a maze. After you’ve discovered the exit, you mark every turn you took with a sign that points straight to the exit. The next time anyone walks that corridor, they zip straight out. Over many operations, the amortized cost of Find drops to the inverse Ackermann function α(n), which grows so slowly it’s practically a constant (< 5 for any n you’ll ever encounter).

Why union by rank/size helps

If we always attach the deeper tree under the shallower one, we keep the overall height of the trees low. Without this heuristic, a series of unions could still produce a skinny tree, and even with path compression we’d be doing extra work. By union‑by‑rank (or size), we guarantee that the tree height grows at most logarithmically, and combined with path compression we get that amazing α(n) bound.

The “aha!” moment

When I first saw the code, I felt like I’d uncovered a hidden spell in an old tome: a few lines that turned an O(n²) nightmare into something that could breeze through 10⁶ elements in a blink. It’s the kind of insight that makes you want to shout, “I did it!”—and then immediately go look for more problems to apply it to.

Wielding the Power (Code & Examples)

The basic Union‑Find class (Python)

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

    def find(self, x):
        # path compression: make every node on the path point to root
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:               # already in the same set
            return False
        # union by rank: attach smaller tree under larger one
        if self.rank[rx] < self.rank[ry]:
            self.parent[rx] = ry
        elif self.rank[rx] > self.rank[ry]:
            self.parent[ry] = rx
        else:
            self.parent[ry] = rx
            self.rank[rx] += 1
        return True

Why this is the “after” – Compare it to the naïve approach:

# Naïve O(n²) version for counting components
components = [set([i]) for i in range(n)]
for u, v in edges:
    # search which set contains u and v (linear scan)
    set_u = next(s for s in components if u in s)
    set_v = next(s for s in components if v in s)
    if set_u is not set_v:
        set_u.update(set_v)
        components.remove(set_v)

Every find or union in the naïve version walks through potentially O(n) elements; the Union‑Find version does it in almost constant time.

Real interview problem #1: Number of Islands

LeetCode 200 – Number of Islands

Given a 2‑D grid of '1' (land) and '0' (water), count the number of distinct islands (4‑directionally connected land).

def numIslands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)
    # helper to convert (r,c) -> id
    def idx(r, c): return r * cols + c

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                # union with right neighbor
                if c + 1 < cols and grid[r][c+1] == '1':
                    uf.union(idx(r, c), idx(r, c+1))
                # union with down neighbor
                if r + 1 < rows and grid[r+1][c] == '1':
                    uf.union(idx(r, c), idx(r+1, c))

    # count unique roots among land cells
    roots = set()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                roots.add(uf.find(idx(r, c)))
    return len(roots)

What changed?

Instead of running a DFS/BFS for each unvisited land cell (O(mn) time, O(mn) stack/queue), we make a single pass, union neighboring lands, and then count distinct representatives. The overall complexity is O(mn α(mn)), effectively linear.

Real interview problem #2: Friend Circles

LeetCode 547 – Number of Provinces (also known as Friend Circles)

Given an n x n matrix isConnected where isConnected[i][j] = 1 means person i is directly friends with person j, return the number of friend circles.

def findCircleNum(isConnected):
    n = len(isConnected)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i+1, n):          # only upper triangle needed
            if isConnected[i][j]:
                uf.union(i, j)
    # each distinct root is a circle
    return len({uf.find(i) for i in range(n)})

Again, we avoid the O(n³) Floyd‑Warshall‑style scan and get almost linear time thanks to Union‑Find.

Common traps to avoid

1. Forgetting path compression – If you implement find as a simple loop without updating parents, you lose the amortized guarantee and can degrade to O(n) per operation.
2. Union without rank/size – Always attaching one tree arbitrarily can create deep chains; union‑by‑rank (or size) keeps the tree shallow.
3. Off‑by‑one errors in indexing – Especially when mapping 2‑D coordinates to a 1‑D ID (idx = r * cols + c). Double‑check your bounds.

Why This New Power Matters

Mastering Union‑Find is like gaining a reusable spell slot in your algorithmic toolbox. Suddenly, problems that ask about connectivity, components, or “are these two nodes in the same cluster?” become trivial. You can tackle:

• Dynamic connectivity (adding edges over time) – just call union as edges appear.
• Minimum Spanning Tree via Kruskal’s algorithm – sort edges, then union them while counting weight.
• Grid‑based puzzles (image labeling, percolation, maze generation).

The best part? The data structure is tiny: two integer arrays of size n. No fancy libraries, no hidden constants. Once you internalize the two heuristics—path compression and union by rank—you’ll start seeing opportunities to apply them everywhere.

Your turn

Pick a problem you’ve previously solved with DFS/BFS or brute force, refactor it using Union‑Find, and notice the speed difference. Share your before/after times in the comments—I love seeing those “I can’t believe it’s that fast!” moments.

Now go forth, fellow adventurer, and may your sets always stay united! 🚀