Union Find: Components, Islands and Connectivity

Learning Outcome

Use DSU for dynamic connectivity, merged accounts, island additions, and offline edge-limit queries.

Pattern Recognition

Intuition

DSU keeps only the component representative, which is enough for connectivity questions.

Exact Practice Question Names

• Accounts Merge
• Graph Valid Tree
• Number of Islands II
• Smallest String With Swaps
• Checking Existence of Edge Length Limited Paths

Interview Approach

1. Initialize parent[i] = i.
2. Use path compression in find.
3. Union by rank or size.
4. For weighted offline queries, sort edges and queries by threshold before unioning.

Pseudocode

find(x):
  if parent[x] != x: parent[x] = find(parent[x])
  return parent[x]
union(a,b):
  ra = find(a); rb = find(b)
  if ra != rb: attach smaller to larger
  

Sample Dry Run

For accounts merge, every shared email unions two account indices. After all unions, each root collects its sorted emails.

Edge Cases

• Duplicate union
• Grid cell already activated
• Owner name should not be part of DSU key
• Queries with strict less-than edge limit

Common Mistakes

• No path compression
• Unioning names instead of emails/accounts
• Forgetting 2D to 1D id conversion

Complexity

Java, C++ and Python Notes

• Java: prefer explicit classes and clear helper methods over clever one-liners.
• C++: use vector, unordered_map, set, priority_queue, and long long when sums can grow.
• Python: keep state readable with dict, set, deque, heapq, and lru_cache where appropriate.

Quick Revision Checklist

• Name the pattern before coding.
• State the invariant or DP state in one sentence.
• Dry-run the smallest non-trivial example.
• Close with time and space complexity.