Union-Find (disjoint set union) interviews live or die on how cleanly you write the find/union boilerplate under time pressure. This section covers the exact array/map initialization idioms in Python, Java, Go, and JavaScript, the recursive-vs-iterative find trade-off, and the rank/size-based union — the mechanics, not the amortized-complexity proof (that's covered on the roadmap).
Language Verdict: Pros, Cons & Recommendation
list(range(n)) is a concise, correct one-liner for parent-array init; [0] * n is safe for the rank array since 0 is immutable- Tuple assignment (
ra, rb = rb, ra) makes the union-by-rank swap-to-normalize trick a single readable line - Dict comprehension (
{node: node for node in nodes}) mirrors the array version cleanly for non-integer or sparse ids - No boxing concerns — plain
int keys/values throughout, unlike Java's boxed Integer in a Map-based variant
- No built-in DSU/union-find structure — the same array/dict boilerplate must be hand-written every time
- CPython's recursion limit (~1000 frames) is the tightest of the three for the recursive
find() variant, reinforcing the iterative version as the safer default
new int[n] zero-initializes the rank array automatically — no explicit fill neededArrays.setAll(parent, i -> i) gives a one-line, index-aware parent-array init as an alternative to a manual loop- Primitive
int[] arrays avoid any boxing overhead in the hot find/union path - Tolerates deeper recursion than Python before
StackOverflowError, if the recursive find() variant is used
- No built-in DSU/union-find structure and no tuple type — the rank-swap in
union() needs a manual tmp variable - The
Map-based variant requires the key type to correctly implement equals/hashCode, or lookups silently misbehave for custom key classes
parent []int + rank []int with make is the most natural union-find in any of these languages — zero-fill rank, one loop for parent[i] = i- Tuple assignment (
ra, rb = rb, ra) makes the rank-swap a single readable line - Path compression + union by rank is a tiny
*UF struct with find/union methods — no boxing, no generics wart - Comparable map keys (
map[string]string) cover sparse/non-integer ids without hashCode/equals
- No built-in DSU — the same slice boilerplate must be hand-written every time (true of all four languages)
- A map-based variant returns the zero value on a missing key, so forgetting to initialize a node silently yields
0/"" instead of a loud error
Array.from({ length: n }, (_, i) => i) cleanly produces an index-aware parent array- Array-destructuring swap (
[ra, rb] = [rb, ra]) matches Python's tuple-swap ergonomics for union-by-rank Map preserves original key types and supports direct !== comparison, unlike plain objects which coerce all keys to strings- Numbers are never boxed, so no Java-style
equals/hashCode setup is needed for primitive-keyed maps
- No built-in DSU structure, and the natural-looking
new Array(n).fill(i) for parent-array init is actively wrong — it assigns the same value to every slot instead of each node's own index - Plain objects (as opposed to
Map) silently coerce all keys to strings, a real trap if a non-integer union-find variant reaches for {} instead of Map
Recommendation: None of the four ships a built-in union-find. Python's list(range(n)) and tuple swaps are the typical DSA default for speed-of-writing; Go is equally natural (make([]int, n) + tuple swap, rating 5) and a strong nice-to-have. Java's zero-init arrays come close; JS works too but watch for the Array(n).fill(i) init trap.
Coding Mechanics, Side by Side
The most common off-by-one mistake here is sizing the array to n-1 or forgetting that parent[i] should start pointing to itself (i), not to 0 or -1.
parent = list(range(n)) # parent[i] == i initially
rank = [0] * n
list(range(n)) is the idiomatic one-liner — it's both correct (each node is its own root) and fast (no Python-level loop). [0] * n is safe here specifically because 0 is immutable; the same [x] * n trick is unsafe for mutable elements like lists (see the adjacency-matrix gotcha in Graphs).
Same find/union logic as the array version — only the storage and lookup syntax change from index access to key lookup. Use this when node ids are strings, sparse, or not known to form a clean 0..n-1 range.
parent = {node: node for node in nodes}
def find(x):
while parent[x] != x:
x = parent[x]
return x
def union(a, b):
ra, rb = find(a), find(b)
if ra != rb:
parent[ra] = rb
A dict comprehension replaces list(range(n)) when ids aren't dense integers. Every parent[x] array-index becomes a dict lookup — same O(1) average cost, just hashed instead of direct.
Same recursion-depth caveat as Trees & Recursion Mechanics: a long unbalanced chain (before compression has had a chance to flatten it) can recurse deep enough to matter. See that section for the underlying stack-frame mechanics — the iterative version below is the safer default.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x]) # compress on the way back up
return parent[x]
Clean and short, but each unresolved chain link is a stack frame — on a long chain before any compression has happened, this can approach Python's recursion limit, which is the tightest of the three languages.
Two passes: walk up to find the root, then walk the same path again re-pointing every node directly to the root. This is the interview-safer default — it sidesteps the recursion-depth question entirely and is what most engineers actually ship.
def find(x):
root = x
while parent[root] != root:
root = parent[root]
while parent[x] != root:
parent[x], x = root, parent[x]
return root
First loop finds the root without mutating anything; second loop re-walks from x to root, re-pointing each node directly to root. The tuple-assignment parent[x], x = root, parent[x] reads parent[x] (the old next-hop) before overwriting it — order matters.
The exact rank-comparison logic: attach the shorter tree under the taller one's root; only bump the rank when both trees were equally tall (attaching one doesn't change the other's height otherwise).
def union(a, b):
ra, rb = find(a), find(b)
if ra == rb:
return False
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1
return True
The if rank[ra] < rank[rb]: ra, rb = rb, ra swap ensures ra is always the taller (or equal) root before attaching — avoids writing the attach logic twice for both directions. Returning a bool lets the caller track component count (see the component-counting block).
Start a counter at n (every node is its own component) and decrement it exactly once per successful union — a union that finds ra == rb didn't merge two components, so it must not decrement.
count = n
def union(a, b):
global count
ra, rb = find(a), find(b)
if ra == rb:
return
if rank[ra] < rank[rb]:
ra, rb = rb, ra
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1
count -= 1
global count is needed only if union is a free function mutating a module-level variable — wrapping everything in a small UnionFind class with self.count avoids the global keyword and is generally the cleaner interview approach.
With both path compression and union by rank (or size) applied together, each find/union operation runs in amortized O(α(n)) time, where α is the inverse Ackermann function — for any n that could ever fit in memory, α(n) ≤ 4, so this is effectively O(1) in practice. Either optimization alone still gives O(log n) amortized; it's the combination that reaches the near-constant bound. The formal proof is out of scope here (that's the roadmap's job) — the practical takeaway is: always apply both, and treat the per-operation cost as O(1) when reasoning about overall algorithm complexity in an interview.