Union-Find (also called Disjoint Set Union, or DSU) answers one question extremely fast, over and over: “are these two things in the same group?” It underlies connected-components problems, Kruskal’s minimum spanning tree, and any “merge these into groups, then query membership” pattern — all with two tiny operations: findfind and unionunion.

What you’ll learn

• The parent-array representation of disjoint sets.
• Path compression — flattening a tree every time you findfind through it.
• Union by rank/size — always attaching the shorter tree under the taller.
• Why the combination is near $O(1)$ amortized: the inverse Ackermann function $\alpha(n)$.
• Counting connected components with a DSU.

The problem: grouping things that get merged over time

Imagine friendships forming one pair at a time: “0 and 1 are friends,” “1 and 2 are friends,” and so on. At any point you want to answer “are xx and yy in the same friend group?” in as close to $O(1)$ as possible — even though the groups keep merging. That’s exactly what DSU is built for.

The naive version: a parent array

Each element starts as its own group (its own root). findfind walks up parentparent pointers until it hits a node that is its own parent (the root). unionunion connects two groups by pointing one root at the other.

class NaiveUnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # each node starts as its own root
 
    def find(self, x):
        while self.parent[x] != x:      # walk up until we hit a root
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a   # attach one tree under the other
 
 
uf = NaiveUnionFind(6)
uf.union(0, 1)
uf.union(1, 2)
uf.union(1, 3)
uf.union(1, 4)
uf.union(1, 5)   # always attaching the same way builds a long chain
 
print("parents:", uf.parent)
print("find(5):", uf.find(5))   # walks the whole chain -- O(n) worst case

class NaiveUnionFind:
    def __init__(self, n):
        self.parent = list(range(n))   # each node starts as its own root
 
    def find(self, x):
        while self.parent[x] != x:      # walk up until we hit a root
            x = self.parent[x]
        return x
 
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a != root_b:
            self.parent[root_b] = root_a   # attach one tree under the other
 
 
uf = NaiveUnionFind(6)
uf.union(0, 1)
uf.union(1, 2)
uf.union(1, 3)
uf.union(1, 4)
uf.union(1, 5)   # always attaching the same way builds a long chain
 
print("parents:", uf.parent)
print("find(5):", uf.find(5))   # walks the whole chain -- O(n) worst case

This works, but nothing stops the tree from degenerating into a straight line — findfind on the deepest node becomes $O(n)$.

  graph TD
    N0["0 (root)"]
    N1["1"] --> N0
    N2["2"] --> N1
    N3["3"] --> N2
    N4["4"] --> N3

Path compression: flatten as you go

Every time findfind walks up to the root, path compression re-points every node it passed directly at the root. The next findfind on any of those nodes is then a single hop.

  graph TD
    R0["0 (root)"]
    N1["1"] --> R0
    N2["2"] --> R0
    N3["3"] --> R0
    N4["4"] --> R0

Union by rank: never grow the chain on purpose

Path compression alone helps, but pairing it with union by rank (attach the shallower tree under the deeper one, so tree height only grows when two equally-tall trees merge) keeps trees flat from the start instead of relying on repair after the fact.

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n   # number of distinct components
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # path compression
        return self.parent[x]
 
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False   # already in the same group
 
        # union by rank: attach the shorter tree under the taller one
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
 
        self.count -= 1
        return True
 
 
uf = UnionFind(7)
edges = [(0, 1), (1, 2), (3, 4), (5, 6), (2, 3)]
for a, b in edges:
    uf.union(a, b)
 
print("connected components:", uf.count)
print("0 and 4 connected?", uf.find(0) == uf.find(4))
print("0 and 5 connected?", uf.find(0) == uf.find(5))

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n   # number of distinct components
 
    def find(self, x):
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])   # path compression
        return self.parent[x]
 
    def union(self, a, b):
        root_a, root_b = self.find(a), self.find(b)
        if root_a == root_b:
            return False   # already in the same group
 
        # union by rank: attach the shorter tree under the taller one
        if self.rank[root_a] < self.rank[root_b]:
            root_a, root_b = root_b, root_a
        self.parent[root_b] = root_a
        if self.rank[root_a] == self.rank[root_b]:
            self.rank[root_a] += 1
 
        self.count -= 1
        return True
 
 
uf = UnionFind(7)
edges = [(0, 1), (1, 2), (3, 4), (5, 6), (2, 3)]
for a, b in edges:
    uf.union(a, b)
 
print("connected components:", uf.count)
print("0 and 4 connected?", uf.find(0) == uf.find(4))
print("0 and 5 connected?", uf.find(0) == uf.find(5))

Counting connected components: Number of Provinces

A near drop-in application: given an adjacency matrix, union every connected pair, then count the distinct roots.

def count_provinces(is_connected):
    n = len(is_connected)
    parent = list(range(n))
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
 
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j] == 1:
                union(i, j)
 
    return len({find(i) for i in range(n)})
 
 
matrix = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
]
print("provinces:", count_provinces(matrix))

def count_provinces(is_connected):
    n = len(is_connected)
    parent = list(range(n))
 
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
 
    def union(a, b):
        ra, rb = find(a), find(b)
        if ra != rb:
            parent[ra] = rb
 
    for i in range(n):
        for j in range(i + 1, n):
            if is_connected[i][j] == 1:
                union(i, j)
 
    return len({find(i) for i in range(n)})
 
 
matrix = [
    [1, 1, 0],
    [1, 1, 0],
    [0, 0, 1],
]
print("provinces:", count_provinces(matrix))

Why it’s (almost) O(1): the inverse Ackermann function

With both path compression and union by rank, a sequence of $m$ findfind and unionunion operations on $n$ elements costs:

where $\alpha(n)$ is the inverse Ackermann function — it grows so slowly that $\alpha(n) < 5$ for any $n$ you could ever actually construct (far beyond the number of atoms in the observable universe). In practice, treat findfind and unionunion as $O(1)$.

Time and space complexity

LeetCode problem set

Practice — real LeetCode problems

Each exercise is the actual LeetCode problem with its real method signature and LeetCode’s own examples as the test. Write the body, press Run, and match the expected output.

LC 990 — Satisfiability of Equality Equations · Medium

Problem. Given equations of the form "a==b""a==b" or "a!=b""a!=b" over single lowercase letters, return TrueTrue if some assignment of integers satisfies all of them.

Constraints. 1 <= len(equations) <= 5001 <= len(equations) <= 500, each string has length 4 and is well-formed.

Examples. ["a==b","b!=a"]["a==b","b!=a"] gives FalseFalse · ["b==a","a==b"]["b==a","a==b"] gives TrueTrue · ["a==b","b==c","a==c"]["a==b","b==c","a==c"] gives TrueTrue · ["a==b","b!=c","c==a"]["a==b","b!=c","c==a"] gives FalseFalse

LC 721 — Accounts Merge · Medium

Problem. Each account is [name, email1, email2, ...][name, email1, email2, ...]. Two accounts belong to the same person if they share any email. Merge them, returning each person as their name followed by their emails in sorted order.

Constraints. 1 <= len(accounts) <= 10001 <= len(accounts) <= 1000, 2 <= len(accounts[i]) <= 102 <= len(accounts[i]) <= 10.

Examples. Two “John” accounts sharing johnsmith@mail.comjohnsmith@mail.com merge into one with all three emails; a separate “John” with a different email stays separate.

LC 128 — Longest Consecutive Sequence · Medium

Problem. Given an unsorted array, return the length of the longest run of consecutive integers present (the elements need not be adjacent in the array). Must run in $O(n)$.

Constraints. 0 <= len(nums) <= 10^50 <= len(nums) <= 10^5, -10^9 <= nums[i] <= 10^9-10^9 <= nums[i] <= 10^9.

Examples. [100,4,200,1,3,2][100,4,200,1,3,2] gives 44 (the run 1,2,3,41,2,3,4) · [0,3,7,2,5,8,4,6,0,1][0,3,7,2,5,8,4,6,0,1] gives 99 · [][] gives 00

Recap

• DSU tracks disjoint groups with a parentparent array: findfind walks to the root, unionunion connects two roots.
• Path compression flattens every path it walks; union by rank keeps trees short from the start.
• Together, both optimizations make findfind/unionunion run in $O(\alpha(n))$ amortized — effectively constant time in practice.
• The classic application is connected components: union every known connection, then count (or query) distinct roots.

Next: Sorting Algorithms — where these core structures become building blocks for faster comparisons and partitioning.