The Fellowship of the Sets: Union-Find (Disjoint Set) on LeetCode

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. I tried DFS, BFS, even a naive union‑by‑checking‑every‑pair approach. My code exploded in O(n²) time and I felt like I was trying to herd cats with a broomstick. Honestly, I was ready to give up and blame the problem setter for being evil.

Then a friend whispered, “Have you heard of Union‑Find?” I shrugged, thought it sounded like some obscure math thing, and moved on. A few days later, I hit a wall again on a problem about merging accounts based on shared emails. That’s when I decided to give Union‑Find a real shot. What I discovered felt like finding a secret shortcut in a maze — suddenly the dragon I’d been slaying for hours turned into a docile puppy.

The Revelation (The Insight)

So what’s the magic? Union‑Find, also called Disjoint Set Union (DSU), is a data structure that keeps track of a partition of elements into disjoint (non‑overlapping) sets. It supports two operations in almost constant time:

1. Find(x) – tells you which set x belongs to (the “representative” or root).
2. Union(x, y) – merges the sets containing x and y.

The beauty lies in two simple tricks:

• Path compression – when we follow parent pointers to find a root, we make every node on the way point directly to that root. Future finds become shortcuts.
• Union by size/rank – we always attach the smaller tree under the larger one, keeping the overall tree shallow.

Why does this give us near‑O(1) amortized time? Think of each Find as pulling a rope tight. Path compression shortens the rope each time you pull it, and union by size ensures you never tie a thick rope to a thin one — so the rope never gets too long. Over a sequence of m operations on n elements, the total work is bounded by O((n + m) α(n)), where α is the inverse Ackermann function — a number that grows so slowly it’s practically ≤ 5 for any conceivable input. In interview terms, we treat it as O(1).

When I first saw the proof, I was shocked. It felt like when Neo dodges bullets in The Matrix — everything just clicked, and the seemingly impossible became trivial.

Wielding the Power (Code & Examples)

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

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # each node is its own parent
        self.size   = [1] * n          # size of each tree (for union by size)

    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:
            return False                 # already in the same set
        # Union by size: attach smaller tree under larger one
        if self.size[rx] < self.size[ry]:
            rx, ry = ry, rx              # ensure rx has larger size
        self.parent[ry] = rx
        self.size[rx] += self.size[ry]
        return True

Common traps

• Forgetting path compression – you’ll still get correct answers, but the runtime can degrade to O(log n) per op, which feels fine until you hit the worst‑case test.
• Union without size/rank – attaching arbitrarily can create tall trees, turning Find into a linear scan.
• Using recursion for find in languages with low stack limits – an iterative loop is safer in C++/Java.

Problem 1 – Number of Connected Components (LeetCode 323)

Given n nodes labeled 0…n‑1 and a list of undirected edges, return the number of connected components.

The solution is just a Union‑Find walk:

def countComponents(n, edges):
    uf = UnionFind(n)
    for u, v in edges:
        uf.union(u, v)
    # count distinct roots
    return sum(1 for i in range(n) if uf.find(i) == i)

Each edge triggers a near‑constant‑time union, and the final pass is O(n). Overall O(n + m) → effectively linear.

Problem 2 – Accounts Merge (LeetCode 721)

Merge accounts that share at least one email. Return each merged account with name and sorted emails.

We treat each email as a node. When we see an email in an account, we union it with the first email of that account. After processing all accounts, we gather emails by their root and prepend the account name.

def accountsMerge(accounts):
    email_to_name = {}
    email_id = {}
    i = 0
    for acc in accounts:
        name = acc[0]
        for email in acc[1:]:
            email_to_name[email] = name
            if email not in email_id:
                email_id[email] = i
                i += 1

    uf = UnionFind(i)
    for acc in accounts:
        first = email_id[acc[1]]
        for email in acc[2:]:
            uf.union(first, email_id[email])

    from collections import defaultdict
    groups = defaultdict(list)
    for email, eid in email_id.items():
        root = uf.find(eid)
        groups[root].append(email)

    res = []
    for emails in groups.values():
        name = email_to_name[emails[0]]
        res.append([name] + sorted(emails))
    return res

Again, each union/find is amortized O(1), so the whole algorithm runs in O(N α(N)) where N is total distinct emails — essentially linear for interview constraints.

Why This New Power Matters

Mastering Union‑Find changed how I approach graph‑related interview questions. Instead of reaching for DFS/BFS every time, I now ask: “Do I just need to know whether two nodes are in the same component?” If yes, Union‑Find is often faster, simpler, and less error‑prone. It’s the go‑to tool for:

• Dynamic connectivity (adding edges over time)
• Cycle detection in undirected graphs
• Kruskal’s MST algorithm
• Problems where you need to merge groups based on a attribute (like accounts, friend circles, or even pixels in an image)

The confidence of knowing I have a near‑constant‑time “merge‑and‑query” tool in my belt makes me walk into coding interviews feeling like I’ve got a lightsaber instead of a wooden stick.

Your Turn

Grab a LeetCode problem that mentions “connected components”, “friend circles”, or “merge accounts”. Try solving it first with a naïve approach, then rewrite it using Union‑Find. Notice how the code shrinks and the speed jumps. If you get stuck, drop a comment — I love hearing about your quests and debugging war stories.

Now go forth, wield the power of disjoint sets, and may your trees always stay shallow! 🚀