Dashboard/Coding patterns/25. Union Find

CODING PATTERNS · LESSON 25 OF 28 · 42 MIN VIDEO · 14 PROBLEMS

Union Find

Module Progress (0 / 14 Problems Solved)0%
Coding patterns Track (0 / 28 Modules) · Overall 0/80 (0%)0%
⌁

Narrated HD Video Lesson (42 min) · Pro

Pattern Guide + Problem #01 + Checkpoint Quiz #1 are unlocked free below (no login required). Unlock all 80 HD video lessons and all 540 Python problems — or watch our two free sample video lessons first.

PATTERN STUDY GUIDE

Union Find — How the Pattern Works

Union-Find (Disjoint Set Union, or DSU) is a forest-based data structure that partitions elements into disjoint connected components while supporting dynamic merges and connectivity queries. Each component maintains a rooted tree invariant where a canonical representative (parent[root] == root) uniquely identifies the set, allowing two sets to merge by redirecting a single root pointer rather than relabeling elements. Combined with path compression and union by size/rank, both find and union execute in amortized O(α(n)) (effectively O(1)) time, reducing repeated O(V + E) graph traversals or O(n^2) component scans to near-linear complexity.

WHEN TO USE THIS PATTERN
  • Edges or elements arrive incrementally and the problem asks for dynamic connectivity, live component counts, or the exact edge that first closes a cycle.
  • Items are grouped transitively by a pairwise equivalence relation (shared row/column, shared email key, single-swap string similarity, or consecutive integer adjacency).
  • Minimum Spanning Tree construction (Kruskal's algorithm) where weighted edges (and virtual source edges) are processed cheapest-first and cycle-forming edges must be skipped.
  • Grid cells or graph paths progressively split apart over time (e.g., daily flooding), allowing offline time reversal so splits turn into incremental Union-Find merges.
  • Pairwise multiplicative ratios link variables across equations (weighted Union-Find), or painted coordinate intervals must skip already-processed slots (next_free jump pointers).
COMMON INTERVIEW PITFALLS
  • Comparing parent[a] == parent[b] instead of find(a) == find(b): parent[x] can still point to an intermediate ancestor before path compression runs, causing false negatives on connectivity checks.
  • Writing parent[b] = a instead of parent[find(b)] = find(a) during union: overwriting a non-root node's parent detaches it from its existing component and corrupts component connectivity.
  • Updating size[ra] += size[rb] or decrementing components -= 1 without checking ra != rb: merging two nodes already in the same component inflates component sizes and undercounts remaining groups.
  • Attempting to split components directly in standard Union-Find: DSU does not invert past merges, so problems where connectivity breaks over time must be processed offline in reverse chronological order.
Standard Union-Find (Path Compression + Component Size)Tracking connected components, component counts, and component sizes over integer indices 0..n-1.
parent, size = list(range(n)), [1] * 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:
        if size[ra] < size[rb]: ra, rb = rb, ra
        parent[rb] = ra
        size[ra] += size[rb]
    return ra != rb
Sparse Hash-Map Union-FindGrouping non-integer keys (strings, emails, `(r, c)` grid coordinates) or dynamically arriving items without preallocating a dense array.
parent = {}
def find(x):
    parent.setdefault(x, 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[rb] = ra
Weighted Union-Find (Pairwise Ratios)Maintaining multiplicative factors (`ratio[x] = x / parent[x]`) across transitive pairwise equations.
parent, ratio = {}, {}
def find(x):
    if parent[x] != x:
        old = parent[x]
        parent[x] = find(old)
        ratio[x] *= ratio[old]
    return parent[x]
def union(a, b, val):
    ra, rb = find(a), find(b)
    if ra != rb:
        parent[ra] = rb
        ratio[ra] = val * ratio[b] / ratio[a]
🔒 PRO PROBLEMTarget: O(n log n) time · O(n) space

10. The Skyline Problem

Pattern Trigger: fill ranges, skip filled parts → next free

Problem #01 of every pattern lesson is unlocked free outside the paywall. Unlock all 540 Python 3.14 problems, step-by-step solution editorials, and 80 narrated HD video lessons with Monthly ($69), 3-Month ($149), or Annual ($299) access — or 50% off for verified university students.

Pattern Checkpoint Quizzes

CHECKPOINT QUIZ #1

Four items have parents zero, zero, one and two. What does find return for item three?