Skip to main content
Union Find Pattern

​
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 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

OperationWithout OptimizationWith Path Compression + Union by Rank
FindO(n)O(alpha(n)) nearly O(1)
UnionO(n)O(alpha(n)) nearly O(1)
ConnectedO(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

ProblemPatternKey Insight
Number of IslandsGrid connectivity2D to 1D mapping
Accounts MergeEmail groupingUnion emails, group by root
Redundant ConnectionCycle detectionEdge creating cycle
Longest ConsecutiveValue connectivityUnion consecutive numbers
Kruskal’s MSTEdge processingUnion in weight order

​
Interview Problems by Company

ProblemCompanyKey Concept
Number of ProvincesAll FAANGBasic connectivity
Redundant ConnectionGoogle, AmazonCycle detection
Accounts MergeMeta, AmazonEmail grouping
SatisfiabilityGoogleEquality constraints

​
Interview Tips

Script for interviews:
  1. “I’ll use Union Find for efficient connectivity queries.”
  2. “I’ll implement with path compression and union by rank.”
  3. “Find operation compresses the path to root.”
  4. “Union attaches smaller tree under larger.”
  5. “Both operations are nearly O(1) amortized.”
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
VariationUse Case
Track component sizeLargest component problems
Weighted Union FindEquations, ratios
2D to 1D mappingGrid problems: i * cols + j
Virtual nodesConnect to boundary/source

​
Practice Problems

Number of Provinces

Connected components

Accounts Merge

Email grouping

Redundant Connection

Cycle detection

Longest Consecutive

Value connectivity

​
Practice Roadmap

1

Day 1: Basic Union Find

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

Day 2: Grid Problems

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

Day 3: Advanced Applications

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

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.