Sign in
Skip to solution
hardDSA

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

119 views
01

Understand the problem

Explain union-find.

union-find
02

Attempt it yourself

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

Nudge consolestandby

Stuck? Beam a request up — the console returns a conceptual nudge that guides your logic without spoiling the implementation.

03

Study the solution

Union-Find tracks elements partitioned into disjoint sets with two ops: find (which set) and union (merge sets). With path compression and union by rank it runs in near-O(1) amortized — used for connectivity, cycle detection, and Kruskal's MST.

Solution ready — 2 min read

Classified // press E to declassify

04

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
05

Join the discussion

Discussion (0)

Sign in to join the discussion.

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

Transmission complete // awaiting log

KEEP THE
STREAK ALIVE.

Dossier 127 of 127 decoded in the Data Structures & Algorithms track. One more won't hurt.

Back to track

Track complete

You decoded the whole Data Structures & Algorithms. Legend.

Pick another arena