Union-Find: The Matrix of Disjoint Sets

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 initial instinct 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 I was trying to bail out a sinking ship with a teaspoon. I was frustrated, not because I lacked effort, but because I was solving the wrong problem—I was treating connectivity as a series of pairwise checks instead of a dynamic merging process.

That’s when a friend tossed me a link to a short video about Union‑Find (also called Disjoint Set Union, DSU). I rolled my eyes at first—another data structure with a funny name? Yet, after five minutes of watching the animation of sets merging and path compression flattening trees, I felt a spark. It wasn’t just another trick; it was a different way of thinking about connectivity.

The Revelation (The Insight)

So why does Union‑Find work? Imagine you have a bunch of islands, and you keep getting messages that two islands are now connected by a bridge. Instead of redrawing the whole map each time, you only need to know which representative (or “root”) each island currently belongs to. If two islands share the same root, they’re already in the same component; if not, you attach one root to the other.

The magic lies in two simple heuristics:

1. Union by rank/size – always attach the smaller tree under the larger one. This keeps the overall depth shallow, preventing degenerate chains.
2. Path compression – whenever you look up a node’s root, you make every node on that path point directly to the root. Future lookups become almost instantaneous.

Together, they give an amortized time complexity of α(n) (inverse Ackermann), which grows so slowly that for any practical input it’s effectively O(1). In other words, each union or find operation is practically constant, and a sequence of m operations on n elements runs in O(m α(n)) ≈ O(m).

That’s the insight: Union‑Find doesn’t just store connections; it compresses the knowledge of those connections so that future queries are cheap. It’s like keeping a living summary of the network that updates itself on the fly.

Wielding the Power (Code & Examples)

Before – The Naïve Attempt

def count_components_naive(n, edges):
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)
        adj[v].append(u)

    visited = [False] * n
    def dfs(node):
        visited[node] = True
        for nei in adj[node]:
            if not visited[nei]:
                dfs(nei)

    groups = 0
    for i in range(n):
        if not visited[i]:
            dfs(i)
            groups += 1
    return groups

This works, but building the adjacency list and running DFS for every component is O(n + e) per query if you need to answer many connectivity checks online. In interview settings where you get a stream of union operations and occasional queries, this approach quickly becomes a bottleneck.

After – Union‑Find in Action

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank   = [0] * n          # rank ≈ tree 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):
        rx, ry = self.find(x), self.find(y)
        if rx == ry:                     # already together
            return
        # Union by rank
        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

Why this is beautiful:

• find collapses the path, so the next time you ask for the root of any node on that path, you get it in one step.
• union never makes a tall tree because it always attaches the shallower tree under the deeper one.

Now let’s tackle two classic LeetCode problems.

1. Number of Islands (LeetCode 200)

def numIslands(grid):
    if not grid: return 0
    rows, cols = len(grid), len(grid[0])
    uf = UnionFind(rows * cols)
    water = rows * cols                 # extra node for all water cells

    def idx(r, c): return r * cols + c

    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '0':
                uf.union(idx(r, c), water)   # treat water as a single set
            else:
                if r + 1 < rows and grid[r+1][c] == '1':
                    uf.union(idx(r, c), idx(r+1, c))
                if c + 1 < cols and grid[r][c+1] == '1':
                    uf.union(idx(r, c), idx(r, c+1))

    # Count distinct roots that are not water
    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)

We treat each land cell as a node; water cells are merged into a dummy node so we can ignore them later. Each union/find is practically O(1), giving us O(rows × cols) overall—linear in the board size.

2. Friend Circles (LeetCode 547)

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

Again, we sweep the matrix once, unioning direct friends. The final set of roots tells us how many separate circles exist. The algorithm runs in O(n²) time (the input size) and O(n) space—optimal for this problem.

Common Traps to Avoid

• Forgetting path compression – if you only implement naive find, you can degrade to O(n) per operation in the worst case (think a long chain).
• Union without rank/size – attaching arbitrarily can also create tall trees; always union by rank or size to keep the depth logarithmic.
• Mis‑counting components – remember to query find on each element after all unions, because intermediate parents may still be stale.

Why This New Power Matters

Mastering Union‑Feel like you’ve unlocked a cheat code for any problem that asks about dynamic connectivity. Whether it’s counting regions in a grid, detecting cycles in an undirected graph, merging accounts, or even offline queries like “are these two nodes connected after adding these edges?”—Union‑Find gives you a clean, near‑constant‑time tool that scales gracefully.

The best part? The concept is tiny enough to fit on a sticky note, yet powerful enough to replace whole BFS/DFS traversals in many interview scenarios. Once you internalize the two heuristics, you’ll start seeing opportunities to apply them everywhere—sometimes in places you never imagined a “set” could help.

So go ahead, grab a piece of paper, sketch out a few union operations, watch the trees flatten, and feel that rush when the algorithm finally clicks. It’s like finding the Triforce in Zelda when the puzzle finally solves itself—pure satisfaction.

Your turn: pick a LeetCode problem that involves connectivity (try “Accounts Merge” or “Satisfiability of Equality Equations”), implement Union‑Find from scratch, and share your breakthrough in the comments. I can’t wait to hear how your own quest unfolds!