DSU with Path Compression
Find and union in near-constant time.
DSU with Path Compression is a free Coding Interview Prep lesson on CoddyKit — lesson 1 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.
What a DSU Tracks
A Disjoint Set Union keeps items grouped into non-overlapping sets, so you can ask if two things already belong together. 🤝
Sets as Trees
DSU stores each set as a tree. Every element points to a parent, and the topmost node, the root, is the unique name of the whole group.
The Parent Array
You hold all those links in one array. Start with each element as its own parent, meaning every item begins in a set by itself.
parent = list(range(n))Finding the Root
The find operation walks up parent links until an element points to itself. That self-pointing node is the root that identifies the set.
while parent[x] != x:
x = parent[x]Long Chains Hurt
Without care, sets can form long skinny chains. Then find crawls node by node and a single query can cost O(n), which is far too slow.
Enter Path Compression
Path compression fixes this: while finding the root, you re-point every visited node straight at the root, flattening the tree for next time. ⚡
Recursive Compression
The cleanest way is recursion. Find the root, then store it back into parent[x] before returning, so the link is permanently shortened.
def find(x):
if parent[x] != x:
parent[x] = find(parent[x])
return parent[x]Two Items, Same Set?
To test if two elements are connected, compare their roots. If find(a) equals find(b), they live in the same group; otherwise they are still apart.
if find(a) == find(b):
print("connected")Merging Two Sets
The union operation joins groups by pointing one root at the other. One line links two whole trees into a single set.
def union(a, b):
parent[find(a)] = find(b)Why It Is So Fast
With compression alone, operations run in roughly O(log n) amortized, and paired with ranking they hit near-constant time per query.
Where DSU Shines
DSU powers connectivity questions: friend circles, network components, and Kruskal's spanning tree all lean on fast find and union. 🌐
Quick Check
Think about what path compression actually changes.
Recap
You built a DSU: a parent array, find to get the root, and union to merge. Path compression keeps it lightning fast. Nice work! 🎉
Frequently asked questions
Is the “DSU with Path Compression” lesson free?
Yes — the full text of “DSU with Path Compression” 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 “DSU with Path Compression”?
Find and union in near-constant time. 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 1 of 4, so you can start here or from the beginning and move at your own pace.
How long does the “DSU with Path Compression” 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