Union Find in 5 minutes - Data Structures & Algorithms

[@potatocoders2028]

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

[@cartooncartel6493]

Bro you cooked

[@robirahman]

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.

[@tunguyenxuan8296]

true. if we represent the group as a tree, it will take O(n) for find function in worst case. We better to represent a group as a trie, where all children point to one root.

[@neerajvshah]

@@tunguyenxuan8296 Trie's don't change the runtime complexity, a trie is just a type of tree (keep in mind not all trees are binary trees, a trie is just an k-ary tree). As Robi mentioned it's path compression which makes union find efficient. This video is incorrect - O(logn) is never the time complexity for union find. It's either O(n) without path compression or O(a(n)) with path compression.

[@lightlysal]

​​​@@neerajvshahWhat's a(n) mean in your explanation? Is it the amount of times we "compress" a parent? I thought when people say the time complexity of union find they mean O(log N) on average over all use cases

[@sirmonke8946]

@@lightlysal a(n) is the reverse ackermann function. It grows insanely slow (slower than any log) and can basically be rounded to constant time

[@MrKlaygomes]

@@neerajvshahpartially correct, if it is only weighted without path compression it is O(log n).

[@BobTheScience]

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.

[@nomealow]

Yes, this is called path compression, by setting the parent of x and all of the ancestors of x to be the root ancestor of x. This makes it so that find(), for that particular tree in the future, will be O(1) instead of being dependent on the tree depth

[@luisgualpa7019]

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

[@potatocoders2028]

I'm so glad!

[@richtigmann1]

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

[@tenminuteamateurhour]

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.

[@Coffeycup27]

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

[@jakubucinski]

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

[@rm-stl]

I’ve seen this done but never heard it explained. It looked odd to have a side effect in a find(). Makes perfect sense now. Thanks

[@stevenhicks3321]

I also noticed this and thought it may be better to use sets if you don't care about the three structure of the disjoineted set.

[@pieterjanvandecasteele135]

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

[@potatocoders2028]

You're welcome!

[@vishaldhawan9236]

+1

[@danielwang8833]

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

[@nightmare_9]

Crystal clear and precise...Thanks!!

[@potatocoders2028]

Glad it was helpful! Also I like your profile picture :)

[@estebanzavala9533]

wow really good preparing for an upcoming interview

[@jerrygord3131]

This was really helpful, thank you!

[@nghiapham1632]

It so simple and straight forward. Thanks you so much

[@Anirozannay]

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

[@potatocoders2028]

Thank you! We hope it has helped!

[@tudorradu5848]

@@potatocoders2028 it helped me a lot, thank you man!

[@송예은-h7b]

So practical and helpful video=) Thanks

[@kmishy]

Best illustration... please provide more content

[@Shasol]

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

[@UsamaAziz-lb7ky]

Great video, worth adding path compression as well.

[@jashmerchant5121]

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

[@shamitfatin3516]

under-rated video.. thanks for the explanation

[@vinitsunita]

Awesome explaination

[@chrisdahms9682]

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

[@manojmpatil1269]

Perfectly explained. Thanks

[@donaldcodes]

Love it man, short and clear!

[@alesblaze4745]

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

[@gregoriuswillson4153]

Great content bro

[@samruddhisaoji7195]

Loved this bite sized explanation!

[@JamesBrodski]

Thank you so much this is great!

[@chrismiaomiao9426]

Amazing! It's very clear. Thank you

[@bozecki]

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

[@civilspot5912]

Great explanation

[@ahmetemin7572]

Short and clear, thanks

[@SterlingVanlaere]

Excellent video, thanks!

[@potatocoders2028]

Glad it helped!

[@piotr780]

best explanation every ! :D

[@Baal3033]

Awesome explanation, thank you!

[@potatocoders2028]

Np :) I am glad it helped

[@Hdhdushzhz57743]

Thank you! This was very helpful

[@aadityakiran_s]

You got a video on path compression?

[@Dev_God]

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

[@OtitoAmuga]

This not efficient. "Set the root of one tree to the child of another" Another what? Another node? Another number? Another graph? Lol 😅

[@OtitoAmuga]

Mediocre at best

[@Dev_God]

@@OtitoAmuga Thanks! I'll get to know more about this.

[@jeresher6821]

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

[@potatocoders2028]

Wow, thank you for the great comment! :)

[@persas1683]

Thank you very much. Nice video.

[@mykz814]

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

[@waynegreen7970]

Good content!

[@potatocoders2028]

Thank you. Let me know if there is any more content that you would like to see! 😀

[@gdthegreat]

thanks a lot for explaining in few minutes.

[@jashmerchant5121]

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

[@austecon6818]

Thanks and other implementations include rank. Does it matter?

[@arjunv7055]

wonderful explanation! Thanks mate!

[@jubiliudu]

Amazing! thank you!

[@adam23sp]

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

[@collyyang9664]

good, thank you very much

[@paccini1]

Wow, thanks a lot, great explanation!

[@samwilson4597]

Thank you so much man

[@DeepakSankar88]

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

[@chku]

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 ✨

[@WebSurfingIsMyPastime]

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

[@Rockyzach88]

Thanks Mr. Tater.

[@pamp3657]

good video

[@MinhPham-eh6lr]

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

[@tudorradu5848]

THANK YOU!

[@rasheedlewis1]

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

[@mehraan8592]

beautiful

[@algorithmdatastructures9244]

Subbed 💛

[@potatocoders2028]

Thank you ☺️

[@corgirun7892]

awesome

[@Luca_040]

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

[@kmishy]

algorithm was easy but you should write code and execute

[@helloyogeshpatel]

That’s how Algo is studied

[@errorless7921]

Yes important is implementation

[@mahlahlana]

wow!

[@KoScosss]

Thanks

[@emerald_eyes]

Didn't know I'd be learning computer science from Jaqen H'ghar

[@JackSparrow-vv2uq]

Thank you

[@samuraipiyush]

beauty

[@moshebixenshpaner5094]

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.

[@CSSFACE]

what do you mean by O(log* n) what is the *?

[@supratimdas1006]

​@@CSSFACE study

[@OtitoAmuga]

Bro speaking not exactly matching what he's saying. I guess that's why he's a potato coder.

[@quantum_psi]

This really didn't make sense

[@jakobmusic9187]

fantastic video! thanks!!!

[@nguyennguyendinh5215]

very clear! Thanks!