Finding the Fellowship: Union‑Find (Disjoint Set) from Theory to LeetCode

The Quest Begins (The "Why")

I still remember the first time I stared at a LeetCode problem that asked me to tell whether two nodes were in the same connected component after a series of edge additions. My initial instinct? Run a BFS/DFS for every query. It worked on the tiny examples, but the moment the test data grew to 10⁵ nodes I felt like I was trying to sweep a beach with a toothbrush—exhausting and hopelessly slow.

That frustration was the dragon I needed to slay. I kept thinking: There has to be a smarter way to keep track of groups as they merge. When a friend casually mentioned “Union‑Find” during a coffee break, I was skeptical. It sounded like some obscure data‑structure relic from a textbook. Yet, the moment I dug into it, I realized it was less a relic and more a secret weapon—one that could turn an O(n²) nightmare into almost linear time.

The Revelation (The Insight)

So what makes Union‑Find (also called Disjoint Set Union, DSU) tick? Imagine you have a bunch of islands, and every time you build a bridge you want to know which islands are now reachable from each other. The naïve way would be to redraw the whole map after each bridge. Union‑Find flips that on its head: instead of redrawing, we keep a parent pointer for each island that tells us who its “representative” is. All islands that share the same representative belong to the same set.

The magic happens in two simple tricks:

1. Union by rank/size – When we merge two sets, we attach the smaller tree under the root of the larger one. This keeps the overall depth shallow, preventing skinny chains from forming.
2. Path compression – Whenever we look up the representative of an element, we make every node on the path point directly to the root. Future lookups become O(1) because the tree gets flattened on the fly.

Together, these give an amortized time of inverse Ackermann (α(n)), which grows so slowly that for any practical input it’s basically constant. In other words, after a few unions and finds, the structure almost magically stays flat, and each operation feels like a snap of the fingers.

Why does it work? Because we never need to know the exact shape of the set—only who the leader is. The leader can change, but the invariant “all members of a set eventually point (directly or indirectly) to the same leader” never breaks. Path compression ensures that invariant is reinforced every time we query, while union by rank guarantees we don’t undo that work by creating tall trees. It’s a beautiful balance of laziness (we postpone work) and eagerness (we immediately reap the benefit).

Wielding the Power (Code & Examples)

Let’s see the spell in action. Below is a compact Python class that implements DSU with both optimizations. I’ve added comments that read like a battle‑cry—because that’s how it feels when the code finally clicks.

class DSU:
    def __init__(self, n: int):
        # parent[i] = i means i is its own leader initially
        self.parent = list(range(n))
        # size[i] = number of nodes in the tree whose root is i
        self.size = [1] * n

    def find(self, x: int) -> int:
        # Find the root while compressing the path
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])  # path halving (or full compression)
        return self.parent[x]

    def union(self, a: int, b: int) -> bool:
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False               # already in the same set
        # Union by size: attach smaller tree under larger
        if self.size[ra] < self.size[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra
        self.size[ra] += self.size[rb]
        return True

Note: The line self.parent[x] = self.find(self.parent[x]) does full path compression; you could also use halving (self.parent[x] = self.parent[self.parent[x]]) for a tad less work—both keep the amortized bound.

First Interview Problem – Redundant Connection (LeetCode 684)

You are given a graph that started as a tree (n nodes, n‑1 edges) and one extra edge was added. Find that edge.

The moment I saw this, I thought, “Just run Union‑Find while adding edges; the first edge that connects two already‑connected vertices is the culprit.”

def findRedundantConnection(edges):
    dsu = DSU(len(edges) + 1)   # nodes are labeled 1..n
    for u, v in edges:
        if not dsu.union(u, v):   # union failed → same set already
            return [u, v]

Why does this work? Because a tree has exactly n‑1 edges and no cycles. Adding any extra edge must create a cycle, and the first edge that tries to unite two vertices already in the same component is precisely that redundant edge. The DSU gives us O(n α(n)) ≈ O(n) time—linear, no DFS needed per edge.

Second Interview Problem – Number of Provinces (LeetCode 547)

Given an n x n matrix isConnected where isConnected[i][j] = 1 means city i is directly connected to city j, return the number of provinces (connected components).

Here we simply union every pair of cities that have a direct link, then count distinct roots.

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

Again, we avoid running a BFS/DFS for each node; the DSU does the heavy lifting in near‑linear time.

Common Traps (The “Bosses” to Dodge)

1. Forgetting path compression – If you only implement union by rank, you’ll still get O(log n) per operation, which is fine but not optimal. In interview settings, they often expect the almost‑constant version, so don’t skip the compression step.
2. Mis‑indexing – LeetCode loves 1‑based node labels while Python lists are 0‑based. A slip here yields “index out of range” errors that are annoying to debug mid‑interview. Always shift labels (x-1) when constructing the DSU.
3. Counting components incorrectly – After all unions, the number of sets isn’t just n - unions_successful when you union by size without tracking. Safest is to collect the roots with a set comprehension as shown.

Why This New Power Matters

Mastering Union‑Find feels like unlocking a new spell slot in your coding arsenal. Suddenly, problems that once required graph traversals, adjacency lists, or even brute‑force checks become trivial: dynamic connectivity, cycle detection, percolation, Kruskal’s MST, and even some string‑equality puzzles (LeetCode 990) bow to its efficiency.

The best part? The implementation is short enough to memorize, yet powerful enough to shave off seconds from your runtime on large test cases—something interviewers notice when they see your solution breeze through the maximal constraints while others choke on TLE.

When I first solved Redundant Connection with DSU, I felt like I’d just discovered a hidden shortcut in a maze—a shortcut that let me bypass the endless corridors of recursion and step straight to the exit. That rush of “I get it now” is why I keep coming back to this topic, and why I’m thrilled to share it with you.

---

Your turn: Grab a LeetCode problem that mentions “connected components” or “detect cycles,” implement DSU from scratch (no libraries!), and watch the clock drop. Share your runtime improvement in the comments—I love hearing how the fellowship helped you conquer the quest! 🚀