Union by Rank and Components
Keep trees flat and count groups.
Union by Rank and Components is a free Coding Interview Prep lesson on CoddyKit — lesson 2 of 4. You can read the complete lesson below for free — then practise it hands-on in the browser with a built-in code editor and a 24/7 AI tutor. It is part of the Coding Interview Prep learning path, one of 4 lessons in the course, and your progress syncs across the web and the CoddyKit app.
Union Can Be Lazy
Plain union just hangs one root under another. Done carelessly, it can build a tall, slow tree, so we need a smarter way to merge roots.
The Big Idea
Union by rank always attaches the shorter tree under the taller one. Keeping trees shallow makes every later find faster. 📏
What Rank Means
Rank is an estimate of a tree's height. Each element starts at rank 0, since a single node has no depth below it.
rank = [0] * nAttach Shorter to Taller
Compare the two roots' ranks. The root with the smaller rank becomes the child, so the combined tree stays as flat as possible.
if rank[ra] < rank[rb]:
parent[ra] = rbTies Bump the Rank
When both roots have equal rank, pick either as the new root and increase its rank by one, since the tree just grew one level taller.
else:
parent[rb] = ra
if rank[ra] == rank[rb]:
rank[ra] += 1Union by Size Variant
A popular alternative is union by size: attach the smaller set under the larger one. It is just as effective and gives you group sizes for free.
Counting Components
Start a count at n, since every element is its own group. Each successful union joins two groups into one, so you decrement it.
components = nSkip No-Op Unions
If two elements already share a root, the union does nothing. Only decrease the count when their roots actually differ.
if find(a) != find(b):
union(a, b)
components -= 1Rank Plus Compression
Combine union by rank with path compression and DSU runs in inverse-Ackermann time, which is effectively constant for any real input. ⚡
Group Sizes On Demand
With union by size you can answer how big any group is instantly: just read the size stored at that element's root.
group = size[find(x)]Where This Helps
Component counting answers classic questions like number of friend circles or connected regions after a stream of union calls. 🌐
Quick Check
Reason about how the component counter changes.
Recap
You learned union by rank to keep trees flat and how to track component counts and group sizes. DSU is now blazing fast! 🎉
Frequently asked questions
Is the “Union by Rank and Components” lesson free?
Yes — the full text of “Union by Rank and Components” is free to read here on the web, and the Coding Interview Prep course includes 4 lessons in total. To practise it interactively (a built-in code editor and a 24/7 AI tutor) and unlock the rest of the Coding Interview Prep course, upgrade to CoddyKit PRO.
What will I learn in “Union by Rank and Components”?
Keep trees flat and count groups. You practise Coding Interview Prep with hands-on code you run directly in the browser, and a 24/7 AI tutor answers your questions as you work through the lesson.
Do I need any experience to start Coding Interview Prep?
No prior experience is required. Coding Interview Prep on CoddyKit is structured for beginners through advanced learners; this is — lesson 2 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “Union by Rank and Components” lesson take?
Most CoddyKit lessons take about 5–10 minutes. Each one is bite-sized and interactive, so you make steady progress and pick up exactly where you left off across the web and the app.
Can I write and run code in this Coding Interview Prep lesson?
Yes. Every Coding Interview Prep lesson includes a built-in code editor, so you write and run real code right in your browser and get instant AI feedback — no local setup required.
All lessons in this course
- DSU with Path Compression
- Union by Rank and Components
- Kruskal's Minimum Spanning Tree
- Prim's MST with a Heap