Union Find in 5 minutes - Data Structures & Algorithms

This video covers one of the most popular data structures and algorithms topic "Union Find". This is an instruction showing how to run Union-Find on a graph, with examples and code. Union Find and Disjoint Set are not as difficult as we think! 😊
#graph #data_structures #algorithms #faang #Union-find #disjoint set #data-structures #recursion #leetcode #interview #algo #disjoint-sets #disjoint sets
Facebook: / potatocoders
Linkedin: / potato-coders

[@potatocoders2028]

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

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

[@Dev_God]

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

[@richtigmann1]

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

[@donaldcodes]

Love it man, short and clear!

[@adam23sp]

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

[@user-dc7oj3el7o]

So practical and helpful video=) Thanks

[@samruddhisaoji7195]

Loved this bite sized explanation!

[@chrismiaomiao9426]

Amazing! It's very clear. Thank you

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

[@arjunv7055]

wonderful explanation! Thanks mate!

[@manojmpatil1269]

Perfectly explained. Thanks

[@paccini1]

Wow, thanks a lot, great explanation!

[@jubiliudu]

Amazing! thank you!

[@nghiapham1632]

It so simple and straight forward. Thanks you so much

[@JamesBrodski]

Thank you so much this is great!

[@danielwang8833]

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

[@shamitfatin3516]

under-rated video.. thanks for the explanation

[@luisgualpa7019]

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

[@potatocoders2028]

I'm so glad!

[@ahmetemin7572]

Short and clear, thanks

[@nguyennguyendinh5215]

very clear! Thanks!

[@Hdhdushzhz57743]

Thank you! This was very helpful

[@nightmare_9]

Crystal clear and precise...Thanks!!

[@potatocoders2028]

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

[@jakobmusic9187]

fantastic video! thanks!!!

[@kmishy]

Best illustration... please provide more content

[@gdthegreat]

thanks a lot for explaining in few minutes.

[@alesblaze4745]

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

[@pieterjanvandecasteele135]

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

[@potatocoders2028]

You're welcome!

[@vishaldhawan9236]

+1

[@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!

[@bozecki]

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

[@MinhPham-eh6lr]

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

[@persas1683]

Thank you very much. Nice video.

[@samwilson4597]

Thank you so much man

[@mykz814]

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

[@Baal3033]

Awesome explanation, thank you!

[@potatocoders2028]

Np :) I am glad it helped

[@jashmerchant5121]

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

[@Shasol]

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

[@piotr780]

best explanation every ! :D

[@tudorradu5848]

THANK YOU!

[@civilspot5912]

Great explanation

[@SterlingVanlaere]

Excellent video, thanks!

[@potatocoders2028]

Glad it helped!

[@DeepakSankar88]

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

[@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.

[@aadityakiran_s]

You got a video on path compression?

[@jeresher6821]

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

[@potatocoders2028]

Wow, thank you for the great comment! :)

[@WebSurfingIsMyPastime]

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

[@JackSparrow-vv2uq]

Thank you

[@chrisdahms9682]

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

[@mahlahlana]

wow!

[@Rockyzach88]

Thanks Mr. Tater.

[@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.

[@waynegreen7970]

Good content!

[@potatocoders2028]

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

[@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 ✨

[@corgirun7892]

awesome

[@pamp3657]

good video

[@KoScosss]

Thanks

[@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.

[@rasheedlewis1]

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

[@algorithmdatastructures9244]

Subbed 💛

[@potatocoders2028]

Thank you ☺️

[@samuraipiyush]

beauty

[@kmishy]

algorithm was easy but you should write code and execute

[@helloyogeshpatel]

That’s how Algo is studied

[@errorless7921]

Yes important is implementation

[@Luca_040]

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

[@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

[@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 *?

[@quantum_psi]

This really didn't make sense