🔍 Introduction
Have you ever had to answer the question: “Are these two elements in the same group?” That’s exactly the kind of problem Union Find (also known as Disjoint Set Union or DSU) is built to solve.
This data structure shines in scenarios like:
Finding connected components in graphs
Implementing Kruskal's algorithm in MST
Modeling social networks (friend groups)
Detecting cycles in undirected graphs
Let’s break it down and see how powerful and elegant this structure can be.
🧠 What is Union Find / Disjoint Set?
Union Find is a data structure that keeps track of a partition of elements into disjoint (non-overlapping) sets. It supports two main operations efficiently:
Find – Determine which set a particular element belongs to
Union – Merge two sets together
For example, if we have 10 elements and some of them are connected, we can quickly answer whether any two elements are in the same connected group.
⚙️ Core Operations
🔍 Find Operation
Returns the root (or representative) of the set that an element belongs to.
Implemented using recursion or iteration, it climbs up the tree of parents until it reaches the root.
int find(int x)
{
if (parent[x] != x)
parent[x] = find(parent[x]); // Path compression
return parent[x];
}
🔗 Union Operation
Connects two disjoint sets. After a union operation, both elements share the same root.
void union(int x, int y)
{
int rootX = find(x);
int rootY = find(y);
if (rootX != rootY)
{
parent[rootY] = rootX;
}
}
⚡ Optimizations
🛣️ Path Compression
In the find function, we make the path from the node to its root shorter by pointing each node directly to the root.
This optimization flattens the structure of the tree and speeds up future operations.
📏 Union by Rank / Size
Instead of attaching one tree under another arbitrarily, we keep track of the rank (depth) or size and attach the smaller tree under the larger one. This avoids the creation of skewed trees.
void union(int x, int y)
{
int rootX = find(x);
int rootY = find(y);
if (rootX == rootY) return;
if (rank[rootX] < rank[rootY])
{
parent[rootX] = rootY;
}
else if (rank[rootX] > rank[rootY])
{
parent[rootY] = rootX;
}
else
{
parent[rootY] = rootX;
rank[rootX]++;
}
}
🌐 Real-world Use Cases
Kruskal’s Minimum Spanning Tree – Efficiently avoids cycles
Dynamic connectivity in networks – Quickly answers whether two users/devices are connected
Percolation systems – Used in simulations
Image processing – Label connected components
Friend circles – Identify communities in social networks
🧮 Memory Layout & Implementation
Union Find is commonly implemented using two arrays:
parent[]: whereparent[i]points to the parent of nodeirank[]orsize[]: used for balancing during unions
Memory Flow Example:
Initially, each element is its own parent.
parent = [0, 1, 2, 3, 4]
After union(0, 1):
parent = [0, 0, 2, 3, 4]
After union(1, 2):
find(1) → 0 → so union(0, 2)
parent = [0, 0, 0, 3, 4]
Thus, all three elements 0, 1, and 2 are now in the same group with 0 as root.
⏱️ Time Complexities
1. Find
Description: Determine the representative of a set
Time Complexity: O(α(N))
2. Union
Description: Merge two disjoint sets
Time Complexity: O(α(N))
3. Initialization
Description: Create N disjoint sets
Time Complexity: O(N)
α(N) is the inverse Ackermann function, which grows extremely slowly. For all practical purposes, it’s nearly constant.
🧪 LeetCode Practice Problems
Number of Provinces – Medium – LeetCode#547
Redundant Connection – Medium – LeetCode#684
Accounts Merge – Medium – LeetCode#721
Evaluate Division – Medium – LeetCode#399
Lexicographically Smallest Equivalent String – Medium – LeetCode#1061
Most Stones Removed with Same Row or Column – Medium – LeetCode#947
🎯 Tips for Interview
When Union Find appears in technical interviews, it's often disguised in graph-based or grouping problems. Here’s how to stay sharp:
Recognize patterns: If a problem asks you to determine if elements are connected or in the same group, think Union Find.
Start with brute force: Explain the naive solution, then introduce Union Find for optimization.
Explain optimizations clearly: Interviewers love hearing about path compression and union by rank/size.
Watch for hidden graphs: Some problems may not explicitly mention a graph—model it using DSU.
Implement quickly: Practice writing the
findandunionfunctions in your preferred language. Interviewers love speed and correctness.
💡
Pro Tip: Practice problems that ask for “connected components,” “groupings,” or “cycle detection in undirected graphs” — these are your red flags for using DSU!
🔚 Wrapping Up
Union Find might seem abstract at first, but it's incredibly useful in solving connectivity and grouping problems efficiently. With optimizations like path compression and union by rank, it becomes a supercharged tool for solving seemingly tough problems with ease.
👉 Dive into the LeetCode problems to build your muscle memory.
Happy coding! 🚀
Nitin
Hashnode | Substack | LinkedIn | GIT | Youtube | Instagram
