The Fellowship of the Union-Find: From Theory to LeetCode

The Quest Begins (The "Why")

I still remember the first time I stared at a LeetCode problem that asked for the number of islands in a 2‑D grid. My brain went straight to “just flood‑fill every land cell with DFS/BFS”, and I wrote a solution that passed the easy test cases. Then the interviewer slipped in a follow‑up: “What if we could add land cells one by one and after each addition you had to report the current island count?”

Suddenly my neat DFS felt like trying to rebuild a castle after every brick was laid. I needed a data structure that could merge groups quickly and answer “are these two cells in the same group?” in almost constant time. That’s when I discovered Union‑Find, also called Disjoint Set Union (DSU). It felt like finding the secret map in a fantasy quest—once you had it, every connectivity puzzle became trivial.

The Revelation (The Insight)

What problem are we really solving?

Union‑Find maintains a collection of disjoint sets and supports two operations:

1. Find(x) – returns the representative (root) of the set containing x.
2. Union(x, y) – merges the sets containing x and y if they’re different.

The magic isn’t just that we can union two elements; it’s that we can do it almost in O(1) time, no matter how many elements we have. Why does that work?

Think of each set as a tree. The root is the “leader”. When we call Find(x), we walk up parent pointers until we hit a node that points to itself. If we stop there every time, a long chain could make Find linear.

Path compression flattens that chain on the way back: every node we visited gets its parent set directly to the root. After a few finds, the tree becomes bushy, almost flat.

Union by rank (or size) ensures we always attach the shorter tree under the taller one. This prevents us from accidentally creating a tall, skinny tree that would wreck the amortized bound.

Together, these two heuristics give us an inverse‑Ackermann amortized cost—so small that for all practical inputs we treat it as O(1) per operation. In other words, after a handful of unions and finds, the structure “learns” the shape of the data and stays fast forever.

That’s why Union‑Find shines in interview problems: it turns a potentially O(n²) connectivity check into a near‑linear sweep.

Wielding the Power (Code & Examples)

Problem 1 – Number of Islands (LeetCode 200)

Naïve DFS (the struggle):

def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    visited = [[False]*n for _ in range(m)]

    def dfs(r, c):
        if r < 0 or r >= m or c < 0 or c >= n: return
        if grid[r][c] == '0' or visited[r][c]: return
        visited[r][c] = True
        dfs(r+1, c); dfs(r-1, c); dfs(r, c+1); dfs(r, c-1)

    islands = 0
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1' and not visited[i][j]:
                dfs(i, j)
                islands += 1
    return islands

It works, but each new land addition would require a fresh DFS—too slow for the dynamic variant.

Union‑Find solution (the victory):

class DSU:
    def __init__(self, size):
        self.parent = list(range(size))
        self.rank   = [0]*size
        self.count  = 0          # number of distinct sets

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

    def union(self, x, y):
        xr, yr = self.find(x), self.find(y)
        if xr == yr: return False          # already together
        # union by rank
        if self.rank[xr] < self.rank[yr]:
            xr, yr = yr, xr
        self.parent[yr] = xr
        if self.rank[xr] == self.rank[yr]:
            self.rank[xr] += 1
        self.count -= 1
        return True

def numIslands(grid):
    if not grid: return 0
    m, n = len(grid), len(grid[0])
    dsu = DSU(m*n)
    # initially treat water as its own set; we'll only count land later
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '0':
                dsu.parent[i*n + j] = -1   # mark as water

    # union adjacent lands
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                idx = i*n + j
                if i+1 < m and grid[i+1][j] == '1':
                    dsu.union(idx, (i+1)*n + j)
                if j+1 < n and grid[i][j+1] == '1':
                    dsu.union(idx, i*n + (j+1))
    # count distinct land roots
    roots = set()
    for i in range(m):
        for j in range(n):
            if grid[i][j] == '1':
                roots.add(dsu.find(i*n + j))
    return len(roots)

Why this is faster:

We touch each cell a constant number of times (once to init, up to twice for unions). Each find/union is amortized O(1), so overall O(m·n) time and O(m·n) space—same asymptotic as DFS but with far less recursion overhead and the added ability to handle incremental updates.

Common trap: Forgetting to apply path compression in find. Without it, the tree can degenerate and you’ll end up near O(n) O(n²) in worst case.

Problem 2 – Redundant Connection (LeetCode 684)

Scenario: In a graph that started as a tree, one extra edge was added. Return that edge.

Union‑Find approach:

def findRedundantConnection(edges):
    n = len(edges)
    dsu = DSU(n+1)          # vertices are 1‑based
    for u, v in edges:
        if not dsu.union(u, v):   # union returns False if already connected
            return [u, v]
    return []

The moment we encounter an edge whose ends already share a root, we’ve found the cycle‑creating edge.

Why it works: A tree has exactly n‑1 edges and no cycles. Adding any edge must create a cycle, and the first edge that connects two already‑connected vertices is precisely the redundant one. Union‑Find detects that instantly.

Another pitfall: Using a naïve union (always attach y to x) without rank can still work for small tests but will degrade on larger inputs, turning the algorithm into O(n²).

Why This New Power Matters

Mastering Union‑Find is like acquiring a universal key for any problem that asks “are these two things connected?”.

• Dynamic connectivity – add/remove edges and query components in near‑constant time.
• Kruskal’s MST – sort edges, then union them while avoiding cycles; the DSU guarantees O(E log E) overall.
• Percolation, image segmentation, social network friend circles – all reduce to maintaining disjoint sets.

When you walk into an interview and the interviewer mentions “you have to handle up to 10⁵ union/find operations”, you can smile, pull out the DSU class, and say, “Let’s do this in almost linear time.”

The best part? The concept is tiny—just a parent array, a rank/size array, and two short functions—but its impact is huge.

Your Turn

Grab a piece of paper (or your IDE) and implement Union‑Find from scratch. Then try solving “Friend Circles” (LeetCode 547) or “Number of Connected Components in an Undirected Graph” using only the DSU.

If you get stuck, remember: the power lies in flattening the tree on the way up and always attaching the shorter tree under the taller one.

Go forth, and may your sets always stay disjoint—until you deliberately union them! 🚀