Union Find in 5 minutes - Data Structures & Algorithms
ฝัง
- เผยแพร่เมื่อ 2 ธ.ค. 2020
- 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 - วิทยาศาสตร์และเทคโนโลยี
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.
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.
@@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.
@@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
@@lightlysal a(n) is the reverse ackermann function. It grows insanely slow (slower than any log) and can basically be rounded to constant time
@@neerajvshahpartially correct, if it is only weighted without path compression it is O(log n).
Thanks for sharing! It's very clearly and efficiently explained!
This was actually insanely helpful in understanding the concept. Thanks!
Love it man, short and clear!
Amazing video, very easy to follow, thank you! 🎉
Really clear and concise explanation. This video helped a ton.
So practical and helpful video=) Thanks
Loved this bite sized explanation!
Amazing! It's very clear. Thank you
wonderful explanation! Thanks mate!
It so simple and straight forward. Thanks you so much
under-rated video.. thanks for the explanation
Perfectly explained. 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)).
Wow, thanks a lot, great explanation!
Best illustration... please provide more content
This video has saved me many hours of my life. Thank you for this.
I'm so glad!
wow , i must say that this was really easy and nice video , really nice explanation
Crystal clear and precise...Thanks!!
Glad it was helpful! Also I like your profile picture :)
bro... come back ur vids r so good 😭
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.
Amazing! thank you!
I was always stuck with the implementation of UF, now I finally got it, thanks!
You're welcome!
+1
Thanks bro, now I finally understand it for tommorow exam ;p
You explained it so well! Thank you for your video!
Thank you! We hope it has helped!
@@potatocoders2028 it helped me a lot, thank you man!
Solved my hours long quandary in 5 minutes. Thank you!
thanks a lot for explaining in few minutes.
fantastic video! thanks!!!
Thank you so much this is great!
Awesome explanation, thank you!
Np :) I am glad it helped
Short and clear, thanks
Thanks for the concise and easy-to-understand explanation!
best explanation every ! :D
very clear! Thanks!
Thank you! This was very helpful
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).
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
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.
Excellent video, thanks!
Glad it helped!
Thank you very much. Nice video.
Thank you so much man
Great explanation
Best video I've found on UF. Thank you!
Wow, thank you for the great comment! :)
This video was great! definitely not something that's very clearly covered in alot of other sources
THANK YOU!
How do you select the representative? I struggle to understand that part of it.
Bro this topic is confusing AF, but at least this vid makes it somewhat understandable
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.
Great explanation. Was able to recall what I had learnt a while back. 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 ✨
Good content!
Thank you. Let me know if there is any more content that you would like to see! 😀
You got a video on path compression?
good video
Thank you
Thanks Mr. Tater.
wow!
The Big-Theta runtime for find() would be Θ(n).
awesome
Subbed 💛
Thank you ☺️
Thanks
beauty
Wer sieht das auch für's HAW Studium?
algorithm was easy but you should write code and execute
That’s how Algo is studied
Yes important is implementation
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
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.
what do you mean by O(log* n) what is the *?
This really didn't make sense