The Union-Find Fellowship: Finding Your Tribe Like in Lord of the Rings

The Quest Begins (The "Why")

I still remember the first time I faced a LeetCode problem that asked me to count the number of islands in a grid. My gut told me to run a DFS/BFS from every land cell, marking visited cells as I went. It worked, but the solution felt… clumsy. Every time I hit a new land cell I was essentially re‑traversing the same ocean over and over. I kept thinking, “There has to be a smarter way to know whether two cells belong to the same island without walking the whole thing each time.”

That itch led me down a rabbit hole of graph theory, and there, waiting like a hidden elven forge, was the Union‑Find (Disjoint Set Union) data structure. It sounded intimidating at first—talk of “parents”, “ranks”, and “path compression”—but once I saw the core idea, it felt like discovering the One Ring: a tiny artifact that could bind the whole kingdom together.

The Revelation (The Insight)

What problem are we really solving?

At its heart, Union‑Find answers a single question over and over: “Are these two elements in the same set?”

Think of a bunch of people at a party. As you learn who knows whom, you keep merging groups. Later, someone asks, “Do Alice and Bob belong to the same friend circle?” You need an answer fast, without recounting the whole acquaintance list each time.

How does it work?

1. Each element starts as its own set – we store a parent pointer that initially points to itself.
2. Find(x) climbs up the parent chain until it reaches a root (an element whose parent is itself). That root is the representative of the set.
3. Union(x, y) finds the roots of x and y. If they differ, we attach one root to the other, merging the sets.

If we stopped there, the structure would still work, but in the worst case a chain could become O(n) long (imagine linking 1, 2, 3, … n in a line). That’s where the two classic optimizations swoop in like Gandalf with his staff:

• Union by rank/size – always attach the smaller tree under the larger one. This keeps the tree shallow.
• Path compression – during Find, we make every node on the path point directly to the root. Future queries become almost instantaneous.

Together they give us an amortized time complexity of O(α(n)), where α is the inverse Ackermann function—so slow‑growing that for any practical input it’s effectively O(1).

Why does this feel like magic? Because we never actually traverse the whole set to answer a query; we just hop up a few pointers, flatten the path, and we’re done. The structure learns from each query, making the next one cheaper. It’s the algorithmic equivalent of leveling up after every battle.

Wielding the Power (Code & Examples)

Below is a compact, battle‑tested Union‑Find class in Python. I’ve added comments that highlight the traps I fell into the first time I wrote it.

class UnionFind:
    def __init__(self, n):
        # Each element is its own parent; rank tracks tree depth.
        self.parent = list(range(n))
        self.rank   = [0] * n          # you could also use size instead of rank

    def find(self, x):
        # Path compression: make every node on the way 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:
            return False          # already in the same set → nothing to merge
        # Union by rank: attach the shorter tree under the taller 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

Common Traps

Trap	What happens	How to avoid it
Forgetting path compression	find degrades to O(n) per call in the worst case.	Always recursively set parent[x] = find(parent[x]).
Merging without checking same root	You may create cycles and waste work.	Return early if rx == ry.
Using rank incorrectly (e.g., incrementing both)	Trees become unbalanced, hurting performance.	Only increase rank when the two trees have equal rank.

Real‑World Interview Problems

1. Number of Islands (LeetCode 200)

Naive approach: Run DFS/BFS from each '1', flood‑fill, and increment a counter. Works, but you touch each cell many times when scanning for the next unvisited land.

Union‑Find solution: Treat each land cell as a node. Whenever you see a '1', union it with its four neighbours that are also '1'. At the end, the number of distinct roots equals the number of islands.

def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    uf = UnionFind(m * n)
    islands = 0

    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                idx = i * n + j
                # count this land as a potential island
                islands += 1
                # check right and down neighbours to avoid double work
                for di, dj in ((0,1), (1,0)):
                    ni, nj = i+di, j+dj
                    if 0 <= ni < m and 0 <= nj < n and grid[ni][nj] == '1':
                        nidx = ni * n + nj
                        if uf.union(idx, nidx):
                            islands -= 1          # merged two islands
    return islands

Why it shines: Each cell is processed once, each union/find is practically O(1). Overall time O(m·n), space O(m·n) for the parent/rank arrays—same asymptotic bounds as DFS but with far less recursion stack overhead and a clearer “merge‑or‑separate” mental model.

2. Friend Circles (LeetCode 547)

Problem: Given an n × n matrix M where M[i][j] = 1 means student i is friends with j, return the number of friend circles (connected components).

Union‑Find solution: Directly union every pair (i, j) where M[i][j] == 1. The answer is the count of distinct roots.

def findCircleNum(M):
    n = len(M)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i+1, n):          # matrix is symmetric, skip duplicates
            if M[i][j] == 1:
                uf.union(i, j)
    # count unique roots
    return sum(1 for i in range(n) if uf.find(i) == i)

Why it shines: The naïve DFS would also be O(n²) but would need recursion or an explicit stack. Union‑Find lets us think in terms of “adding edges” and instantly know when two groups become one—a mindset that maps perfectly to many union‑type problems (e.g., redundant connections, dynamic connectivity).

Why This New Power Matters

Now that you’ve got Union‑Find in your toolkit, you can:

• Solve connectivity questions in near‑constant time—think of it as a Swiss‑army knife for any problem that asks “are these two nodes in the same component?”
• Avoid deep recursion—no more blowing the call stack on large grids or dense graphs.
• Think in merges rather than traversals—a subtle shift that often leads to cleaner, more intuitive code.

The beauty is that the same class works for grids, graphs, social networks, even Kruskal’s MST algorithm. Once you internalize the two tricks—union by rank and path compression—you start seeing opportunities to apply them everywhere.

Your Next Quest

Here’s a challenge to cement the power: Solve “Redundant Connection” (LeetCode 684) using the Union‑Find class above. The problem gives you a graph that started as a tree and had one extra edge added; you need to return that edge.

Give it a try, tweet your solution, or drop a comment below. And remember—every time you call find, you’re not just climbing a tree; you’re flattening the path, making the next adventurer’s journey a little easier. Happy coding! 🚀