🧩 Union Find – A Disjoint Set Structure for Connectivity Problems

🔍 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:

1. Find – Determine which set a particular element belongs to

2. 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[]: where parent[i] points to the parent of node i

• rank[] or size[]: 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

α(N) is the inverse Ackermann function, which grows extremely slowly. For all practical purposes, it’s nearly constant.

🧪 LeetCode Practice Problems

🎯 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 find and union functions in your preferred language. Interviewers love speed and correctness.

🔚 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.

🙌 Enjoying the Series?

This blog is part of my DSA series — “Level Up Your Programming with Nitin”, where I break down core data structures and algorithms with clear explanations, real-world analogies, Java code snippets, and curated LeetCode problems.

You can explore the entire series anytime here:
🔗 DS Interview Prep Series

If you find it helpful, feel free to share with peers, bookmark it for revision, or leave a ❤️ to support the effort.

🔗 Follow my blog on Hashnode: ns717.hashnode.dev
💼 Connect with me on LinkedIn: Nitin Singh

Thanks for reading, and happy coding! 💻🌳