The Fellowship of the Set: Union-Find from Theory to LeetCode

The Quest Begins (The "Why")

I still remember the first time I saw a LeetCode problem that asked me to count the number of islands in a grid. My gut reaction was to scan every cell, run a DFS, and mark visited land. It worked, but the solution felt… clunky. I kept thinking there had to be a cleaner way to keep track of which cells belonged to the same island without revisiting them over and over.

Later, while preparing for a system design interview, I stumbled upon a question about dynamically adding friendships in a social network and querying whether two people are in the same circle. Again, I found myself writing a naive adjacency list and running BFS each time—O(N²) in the worst case. The frustration was real. I felt like I was swinging a sword at a hydra: every time I cut one head, two more grew back.

That’s when I decided to dig into Union‑Find, also known as Disjoint Set Union (DSU). I wanted a tool that could merge groups instantly and answer “are these two in the same group?” in almost constant time. The promise was tantalizing: near‑O(1) per operation after a little preprocessing.

The Revelation (The Insight)

The magic of Union‑Find isn’t just in the code; it’s in the way we think about connectivity. Imagine each element starts in its own isolated house. When we get a request to unite two houses, we don’t rebuild the whole neighborhood—we just point the roof of one house to the roof of the other. Over time, many houses will point, directly or indirectly, to the same roof, which we call the representative or root of the set.

Two simple heuristics make this blazing fast:

1. Union by rank (or size) – always attach the smaller tree under the root of the larger tree. This keeps the overall height shallow.
2. Path compression – whenever we look up the root of a node, we make every node on that path point directly to the root. The next time we ask for the root, it’s a single hop.

Together, they give us an amortized time complexity of α(N) per operation, where α is the inverse Ackermann function—so slow‑growing that for any realistic N it’s practically a constant. It felt like Neo dodging bullets in the Matrix when path compression kicked in: the operations just whooshed by, almost invisible.

Why does this work? Because we never need to know the exact shape of the set; we only need a reliable way to tell if two elements share the same root. The heuristics guarantee that the tree depth stays logarithmic in the worst case and, thanks to path compression, practically constant after a few finds.

Wielding the Power (Code & Examples)

Let’s see the theory in action. Below is a compact Union‑Find class in Python, followed by two classic LeetCode problems where it shines.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * n          # stores approximate depth

    def find(self, x):
        # Path compression
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr:
            return False               # already in the same set
        # Union by rank
        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

Problem 1: Number of Islands (LeetCode 200)

Naive DFS/BFS – O(MN) time, O(MN) extra space for the visited matrix or recursion stack.

Union‑Find solution – treat each land cell as a node. Scan the grid; for each '1', union it with its upper and left neighbor (if they are also land). At the end, count distinct roots among all land cells.

def numIslands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)
    land = 0

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                land += 1
                idx = r * cols + c
                if r > 0 and grid[r-1][c] == '1':
                    uf.union(idx, (r-1) * cols + c)
                if c > 0 and grid[r][c-1] == '1':
                    uf.union(idx, r * cols + (c-1))

    # Count unique roots of land cells
    roots = set()
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                roots.add(uf.find(r * cols + c))
    return len(roots)

Why it’s better:

• No recursion depth worries.
• The inner loops are simple O(1) operations thanks to Union‑Find.
• Overall time: O(MN α(MN)) ≈ O(MN). Space: O(MN) for the parent/rank arrays (still linear, but we avoid the extra visited matrix if we reuse the grid).

Problem 2: Friend Circles (LeetCode 547)

Given an N×N matrix M where M[i][j] = 1 means person i and j are direct friends, friend circles are the transitive closure of this relation.

Naive approach: DFS from each unvisited person → O(N²) time, O(N) space.

Union‑Find approach: Union every pair of friends directly from the matrix, then count distinct roots.

def findCircleNum(M):
    n = len(M)
    uf = UnionFind(n)
    for i in range(n):
        for j in range(i+1, n):
            if M[i][j] == 1:
                uf.union(i, j)
    return len({uf.find(i) for i in range(n)})

Analysis:

• The double loop touches each edge once → O(N²) unions.
• Each union/find is α(N) → total O(N² α(N)) ≈ O(N²).
• Space: O(N) for parent/rank.

Common Traps

1. Forgetting path compression – If you implement find recursively without updating parents, the tree can stay tall, degrading to O(N) per operation in the worst case.
2. Union by rank vs. size confusion – Using rank incorrectly (e.g., always attaching x to y) can still work but may lose the logarithmic guarantee; keep the rule: attach the lower‑rank tree under the higher‑rank one.

Why This New Power Matters

With Union‑Find in your toolbox, you stop thinking about “traversing the whole graph every time” and start thinking about “maintaining groups as they evolve.” Dynamic connectivity problems—whether they’re about percolation, social networks, or even Kruskal’s minimum spanning tree—become straightforward.

You’ll notice interviewers smiling when you mention “near‑constant amortized time” instead of launching into a lengthy DFS explanation. It signals that you know how to pick the right abstraction for the job, not just hammer every nail with the same screwdriver.

Most importantly, it’s fun. Watching a bunch of isolated nodes snap together into coherent sets with just a couple of lines feels like watching a puzzle solve itself.

Your Turn

Grab a LeetCode problem that involves grouping or connectivity—Number of Provinces, Accounts Merge, Satisfiability of Equality Equations—and try solving it with Union‑Find first. If you hit a snag, drop a comment; I love hearing where the journey gets tricky and celebrating the breakthroughs together.

Now go forth, unite those sets, and may your finds always be compressed! 🚀