hardDSA

What is the Union-Find (Disjoint Set) data structure?

Q: What is the Union-Find (Disjoint Set) data structure?

**Intuition.** Union-Find tracks a collection of elements split into **disjoint groups**, with two near-instant operations: find (which group is this element in?) and union (merge two groups). Each group is a tree; the root is the group's representative. union(A,B): attach one root under the other <circle cx="80" cy="50" r="20" fill="#3b82f

118 views

Understand the problem

Explain union-find.

union-find

Attempt it yourself

Sketch your approach before reading the solution — that's what interviews test.

Stuck? AI Nudge Available

Get a conceptual hint to guide your logic without spoiling the final implementation.

Study the solution

The solution is waiting

Give it an honest attempt first — then compare your thinking with the full walkthrough.

Read the code

Union-Find with both optimizations

Run Playground

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

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

    def union(self, a, b):
        ra, rb = self.find(a), self.find(b)
        if ra == rb:
            return False                 # already connected
        if self.rank[ra] < self.rank[rb]:
            ra, rb = rb, ra
        self.parent[rb] = ra             # union by rank
        if self.rank[ra] == self.rank[rb]:
            self.rank[ra] += 1
        return True


# --- demo ---
uf = UnionFind(5)
uf.union(0, 1); uf.union(2, 3); uf.union(1, 3)
print(uf.find(0) == uf.find(2))   # True  (0-1-3-2 connected)
print(uf.find(0) == uf.find(4))   # False

Join the discussion

Discussion (0)

No responses yet. Be the first to share what you think.

How do you find the top K frequent elements?