Union Find (Disjoint Set)

What is Union Find?

Union Find (Disjoint Set Union) tracks elements partitioned into disjoint sets. It supports near O(1) operations for finding which set an element belongs to and merging sets.

Quick Recognition: Problems involving grouping, connectivity, or dynamic component counting. Keywords: “connected components”, “group together”, “same group”, “cycle detection”.

Pattern Recognition Cheatsheet — When the LeetCode prompt says X, reach for Union-Find:

Phrase in the Problem	What to Reach For
”number of connected components” / “provinces”	Union-Find, count distinct roots
”redundant connection” / “find the edge that creates a cycle”	UF: first edge whose endpoints share a root is the answer
”cycle detection in undirected graph”	Same as above (UF cannot detect directed cycles)
“accounts merge” / “merge groups by shared identifiers”	UF on the identifiers (emails, IDs), then group by root
”dynamic / online connectivity” — edges added one at a time	UF — each addition is O(alpha(n)), beats re-running BFS
”number of islands II” — land added incrementally	UF with on-the-fly node creation
”smallest string with swaps” / “swap-equivalent groups”	UF on indices, sort within each group
”graph valid tree?”	UF — check (cycle-free AND fully connected AND exactly n-1 edges)
“Kruskal’s MST”	UF as the cycle-detection backbone
”evaluate division” / “ratios via equations”	Weighted UF — each edge stores ratio to parent
”satisfiability of equations”	UF on equality constraints, then validate inequalities against components
”minimum number of edges to connect graph”	UF — answer is (component count - 1)

UF excels at INCREMENTAL connectivity. If edges are static and you only need one query, BFS / DFS may be simpler. UF cannot handle edge DELETIONS efficiently — for that, use offline processing in reverse or rollback UF without path compression.

Pattern Recognition Checklist

Use Union Find When

Counting connected components
Checking if two nodes are connected
Cycle detection in undirected graphs
Dynamic connectivity queries
Kruskal’s MST algorithm
Grouping elements by some relation

Don't Use When

Need shortest path (use BFS/Dijkstra)
Directed graph cycle detection (use DFS)
Need to traverse paths
Static graph (BFS/DFS might be simpler)

Complexity Reference

Operation	Without Optimization	With Path Compression + Union by Rank
Find	O(n)	O(alpha(n)) nearly O(1)
Union	O(n)	O(alpha(n)) nearly O(1)
Connected	O(n)	O(alpha(n)) nearly O(1)

alpha(n) = inverse Ackermann function, grows extremely slowly

When to Use

Connected Components

Counting groups, checking connectivity

Cycle Detection

Detect cycles in undirected graphs

Dynamic Connectivity

Online queries about connectivity

MST Algorithms

Kruskal’s algorithm

Implementation

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n  # Number of components
    
    def find(self, x):
        """Find root with path compression"""
        if self.parent[x] != x:
            self.parent[x] = self.find(self.parent[x])
        return self.parent[x]
    
    def union(self, x, y):
        """Union by rank"""
        root_x, root_y = self.find(x), self.find(y)
        
        if root_x == root_y:
            return False  # Already connected
        
        # Attach smaller tree under larger
        if self.rank[root_x] < self.rank[root_y]:
            root_x, root_y = root_y, root_x
        
        self.parent[root_y] = root_x
        if self.rank[root_x] == self.rank[root_y]:
            self.rank[root_x] += 1
        
        self.count -= 1
        return True
    
    def connected(self, x, y):
        """Check if in same component"""
        return self.find(x) == self.find(y)

Pattern Variations

1. Number of Islands (Union Find approach)

def num_islands(grid):
    """Count islands using Union Find"""
    if not grid:
        return 0
    
    rows, cols = len(grid), len(grid[0])
    
    def index(r, c):
        return r * cols + c
    
    uf = UnionFind(rows * cols)
    land_count = 0
    
    for r in range(rows):
        for c in range(cols):
            if grid[r][c] == '1':
                land_count += 1
                
                # Union with adjacent land
                for dr, dc in [(0, 1), (1, 0)]:
                    nr, nc = r + dr, c + dc
                    if 0 <= nr < rows and 0 <= nc < cols and grid[nr][nc] == '1':
                        if uf.union(index(r, c), index(nr, nc)):
                            land_count -= 1
    
    return land_count

2. Accounts Merge

def accounts_merge(accounts):
    """Merge accounts with common emails"""
    from collections import defaultdict
    
    email_to_id = {}
    email_to_name = {}
    
    # Map emails to indices
    for account in accounts:
        name = account[0]
        for email in account[1:]:
            if email not in email_to_id:
                email_to_id[email] = len(email_to_id)
            email_to_name[email] = name
    
    uf = UnionFind(len(email_to_id))
    
    # Union emails in same account
    for account in accounts:
        first_email = account[1]
        for email in account[2:]:
            uf.union(email_to_id[first_email], email_to_id[email])
    
    # Group emails by root
    root_to_emails = defaultdict(list)
    for email, idx in email_to_id.items():
        root = uf.find(idx)
        root_to_emails[root].append(email)
    
    # Build result
    result = []
    for emails in root_to_emails.values():
        emails.sort()
        name = email_to_name[emails[0]]
        result.append([name] + emails)
    
    return result

3. Redundant Connection (Cycle Detection)

def find_redundant_connection(edges):
    """Find edge that creates cycle"""
    n = len(edges)
    uf = UnionFind(n + 1)
    
    for u, v in edges:
        if not uf.union(u, v):
            return [u, v]  # This edge creates cycle
    
    return []

Classic Problems

Problem	Pattern	Key Insight
Number of Islands	Grid connectivity	2D to 1D mapping
Accounts Merge	Email grouping	Union emails, group by root
Redundant Connection	Cycle detection	Edge creating cycle
Longest Consecutive	Value connectivity	Union consecutive numbers
Kruskal’s MST	Edge processing	Union in weight order

Interview Problems by Company

Medium
Hard

Problem	Company	Key Concept
Number of Provinces	All FAANG	Basic connectivity
Redundant Connection	Google, Amazon	Cycle detection
Accounts Merge	Meta, Amazon	Email grouping
Satisfiability	Google	Equality constraints

Problem	Company	Key Concept
Swim in Rising Water	Google	Binary search + UF
Largest Component	Meta	Size tracking
Making A Large Island	Amazon	Virtual unions
Bricks Falling	Google	Reverse time

Interview Tips

How to Explain Your Approach

Script for interviews:

“I’ll use Union Find for efficient connectivity queries.”
“I’ll implement with path compression and union by rank.”
“Find operation compresses the path to root.”
“Union attaches smaller tree under larger.”
“Both operations are nearly O(1) amortized.”

Union Find Template

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n
    
    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, x, y):
        px, py = self.find(x), self.find(y)
        if px == py:
            return False
        if self.rank[px] < self.rank[py]:
            px, py = py, px
        self.parent[py] = px
        if self.rank[px] == self.rank[py]:
            self.rank[px] += 1
        self.count -= 1
        return True

Common Variations

Variation	Use Case
Track component size	Largest component problems
Weighted Union Find	Equations, ratios
2D to 1D mapping	Grid problems: i * cols + j
Virtual nodes	Connect to boundary/source

Why Path Compression + Union-by-Rank Together?

Each optimization alone is good but not great. Together they hit the theoretical optimum.

Path compression alone -> amortized O(log n) per operation. After many find calls, the tree flattens, but a single bad union sequence can rebuild a deep tree.
Union by rank alone -> worst-case O(log n) per operation. The rank rule keeps tree height at most log n, but every find walks the full path.
Both together -> amortized O(alpha(n)) per operation. Tarjan’s 1975 result. alpha(n) is the inverse Ackermann function — for any input size you will ever encounter (up to 2^65536), alpha(n) <= 4. Effectively constant.

Why does the combination beat the sum of the parts? Union by rank guarantees the tree is balanced at union time — so initial path lengths are bounded. Path compression then PERMANENTLY flattens during traversals — so once a node has been touched by a find, its future find calls are O(1). The two effects compound: rank keeps trees shallow; compression amortizes the cost of any remaining deep paths over future queries. Use one without the other and you give up one of these guarantees. In interviews, when you implement UF, always include BOTH. Skipping one is a red flag — interviewers know which line was missed.

Worked LeetCode Problems

These five cover every common UF interview pattern: basic component counting (547), undirected cycle detection (684), grouping by shared identifier (721), dynamic / online land additions (305), and minimum-cost connectivity (1319).

LC 547 — Number of Provinces (Medium)

Given an isConnected[i][j] adjacency matrix of cities, count the connected groups (provinces). Trivial UF: union every connected pair, return the component count.

def findCircleNum(isConnected):
    n = len(isConnected)
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]              # Path compression
            x = parent[x]
        return x
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx != ry:
            parent[rx] = ry
            return True
        return False
    for i in range(n):
        for j in range(i+1, n):
            if isConnected[i][j]:
                union(i, j)
    return len({find(i) for i in range(n)})

Time O(n^2 alpha(n)), space O(n). The DFS variant is also clean — use whichever you find easier; UF is slightly safer on huge dense matrices.

LC 684 — Redundant Connection (Medium, undirected cycle detection)

A tree on n nodes has exactly n-1 edges. Add one extra and you create exactly one cycle. Find that extra edge — return the LAST such edge in the input order.

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n + 1))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    for u, v in edges:
        ru, rv = find(u), find(v)
        if ru == rv:
            return [u, v]                              # Adding this edge creates the cycle
        parent[ru] = rv
    return []

Why it works: process edges in order. Before each union, check if both endpoints already share a root. If yes, this edge is redundant — adding it would close a cycle. If no, perform the union. Since the input has exactly one extra edge over a tree, the FIRST collision is the answer (and given the problem’s “return the last one in the input” framing, that lines up because all edges before the extra are tree edges, never causing a collision).

LC 721 — Accounts Merge (Medium)

Each account has a name and a list of emails. Two accounts belong to the same person if they share any email. Output merged accounts with sorted emails.

from collections import defaultdict

def accountsMerge(accounts):
    parent = {}
    email_to_name = {}
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx != ry: parent[rx] = ry
    for account in accounts:
        name = account[0]
        first_email = account[1]
        for email in account[1:]:
            if email not in parent:
                parent[email] = email
            email_to_name[email] = name
            union(first_email, email)
    groups = defaultdict(list)
    for email in parent:
        groups[find(email)].append(email)
    result = []
    for emails in groups.values():
        emails.sort()
        result.append([email_to_name[emails[0]]] + emails)
    return result

The trick: union AT THE EMAIL LEVEL (not the account-index level). Two accounts share a person iff they share any email; the natural unifying entities are emails.

LC 305 — Number of Islands II (Hard, online / dynamic UF)

Given a sequence of addLand(r, c) operations, return the island count after each operation. Pure DFS / BFS is O(K * m * n) — TLE. UF is O(K * alpha(K)).

def numIslands2(m, n, positions):
    parent = {}
    count = 0
    result = []
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])
        return parent[x]
    for r, c in positions:
        idx = r * n + c
        if idx in parent:
            result.append(count)                       # Already land
            continue
        parent[idx] = idx
        count += 1
        for dr, dc in [(0,1),(0,-1),(1,0),(-1,0)]:
            nr, nc = r+dr, c+dc
            nidx = nr * n + nc
            if 0 <= nr < m and 0 <= nc < n and nidx in parent:
                ri, rn = find(idx), find(nidx)
                if ri != rn:
                    parent[ri] = rn
                    count -= 1                         # Two components merged
        result.append(count)
    return result

The “lazy” UF — initialize a node only when its land arrives — avoids allocating an m*n array when the grid is sparse.

LC 1319 — Number of Operations to Make Network Connected (Medium)

You have n computers and a list of cables. Find the minimum number of cable rearrangements to make all n computers connected, or -1 if impossible.

def makeConnected(n, connections):
    if len(connections) < n - 1:
        return -1                                      # Not enough cables
    parent = list(range(n))
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]
            x = parent[x]
        return x
    components = n
    for u, v in connections:
        ru, rv = find(u), find(v)
        if ru != rv:
            parent[ru] = rv
            components -= 1
    return components - 1                              # n components -> 1 needs n-1 moves

The insight: any extra cable (one that already connects same-component computers) can be relocated to bridge two different components. So as long as len(connections) >= n-1, the answer is (component count - 1).

Caveats and Traps

Trap 1 — Implementing UF without path compression OR without union by rank. Without both, find degrades to O(log n) at best, O(n) at worst. On a chain-style union sequence (union(0,1), union(1,2), ..., union(n-1,n)), find on the deepest node walks the entire chain.

Solution: Always include BOTH path compression in find AND union-by-rank (or union-by-size) in union. The combination is what gives you amortized O(alpha(n)). Skipping one is a red flag interviewers actively look for.

Trap 2 — Path compression that compresses only the immediate parent. A common bug: writing parent[x] = parent[parent[x]] once instead of recursively pointing to the root. This is “path halving” — better than nothing, but loses the full O(alpha(n)) bound.

Solution: Either recursive find with parent[x] = find(parent[x]) (full path compression), or an iterative two-pass find (first walk to root, then second pass setting every node’s parent to root). Both achieve full compression.

Trap 3 — Confusing union by SIZE vs union by RANK. They are different invariants. Size tracks the exact count of nodes; rank is an upper bound on tree height. Mixing the two (if size[x] < rank[y]) is a silent bug.

Solution: Pick one and stick to it. Union by size has a practical bonus — size[root] gives you the component size for free, which many problems need. Union by rank is conceptually cleaner if you do not need sizes. Both achieve the same asymptotic bound.

Trap 4 — Using UF for directed cycle detection. UF treats union(a, b) and union(b, a) identically — direction information is lost. On a directed graph, two nodes “in the same component” doesn’t tell you whether the cycle is consistent with edge directions.

Solution: For undirected cycle detection, UF is perfect. For directed graphs, use DFS with three-color marking, or Kahn’s BFS (cycle iff result has fewer than V nodes).

Trap 5 — Trying to undo a union after path compression. Path compression is destructive — once a node is rewired to point directly at the root, you cannot recover its previous parent without storing it. Rolling back a union after subsequent finds is essentially impossible.

Solution: If your problem requires rollback (e.g., offline dynamic connectivity, divide-and-conquer on time), use rollback UF: union by rank with NO path compression, plus a history stack of (node, old_parent, old_rank) tuples. Each operation is O(log n) instead of O(alpha(n)), but you can undo. This is the standard pattern for offline dynamic connectivity.

Curated LeetCode List

Difficulty	Problem	LC #	Pattern
Easy	Number of Provinces	547	Basic UF / connected components
Easy	Find if Path Exists in Graph	1971	UF or DFS for connectivity
Easy	Find the Town Judge	997	Degree counting (not strictly UF, related)
Medium	Redundant Connection	684	Cycle detection in undirected graph
Medium	Accounts Merge	721	UF on string identifiers
Medium	Number of Connected Components	323	UF or DFS
Medium	Graph Valid Tree	261	UF: cycle-free + connected + V-1 edges
Medium	Smallest String With Swaps	1202	UF on indices, sort within groups
Medium	Satisfiability of Equality Equations	990	UF on equality, validate inequality
Medium	Evaluate Division	399	Weighted UF (or DFS with ratios)
Medium	Connecting Cities With Minimum Cost	1135	MST via Kruskal + UF
Medium	Min Cost to Connect All Points	1584	MST via Kruskal + UF
Medium	Number of Operations to Make Network Connected	1319	UF, components - 1
Hard	Number of Islands II	305	Online / dynamic UF
Hard	Swim in Rising Water	778	UF + sorted edges (or Dijkstra)
Hard	Bricks Falling When Hit	803	Reverse-time UF
Hard	Most Stones Removed with Same Row or Column	947	UF on rows + columns
Hard	Couples Holding Hands	765	UF on couple indices, count merges

Solve order: 547 -> 684 -> 721 -> 1319 -> 1202 (one week of medium UF) -> 305 -> 803 (the hard online / time-reversal patterns).

Union-Find Interview Q&A

Detect redundant edge in a tree (LC 684) — full walkthrough

Strong Answer Framework:

Recognize: tree on n nodes has exactly n-1 edges. The input has n edges. The extra one creates exactly one cycle.
Process edges in order. Before unioning, check if endpoints already share a root.
If yes -> this edge closes the cycle -> return it.
If no -> perform the union and continue.
Since the problem guarantees exactly one cycle, the FIRST collision is the answer.

Real LeetCode Example — LC 684 Redundant Connection:

def findRedundantConnection(edges):
    n = len(edges)
    parent = list(range(n + 1))                        # 1-indexed nodes
    rank = [0] * (n + 1)
    def find(x):
        while parent[x] != x:
            parent[x] = parent[parent[x]]              # Path compression
            x = parent[x]
        return x
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx == ry:
            return False                               # Already connected
        if rank[rx] < rank[ry]: rx, ry = ry, rx
        parent[ry] = rx
        if rank[rx] == rank[ry]: rank[rx] += 1
        return True
    for u, v in edges:
        if not union(u, v):
            return [u, v]
    return []

Time O(n alpha(n)), space O(n).

Senior follow-up 1 — What about LC 685 (directed version)? Directed redundant connection is much harder. Three cases: (a) a node has two parents (in-degree 2) -> the redundant edge is one of those two; (b) a cycle exists -> remove the cycle-closing edge; (c) both — node has two parents AND a cycle. Need to disambiguate. The standard solution: detect the in-degree-2 node, try removing each of its incoming edges, run UF on the rest — if it forms a valid tree, that was the redundant edge.

Senior follow-up 2 — What if the graph could have multiple redundant edges? The problem becomes “find an edge in any cycle” (multiple valid answers exist). Process edges; the FIRST union that fails identifies SOME redundant edge. To find ALL redundant edges, run a full DFS-based bridge / cycle algorithm: edges NOT in the DFS spanning tree are exactly the cycle-closing edges.

Senior follow-up 3 — How does this scale to a graph with 1B edges? A 1B-element parent array is ~4 GB — fits on one beefy machine but tight. Path compression keeps finds near-constant. The bottleneck is not algorithmic but I/O — reading 1B edges from disk dominates. Use streaming UF: read edges in chunks, apply unions in memory. For distributed UF (graph spread across machines), each machine owns a subset of nodes; unions across machines require network coordination. This is what Pregel-style frameworks handle.

Common Wrong Answers:

Iterating edges twice — once to build the graph, once to detect cycle via DFS. Works but slower and more code than the one-pass UF approach.
Returning the LAST collision when the problem asks for the answer that appears LAST in the input. For LC 684’s input format, the first collision IS the answer; returning the last only matters in problems with multiple cycles.
Forgetting that nodes are 1-indexed. Allocating parent = list(range(n)) instead of list(range(n+1)) is an off-by-one that crashes on the largest node.

Further Reading: LC 684, LC 685 (directed version), LC 261 (Graph Valid Tree).

Accounts Merge — full walkthrough (LC 721)

Strong Answer Framework:

Recognize: “accounts merge if they share an email” -> connectivity via shared email -> UF.
The unifying entity is the EMAIL, not the account index. Two accounts may share an email; the email is what links them.
Use a parent dict keyed by email string (no need to map to integers).
For each account, union the first email with every other email in that account.
Group emails by their root, sort each group, prepend the name.

Real LeetCode Example — LC 721 Accounts Merge:

from collections import defaultdict

def accountsMerge(accounts):
    parent = {}
    email_to_name = {}
    def find(x):
        if parent[x] != x:
            parent[x] = find(parent[x])                # Path compression
        return parent[x]
    def union(x, y):
        rx, ry = find(x), find(y)
        if rx != ry: parent[rx] = ry
    for account in accounts:
        name = account[0]
        first_email = account[1]
        for email in account[1:]:
            if email not in parent:
                parent[email] = email
            email_to_name[email] = name
            union(first_email, email)
    groups = defaultdict(list)
    for email in parent:
        groups[find(email)].append(email)
    result = []
    for emails in groups.values():
        emails.sort()
        result.append([email_to_name[emails[0]]] + emails)
    return result

Time O(N * M * alpha(N * M) + N * M log(N * M)) where N is account count and M is average emails per account. The sort dominates.

Senior follow-up 1 — What if there are 100M accounts? String UF is wasteful — every find does a hash lookup. Map every email to an integer ID first, then run UF on integers. Use an array-based parent. The hashing happens once during ID assignment, not on every operation. Memory: ~8 bytes per email ID instead of ~50 bytes per string. This is a 5x memory reduction and roughly 2-3x speedup.

Senior follow-up 2 — What if accounts arrive as a stream? Same algorithm — UF is naturally online. Each new account: assign IDs to any new emails, union the first email with the rest. Track group membership lazily — only collapse to “merged accounts” when queried. The challenge is OUTPUT freshness: every union potentially merges existing groups, so the cached “current account list” needs invalidation. Use lazy materialization: store unions, materialize the merged-account view only on demand.

Senior follow-up 3 — Why is UF cleaner than BFS / DFS for this problem? BFS / DFS works: build an adjacency list (account_index -> list of account_indexes that share at least one email), then traverse. But building the adjacency list requires comparing every pair of accounts that share an email — O(K^2) per email if K accounts share it. UF processes each email once at its account, doing O(1) unions. The complexity is fundamentally better when emails are heavily shared. Plus, UF is conceptually simpler — emails are nodes, accounts are edge groups.

Common Wrong Answers:

Unioning ACCOUNT INDICES instead of emails. You then have to figure out which accounts share emails BEFORE unioning — which is the original problem you were trying to solve. Circular.
Forgetting to sort each merged email list. The problem requires lexicographic order; missing this fails ~30% of test cases.
Using the FIRST email’s name as the account name vs the original first account’s name. The problem wants the name from the FIRST account that contained that email. Multiple email_to_name writes overwrite — be careful or the wrong name appears.

Further Reading: LC 721, LC 947 (Most Stones Removed), LC 952 (Largest Component Size by Common Factor).

Path compression and union by rank — why both?

Strong Answer Framework:

Each optimization individually gives O(log n) per operation amortized.
Together they give O(alpha(n)) — effectively constant for all real-world inputs.
Path compression flattens the tree during find, making future calls cheap.
Union by rank prevents creation of deep trees during union.
The two effects compound: rank limits initial depth; compression flattens any remaining depth.

Real LeetCode Example — pattern shows up in any UF problem; here using LC 547:

class UnionFind:
    def __init__(self, n):
        self.parent = list(range(n))
        self.rank = [0] * n
        self.count = n
    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, x, y):
        rx, ry = self.find(x), self.find(y)
        if rx == ry: return False
        if self.rank[rx] < self.rank[ry]:              # UNION BY RANK
            rx, ry = ry, rx
        self.parent[ry] = rx
        if self.rank[rx] == self.rank[ry]:
            self.rank[rx] += 1
        self.count -= 1
        return True

Senior follow-up 1 — Construct a sequence of unions that forces O(log n) tree depth WITHOUT path compression but WITH union by rank. Build n / 2 single-node trees. Pairwise union them — n / 4 trees of rank 1. Pairwise union those — n / 8 trees of rank 2. Continue. After log(n) rounds, you have one tree of rank log(n) and depth log(n). This is the worst case for union by rank alone — depth is exactly log(n). Path compression then collapses these paths at the first find, but without compression you pay log(n) per find forever.

Senior follow-up 2 — Why is the inverse Ackermann function the right bound? Tarjan’s 1975 proof partitions nodes by their rank into log* n classes. Each class contributes at most O(alpha(n)) work amortized over a sequence of operations. The matching lower bound (Fredman-Saks 1989) shows that O(alpha(n)) is essentially optimal — no comparison-based data structure can do better. So UF with both optimizations is provably optimal for dynamic connectivity.

Senior follow-up 3 — Path halving vs full path compression — practical difference. Path halving sets parent[x] = parent[parent[x]] during traversal — every other node points to its grandparent. Full compression rewrites every node to point directly to the root. Both achieve O(alpha(n)) amortized. Halving is faster in practice (no recursion, fewer cache misses) but slightly worse asymptotic constants. For interviews, full compression is the canonical answer; for production hot paths, path splitting / halving can be a measurable win.

Common Wrong Answers:

Implementing only path compression and claiming O(alpha(n)). The bound requires both. Path compression alone is O(log n) amortized.
Implementing only union by rank. Gives O(log n) per operation worst case — better than nothing but not the famous result.
Path compression that only updates the immediate child of root. Misunderstanding the recursion — the line parent[x] = find(parent[x]) updates EVERY node on the path during the recursive walk back.

Further Reading: Tarjan and van Leeuwen, “Worst-case Analysis of Set Union Algorithms” (1984). LC 547, LC 1319, LC 305.

Practice Roadmap

Day 1: Basic Union Find

Solve: Number of Provinces, Redundant Connection
Focus: Implement find with path compression, union by rank

Day 2: Grid Problems

Solve: Number of Islands (UF approach), Surrounded Regions
Focus: 2D to 1D coordinate mapping

Day 3: Advanced Applications

Solve: Accounts Merge, Satisfiability of Equations
Focus: Grouping with additional data

Day 4: Hard Problems

Solve: Swim in Rising Water, Making A Large Island
Focus: Combining UF with other techniques

Interview Tip: When you see “connected components” or “group elements”, think Union Find. It’s especially powerful when components are built incrementally.

Interview Questions

Q1: Explain how path compression works in Union Find and why it matters

What interviewers are really testing: Whether you understand the internal mechanics beyond just memorizing the template. They want to see if you know why the data structure is fast, not just that it is fast.Strong Answer:

Path compression is an optimization applied during the find operation. When you traverse from a node up to the root, you make every node along that path point directly to the root. This flattens the tree structure over time.
Without it, the tree can degenerate into a linked list (imagine union-ing 1->2->3->…->n in order), making find O(n). With path compression, repeated find calls amortize down to O(alpha(n)) — the inverse Ackermann function, which is effectively constant (never exceeds 4 for any practically possible input size, even n = 2^65536).
The implementation is elegant — one line of recursion: if self.parent[x] != x: self.parent[x] = self.find(self.parent[x]). The key insight is that this is not just caching the root — it physically rewires the parent pointer for every node on the path, so future traversals for any of those nodes are O(1).
A subtle point: path compression alone gives O(log n) amortized. You need both path compression and union by rank/size together to achieve O(alpha(n)). Most candidates miss this distinction.

Red flag answer: “It just makes find faster by remembering the root” without explaining the pointer rewiring mechanism, or claiming path compression alone gives O(1).Follow-ups:

What is the difference between path compression, path splitting, and path halving? When would you choose one over the other?
Path compression makes find mutate state. What problems does this cause if you need to undo unions (e.g., in a backtracking algorithm)?

Q2: Union by rank vs union by size — what is the difference, and does it matter?

What interviewers are really testing: Depth of understanding about the why behind design choices. Many candidates memorize one variant without understanding the trade-offs or even knowing the other exists.Strong Answer:

Union by rank tracks the upper bound on tree height. When merging, the shorter tree goes under the taller one. Rank only increases when two trees of equal rank merge.
Union by size tracks the exact number of nodes in each tree. The smaller tree goes under the larger one.
Both achieve the same asymptotic complexity — O(alpha(n)) when combined with path compression. The theoretical bound is identical.
The practical difference: union by size is more useful in many interview problems because size[root] gives you the exact component size at any time. Problems like “largest component after merging” or “count elements in a group” need size tracking anyway, so union by size pulls double duty.
Rank has a subtle advantage: after path compression, size values of non-root nodes become stale (they are never updated), but rank was always just an upper bound, so path compression does not violate its semantics.
My default in interviews: use union by size, because the extra information (exact component size) is free and frequently needed. I only switch to rank if the problem specifically does not need sizes and I want a cleaner implementation.

Red flag answer: Saying they are the same thing, or not knowing that union by size exists as a distinct strategy.Follow-ups:

If you are tracking component sizes, what happens to the size values of non-root nodes after path compression? Does that matter?
Can you modify the Union Find to efficiently answer “what is the size of the largest component” at any point? What is the time complexity?

Q3: When would you choose Union Find over BFS/DFS for a connectivity problem?

What interviewers are really testing: Engineering judgment — not just knowing the data structure, but knowing when it is the right tool. The interviewer wants to see trade-off analysis, not a one-size-fits-all answer.Strong Answer:

Choose Union Find when edges arrive incrementally (online/streaming setting). For example, “process edges one by one and after each edge, report the number of connected components.” BFS/DFS would require rebuilding the graph and re-traversing every time — O(V+E) per query. Union Find handles each edge in O(alpha(n)).
Choose Union Find when you only need connectivity answers (are A and B connected? how many components?), not path information. If you need the actual shortest path or any specific path, Union Find cannot help — use BFS.
Choose BFS/DFS when the graph is static and you only query once. Building Union Find over all edges and then querying is the same complexity as a single BFS/DFS traversal, but with higher constant factors and more code.
Choose BFS/DFS for directed graphs. Union Find inherently models undirected relationships (union is symmetric). Directed cycle detection, topological sort, strongly connected components — all need DFS.
Real-world example: Kruskal’s MST algorithm processes edges sorted by weight and uses Union Find to check if adding an edge would create a cycle. You could do this with DFS per edge, but that would be O(E * V) total vs O(E * alpha(V)) with Union Find — a massive difference on a graph with millions of edges.

Red flag answer: “I always use Union Find for graph problems” or the opposite — “I always use BFS/DFS.” Either extreme shows lack of judgment.Follow-ups:

You have a social network with 100M users and connections arrive as a real-time stream. You need to answer “are users X and Y in the same network?” with sub-millisecond latency. Which approach do you pick and why?
What if the problem requires you to remove edges (disconnect nodes)? Can Union Find handle that directly?

Q4: How does cycle detection work with Union Find, and why does it only work for undirected graphs?

What interviewers are really testing: Whether you understand the fundamental invariant that makes cycle detection work, and whether you recognize the limitations (directed vs undirected).Strong Answer:

The principle is simple: process edges one by one. Before adding edge (u, v), check if find(u) == find(v). If they already share a root, adding this edge would create a cycle — both endpoints are already connected through some existing path.
This works for undirected graphs because connectivity is symmetric. If A can reach B, B can reach A.
It fails for directed graphs because direction matters. Consider three nodes: edge A->B, edge A->C, then edge B->C. After processing the first two edges, B and C might be in the same component (if we ignore direction), but B->C does not create a cycle. Meanwhile, if the edge were C->A instead, that would be a cycle. Union Find cannot distinguish these cases because it does not track edge direction.
For directed cycle detection, you need DFS with a recursion stack (tracking “currently visiting” vs “fully visited” states), or Kahn’s algorithm (topological sort via in-degree).
Classic interview problem: Redundant Connection on LeetCode. You are given a tree plus one extra edge. Find the edge that creates the cycle. Process edges in order — the first edge where union returns false is your answer.

Red flag answer: Claiming Union Find works for directed graphs, or being unable to explain why the find-check detects a cycle (just saying “if they are already connected, it is a cycle” without explaining what “connected” means in this context).Follow-ups:

What if there are multiple redundant edges and you need to return the one that appears last in the input? Does the algorithm still work?
LeetCode has “Redundant Connection II” for directed graphs. How does the approach change, and why can you not simply use Union Find?

Q5: How would you adapt Union Find to solve problems on a 2D grid?

What interviewers are really testing: Whether you can translate abstract data structure knowledge into a concrete application. Grid problems are the #1 context where Union Find appears in interviews, and the 2D-to-1D mapping is where many candidates stumble.Strong Answer:

The core technique is coordinate flattening: map cell (r, c) to index r * cols + c. This converts a 2D grid into a 1D array that Union Find can index into.
For a grid with rows rows and cols columns, you initialize UnionFind(rows * cols).
When iterating, you only need to union with right and down neighbors (r, c+1) and (r+1, c) — not all four directions. Since we process left-to-right, top-to-bottom, the left and up neighbors were already handled when we processed those cells. This halves the number of union operations.
A common gotcha: handling water cells (0s) in an island problem. You must not union water cells. One clean approach: track a separate landCount variable, increment it when you see land, decrement it when a union succeeds (merging two land components).
Advanced variant — virtual nodes: for problems like “Surrounded Regions,” create a virtual node that represents the boundary. Union all border O-cells with this virtual node. Then any O-cell connected to the virtual node is not surrounded. This avoids BFS from every border cell.

Red flag answer: Using r + c or r * rows + c as the index formula (wrong formulas that cause collisions), or iterating all four neighbors without realizing the redundancy.Follow-ups:

In the Number of Islands problem, what are the trade-offs between a Union Find approach vs a DFS flood-fill approach? When would you prefer one over the other?
How would you handle a “Number of Islands II” problem where land cells are added one at a time and you need the component count after each addition?

Q6: What is a weighted Union Find and when would you use it?

What interviewers are really testing: Whether you know Union Find beyond the basic template. Weighted Union Find is the leap from “memorized a pattern” to “deeply understands the abstraction.” It appears in problems most candidates cannot solve.Strong Answer:

A weighted Union Find stores an additional value on each edge that represents the relationship between a node and its parent — typically a ratio or offset.
Classic use case: the “Evaluate Division” problem. You are given equations like a/b = 2.0, b/c = 3.0, and must answer queries like a/c = ?. Each node stores a weight representing its ratio to its parent. When you find(a), you multiply weights along the path to get the ratio from a to the root.
During path compression, you must update the weight: the new weight from a node to the root is the product of weights along the original path. During union, you compute the correct weight for the new edge by using the relationship: weight[rootX] = weight[y] * (value of y/x) / weight[x].
Another use case: “Is Graph Bipartite?” can be modeled as a weighted Union Find where the weight tracks parity (0 or 1 for same-side vs opposite-side).
The tricky part is getting the math right during find and union. Off-by-one errors in the weight propagation are the #1 bug. I always draw out a small example (3-4 nodes) on paper before coding.

Red flag answer: Never having heard of weighted Union Find, or confusing it with “union by weight/size.”Follow-ups:

Walk me through exactly how you would update weights during path compression for the division problem. What happens when a chain has three nodes a -> b -> c with weights 2.0 and 3.0?
What is the time complexity of weighted Union Find? Does the weighting change the amortized bounds?

Q7: Can Union Find support an undo or rollback operation? How?

What interviewers are really testing: Whether you understand why certain optimizations work and what they cost you. This question separates senior-level candidates from those who only know the template. It probes understanding of the tension between optimization and reversibility.Strong Answer:

Standard Union Find with path compression cannot be efficiently rolled back. Path compression destructively rewires parent pointers, and there is no cheap way to undo those mutations.
The solution is Union Find by rank/size without path compression, combined with a history stack. Before each union, push the old parent and rank values onto a stack. To undo, pop and restore. Each union/undo is O(log n) instead of O(alpha(n)), but that is usually acceptable.
This pattern is called rollback Union Find or Union Find with undo, and it appears in competitive programming and certain offline algorithms.
Real use case: offline dynamic connectivity. You have a sequence of edge additions and removals. Using divide-and-conquer on the time axis, you add edges for the relevant time range and roll back when backtracking. This requires rollback Union Find.
Another use case: constraint satisfaction problems where you speculatively union elements and need to backtrack if a contradiction is found.
Key insight: you cannot use path compression with rollback. This is a real trade-off — O(log n) per operation instead of O(alpha(n)), but you gain reversibility.

Red flag answer: “Just keep a copy of the parent array” (that is O(n) per snapshot, which can be prohibitively expensive), or “path compression works fine with undo” (it does not).Follow-ups:

What is the total time complexity of the divide-and-conquer approach for offline dynamic connectivity using rollback Union Find?
Could you use persistent data structures instead of a rollback stack? What are the trade-offs?

Q8: Walk me through solving the Accounts Merge problem with Union Find

What interviewers are really testing: Whether you can apply Union Find to a non-obvious, real-world-flavored problem. Accounts Merge is a Meta/Amazon favorite because it requires you to (1) see that this is a connectivity problem, (2) handle the mapping between emails and indices, and (3) reconstruct the grouped result.Strong Answer:

Step 1 — Recognize it as a connectivity problem. If two accounts share any email, they belong to the same person. This is transitive: if account A shares an email with B, and B shares one with C, all three are the same person. That screams Union Find.
Step 2 — Map emails to integer IDs. Union Find works on integer indices, not strings. Create a email_to_id dictionary. As you process each account, assign sequential IDs to new emails.
Step 3 — Union emails within each account. For each account, pick the first email as the “anchor” and union every other email in that account with it. This is O(k * alpha(n)) per account where k is the number of emails.
Step 4 — Group by root. Iterate over all emails, call find on each, and group emails by their root ID. This gives you the merged clusters.
Step 5 — Build the result. For each cluster, sort the emails, prepend the account name (stored in a separate email_to_name map), and add to the result.
Why Union Find over BFS here: both work, but Union Find is cleaner when you think of emails as nodes and “same account” as edges. The BFS approach requires building an explicit adjacency list first, which is more code and conceptually messier.

Red flag answer: Trying to union account indices instead of email indices (a very common mistake — you need to union at the email level because two different account entries can share an email), or forgetting to handle the email-to-name mapping.Follow-ups:

What is the time complexity of your solution? Break it down by step.
If accounts are arriving as a stream (you do not have all accounts upfront), how would your approach change?

Q9: What is the inverse Ackermann function and why does it appear in Union Find analysis?

What interviewers are really testing: Intellectual curiosity and depth of theoretical understanding. Most candidates say “it is basically O(1)” and stop. The interviewer wants to see if you understand why this bizarre function appears and what it actually means.Strong Answer:

The inverse Ackermann function alpha(n) is the inverse of the Ackermann function A(n, n), which grows incomprehensibly fast. The Ackermann function at just A(4, 4) already exceeds the number of atoms in the observable universe.
Because the Ackermann function grows so fast, its inverse grows unbelievably slowly. For any input size you would ever encounter in practice (up to 2^65536), alpha(n) is at most 4.
It appears in the Union Find analysis because of a clever amortized argument by Tarjan (1975). The proof partitions nodes into groups based on their “log-star rank” and shows that each group contributes at most O(alpha(n)) work per operation when amortized over a sequence of m operations.
For practical purposes, you should say: “The amortized cost per operation is O(alpha(n)), which for all practical purposes is O(1). The total cost of m operations on n elements is O(m * alpha(n)).”
Why this matters beyond trivia: it means Union Find is essentially the fastest possible data structure for dynamic connectivity — there is a matching lower bound showing you cannot do better. This was proven by Fredman and Saks in 1989.

Red flag answer: “I don’t know what it is, it’s just O(1)” (shows you memorized the conclusion without understanding it), or confusing it with O(log* n) (iterated logarithm), which is a different function that appears in a weaker analysis without union by rank.Follow-ups:

What is the difference between O(alpha(n)) and O(log* n)? Which optimizations give you which bound?
You mentioned there is a matching lower bound. Does that mean we can never build a faster data structure for the same problem? What assumptions does the lower bound require?

Q10: Design a system that processes friend requests in a social network and answers 'are X and Y in the same friend circle?' in real time

What interviewers are really testing: Whether you can take the Union Find concept and apply it to a system design context with real-world constraints: scale, concurrency, persistence, and failure handling. This bridges data structures and system design.Strong Answer:

Core data structure: Union Find is the natural choice. Each friend_request(A, B) is a union(A, B). Each same_circle(A, B) is a connected(A, B) query. Both are O(alpha(n)), so sub-microsecond for individual operations.
Scale challenge: For a social network with 1B+ users, the parent array alone would be ~4GB (1B * 4 bytes). That fits in memory on a single beefy machine. But for fault tolerance and horizontal scaling, you need more.
Sharding approach: Partition users by ID range. Most friend circles are locality-clustered (people befriend people near their ID assignment time). For cross-shard unions, maintain a smaller “boundary” Union Find that tracks inter-shard connections. This is similar to how distributed Union Find works in parallel graph algorithms.
Persistence: Write union operations to a WAL (write-ahead log). On restart, replay the log to rebuild the Union Find. Periodic snapshots of the parent array reduce replay time.
Concurrency: Union Find is inherently hard to parallelize because find mutates state (path compression) and union modifies two entries. Options: (a) use a lock-free Union Find with CAS operations on the parent array (research papers exist on this), (b) use a readers-writer lock per shard, (c) accept slightly stale reads and batch unions.
Alternative at extreme scale: If real-time exact answers are not required, use an approximate approach: maintain connected components via periodic batch BFS/DFS jobs (like MapReduce connected components), and answer queries from the last computed snapshot. This trades freshness for simplicity.

Red flag answer: Just saying “use Union Find” without addressing any of the real-world concerns (memory, concurrency, persistence, fault tolerance), or immediately jumping to a database solution without considering the latency requirements.Follow-ups:

What happens when a friendship is removed? Union Find does not support efficient deletion. How would you handle unfriend operations in your system?
How would you test this system? What failure scenarios would you specifically design tests for?

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

Union Find (Disjoint Set)

What is Union Find?

Pattern Recognition Checklist

Use Union Find When

Don't Use When

Complexity Reference

When to Use

Connected Components

Cycle Detection

Dynamic Connectivity

MST Algorithms

Implementation

Pattern Variations

1. Number of Islands (Union Find approach)

2. Accounts Merge

3. Redundant Connection (Cycle Detection)

Classic Problems

Interview Problems by Company

Interview Tips

Why Path Compression + Union-by-Rank Together?

Worked LeetCode Problems

LC 547 — Number of Provinces (Medium)

LC 684 — Redundant Connection (Medium, undirected cycle detection)

LC 721 — Accounts Merge (Medium)

LC 305 — Number of Islands II (Hard, online / dynamic UF)

LC 1319 — Number of Operations to Make Network Connected (Medium)

Caveats and Traps

Curated LeetCode List

Union-Find Interview Q&A

Practice Roadmap

Interview Questions

Overview

Array & String

Search & Sort

Data Structures

Graph & Tree

Advanced Techniques

Documentation Index

​What is Union Find?

​Pattern Recognition Checklist

Use Union Find When

Don't Use When

​Complexity Reference

​When to Use

Connected Components

Cycle Detection

Dynamic Connectivity

MST Algorithms

​Implementation

​Pattern Variations

​1. Number of Islands (Union Find approach)

​2. Accounts Merge

​3. Redundant Connection (Cycle Detection)

​Classic Problems

​Interview Problems by Company

​Interview Tips

​Why Path Compression + Union-by-Rank Together?

​Worked LeetCode Problems

​LC 547 — Number of Provinces (Medium)

​LC 684 — Redundant Connection (Medium, undirected cycle detection)

​LC 721 — Accounts Merge (Medium)

​LC 305 — Number of Islands II (Hard, online / dynamic UF)

​LC 1319 — Number of Operations to Make Network Connected (Medium)

​Caveats and Traps

​Curated LeetCode List

​Union-Find Interview Q&A

​Practice Roadmap

​Interview Questions

What is Union Find?

Pattern Recognition Checklist

Complexity Reference

When to Use

Implementation

Pattern Variations

1. Number of Islands (Union Find approach)

2. Accounts Merge

3. Redundant Connection (Cycle Detection)

Classic Problems

Interview Problems by Company

Interview Tips

Why Path Compression + Union-by-Rank Together?

Worked LeetCode Problems

LC 547 — Number of Provinces (Medium)

LC 684 — Redundant Connection (Medium, undirected cycle detection)

LC 721 — Accounts Merge (Medium)

LC 305 — Number of Islands II (Hard, online / dynamic UF)

LC 1319 — Number of Operations to Make Network Connected (Medium)

Caveats and Traps

Curated LeetCode List

Union-Find Interview Q&A

Practice Roadmap

Interview Questions