What is the Union-Find (Disjoint Set) data structure?

Q: What is the Union-Find (Disjoint Set) data structure?

**Target Audience:** Beginners preparing for coding interviews — you should know what an array is; everything else is explained **Difficulty:** Medium **Language:** Python 3 > **How to read this doc:** Every idea is explained in plain language first, then tagged with `📌 Interview term:` so you also learn the exact word an interviewer expects. All code is Python, and every output block in the **Verified** section was copied from a real run of the examples on this page. ## 1. Why This Even Matters — A Story First Imagine a school on the first day of term. Every student starts alone. During the day, pairs of students become friends, and friendship spreads: if Ana is friends with Ben and Ben is friends with Chloe, all three are now one friend group. At any moment a teacher may ask: "are Ana and Dev in the same group?" You could keep a list of every group and, on every new friendship, copy one whole list into the other. That works, but merging big groups means moving a lot of names aro

The problem

Question presented to candidate: "Can you explain what a Union-Find, or disjoint set, data structure is, implement it in Python, and tell me how fast its operations are and why?"

What a strong answer should cover:

What it stores: a partition of elements into non-overlapping sets, each set represented by one root; the whole thing is a forest kept in a parent array.
The two operations: find(x) walks parent pointers to the root; union(a, b) links one root under the other and reports whether a merge happened.
The two optimisations and what each fixes: path compression flattens paths during find; union by size or rank keeps trees shallow (height at most log2 n). Together: amortised O(α(n)) per operation, effectively constant.
Where it is used: connected components, cycle detection in an undirected graph, Kruskal's minimum spanning tree, grouping problems; and what it cannot do (split a set, or answer questions on directed graphs).
Python specifics: store parent and size as plain lists for integer elements (or a dict with setdefault for arbitrary hashable keys), and write find iteratively, because a recursive find on a long chain hits the default recursion limit of 1000 and raises RecursionError.

Code / implementation expected: Yes — a DSU class in Python with find, union returning a bool, and a set count.

union-find

Try it yourself

Sketch your approach before you read the solution. That is what the interview tests.

Stuck? Get a hint.

A short nudge toward the approach. It will not give the answer away.

Solution

Target Audience: Beginners preparing for coding interviews — you should know what an array is; everything else is explained Difficulty: Medium Language: Python 3

How to read this doc: Every idea is explained in plain language first, then tagged with 📌 Interview term: so you also learn the exact word an interviewer expects. All code is Python, and every output block in the Verified section was copied from a real run of the examples on this page.

1. Why This Even Matters — A Story First

Imagine a school on the first day of term. Every student starts alone. During the day, pairs of students become friends, and friendship spreads: if Ana is friends with Ben and Ben is friends with Chloe, all three are now one friend group. At any moment a teacher may ask: "are Ana and Dev in the same group?"

You could keep a list of every group and, on every new friendship, co

The solution is hidden so you can try first

9 min read · 11 sections

Python code

Edit the code and run it here. Each printed line with an expected value becomes a test.

PythonUnion-Find with path compression and union by size

Practice

PythonCounting parent hops: naive vs compression vs union by size

Practice

PythonThree classic problems: components, redundant edge, earliest connection

Practice

Discussion

Other approaches, follow-ups and how it went in real interviews.

Sign in to join the discussion.

No comments yet. Share how you would answer it.

The solution is hidden so you can try first

Keep your momentum going.