Union Find in 5 minutes - Data Structures & Algorithms 

Comment down any questions below! Please give it a like and subscribe to support our channel. Cheers, Potato Coders 🙂

You forgot to mention you have to union the shorter tree into the longer tree! Otherwise the trees in a set of n elements can be up to n elements long (just a straight chain, instead of branching) and you don't get log(n) complexity.

This video has saved me many hours of my life. Thank you for this.

This was actually insanely helpful in understanding the concept. Thanks!

To optimize it, the find function should set the parent of it's parent to find(x). (This will probably help a lot) function find(x): if Parent[x] != x: parent[x] = find(parent[x]) return parent[x] If I'm wrong please tell me.

I was always stuck with the implementation of UF, now I finally got it, thanks!

Awesome video, thank you! Question though; isn't the find operation O(n) time? I'm reading around that it isn't until you use 'Union By Rank' that it becomes O(log(n)).

Crystal clear and precise...Thanks!!

Really clear and concise explanation. This video helped a ton.

You explained it so well! Thank you for your video!

There is a little technicality, that when you do find(x), you want to do path compression, by connecting each vertex on the corresponding branch (the branch where x is) to the root. This results in subsequent find operations being cheaper (and you only double your cost one time).

It so simple and straight forward. Thanks you so much

Solved my hours long quandary in 5 minutes. Thank you!

So practical and helpful video=) Thanks

Bro this topic is confusing AF, but at least this vid makes it somewhat understandable

Thanks for sharing! It's very clearly and efficiently explained!

Correction, this does not run in O(logn), but in O(n). To get O(logn) optimization, you need to use union by rank or by size.

Thank you so much this is great!

bro... come back ur vids r so good 😭

Great video, worth adding path compression as well.

Best video I've found on UF. Thank you!

Thanks bro, now I finally understand it for tommorow exam ;p

Python code: # WITH Path Compression def find(self, parent, x): # finds root or representative of disjoint-set/union if parent[x] != x: parent[x] = self.find(parent, parent[x]) # path compression step return parent[x] def union(self, parent, x, y): root_x = self.find(parent, x) root_y = self.find(parent, y) parent[root_x] = root_y # WITHOUT Path Compression def find(self, parent, x): # finds root or representative of disjoint-set/union if parent[x] != x: return self.find(parent, parent[x]) return parent[x] def union(self, parent, x, y): root_x = self.find(parent, x) root_y = self.find(parent, y) parent[root_x] = root_y

Awesome explanation, thank you!

Best illustration... please provide more content

thanks a lot for explaining in few minutes.

Perfectly explained. Thanks

Love it man, short and clear!

good, thank you very much

Short and clear, thanks

Excellent video, thanks!

Amazing! It's very clear. Thank you

Amazing! thank you!

Thank you! This was very helpful

Amazing video, very easy to follow, thank you! 🎉

Loved this bite sized explanation!

Thank you very much. Nice video.

under-rated video.. thanks for the explanation

wonderful explanation! Thanks mate!

wow , i must say that this was really easy and nice video , really nice explanation

Great explanation

best explanation every ! :D

Thank you so much man

Good content!

Great explanation. Was able to recall what I had learnt a while back. Thank you!

THANK YOU!

This video is so gud but looks like the channel ain't active anymkre 🥺💔 I really loved the explanation n quality so thankuu n hope u r doing well ✨

Wow, thanks a lot, great explanation!

This video was great! definitely not something that's very clearly covered in alot of other sources

Thanks for the concise and easy-to-understand explanation!

How do you select the representative? I struggle to understand that part of it.

algorithm was easy but you should write code and execute

Thanks Mr. Tater.

Thank you

You got a video on path compression?

The Big-Theta runtime for find() would be Θ(n).

Thanks

awesome

good video

wow!

Subbed 💛

beauty

Wer sieht das auch für's HAW Studium?

There are two issues here: 1. When performing union, you set parent of the smaller set to the representative of the larger set. 2. When finding a path, you compress the path on your way back, improving O(logn) ops to O(log* n) in average.

This really didn't make sense

very clear! Thanks!

fantastic video! thanks!!!