Union-Find

Union-Find (also called Disjoint Set Union or DSU) is a data structure that tracks elements partitioned into disjoint sets.

Two Core Operations:

• •Find(x): Which set does x belong to? (Returns the root/representative)
• •Union(x, y): Merge the sets containing x and y

Visual Representation:

When to Use Union-Find:

• •Dynamic connectivity (are X and Y connected?)
• •Counting connected components
• •Detecting cycles in undirected graphs
• •Grouping related items (accounts, friends)
• •Kruskal's MST algorithm

Key Insight: Union-Find answers connectivity queries efficiently without storing the actual graph structure.

The core idea: use a parent array where parent[i] points to i's parent. The root of a set points to itself.

Initial State:

After union(1, 2):

Find Operation: Follow parent pointers until reaching root (where parent[x] == x)

Problem: Without optimization, find() can be O(n) if tree becomes a long chain.

Solution: Path compression - while finding root, make all nodes point directly to root.

Before Path Compression:

After Path Compression on find(4):

Implementation: During find, update each node's parent to the root.

Watch how union and find operations work with path compression. See trees merge and flatten in real-time.

Problem: Even with path compression, bad union order creates tall trees.

Solution: Always attach the shorter tree under the taller one.

Union by Rank:

Rank: Approximate height of tree (upper bound due to path compression)

A common use case: track the number of disjoint sets.

Approach: Start with n components, decrease by 1 on each successful union.

Example: Number of Provinces

Watch how union operations merge components and reduce the component count.

Key Insight: If we try to union two nodes that are ALREADY connected, we've found a cycle!

Algorithm:

1. •Process each edge (u, v)
2. •If find(u) == find(v), adding this edge creates a cycle
3. •Otherwise, union(u, v)

Example: Redundant Connection

For grid problems, flatten 2D coordinates to 1D index.

Index Mapping: (row, col) → row * numCols + col

Example: Number of Islands using Union-Find

Sometimes you need to track the SIZE of each component, not just connectivity.

Use Cases:

• •Find largest connected component
• •Making A Large Island (flip 0 to maximize island)
• •Social network largest friend group

Key Insight: Store size at root, update on union.

Example:

Problem: Merge accounts that share common emails.

Challenge: Emails are strings, but Union-Find uses integers!

Solution: Map emails to indices, union by shared emails.

Example:

Problem: Given a grid of 0s and 1s, flip at most one 0 to 1 to maximize island size.

Approach:

1. •Use Union-Find to find all islands and their sizes
2. •For each 0, check adjacent island roots
3. •Calculate potential size if we flip this 0
4. •Track maximum

Example:

Edge Case: Grid is all 1s → return m * n

Problem: Given string s and pairs of indices that can be swapped any number of times, return lexicographically smallest string.

Key Insight: If you can swap (a,b) and (b,c), then a,b,c are all connected and can be rearranged freely!

Approach:

1. •Union all swap pairs
2. •Group indices by their root
3. •For each group, sort characters and assign smallest to smallest index

Example:

Problem: Find Minimum Spanning Tree - connect all nodes with minimum total edge weight.

Kruskal's Algorithm + Union-Find:

1. •Sort edges by weight (ascending)
2. •For each edge, if it connects two different components, add it
3. •Stop when we have n-1 edges

Why Union-Find? We need to quickly check if two nodes are already connected.

Example:

Problem: Given grid dimensions and positions added as land one at a time, return count of islands after each addition.

Challenge: Grid changes dynamically - DFS would recompute everything each time!

Union-Find Advantage: O(1) per operation vs O(m*n) for DFS.

Approach:

1. •Start with count = 0
2. •For each new land position:
   • Increment count (new island)
   • Check 4 neighbors, union if neighbor is land
   • Each successful union decrements count
3. •Record count after each addition

Example:

Problem: Given equations like ["a==b", "b!=c"], determine if all can be satisfied.

Key Insight:

• •"==" means variables are in same group
• •"!=" means variables must be in different groups

Two-Pass Approach:

1. •First pass: Process all "==" equations (union)
2. •Second pass: Verify all "!=" equations (should have different roots)

Why two passes? Must build all equality relationships before checking inequalities.

Example:

Problem: Stones on 2D plane. Remove stone if another stone shares its row OR column. Return max stones removable.

Key Insight: Stones in same row/column form connected components. Within each component of size k, we can remove k-1 stones (keeping 1).

Answer: total_stones - number_of_components

Mapping Challenge: Row 0 and Column 0 would collide! Solution: Offset columns: use row for rows, col + 10001 for columns.

Example:

Edge Cases to Handle:

1. Self-Connection

2. Empty Input

3. 1-Indexed vs 0-Indexed

4. Duplicate Operations

5. Grid Coordinate Mapping

Common Mistakes:

When to Use Union-Find:

Union-Find vs DFS/BFS:

Decision Framework:

Problem Patterns:

With Both Optimizations (Path Compression + Union by Rank):

α(n) = Inverse Ackermann function

• •For all practical n (up to 10^80), α(n) ≤ 4
• •Essentially constant time!

Space Complexity: O(n)

• •parent array: O(n)
• •rank/size array: O(n)

Without Optimizations:

• •find(): O(n) worst case (long chain)
• •union(): O(n) (calls find)

Comparison:

Problem-Specific Complexity:

Why Path Compression Works: Every find() flattens part of the tree. Over m operations, total work is O(m × α(n)), meaning each operation is O(α(n)) amortized.

Complete Union-Find Template:

When to Add Size Tracking:

• •Need largest component
• •Need component size queries
• •Making A Large Island type problems

Grid Problems Setup:

String Key Problems:

Cycle Detection:

Two-Pass Pattern:

Interview Tips:

• •Always implement with both optimizations
• •Return boolean from union() for flexibility
• •Track count for component problems
• •Draw the tree structure when debugging
• •Remember: find() has side effects (path compression)