Thanks man, just by listening to you and listening to you and seeing the illustration it kind of nailed the point to me, that union-find is pretty much just a generalization of grouping. Not necessarily "grouping" as some specific algorithm, but any problem that you come across which can be solved by grouping elements together like Kruskal's MST
It pains me to see good videos like this are hidden in the algorithm while shitty videos with no efforts have so many views. Keep up the good work william.
Maybe I'm missing something but at 3:44 we are grouping the elements and shouldn't there be a pattern to who becomes who's parent ex. the lower ID becomes the parent or the first element that we pass to the function is the parent? Because first two examples are (C,K) = (4,9) = 4 is parent (lower id ), second example (F, E) = (0,1) = 0 is parent ( lower id ), and then in the third one (A, J) = (5, 6) = 6 is parent? I know this is not the point of the video but shouldn't it follow the same logic if there's any? Later on it makes sense that we are merging the smaller component into the bigger one to flatten the tree. Great video overall didn't mean to be a party pooper :P
yeah, you are correct, william is not following any strict pattern here .. when doing it with code you would probably always take either the smaller or bigger id in those cases (merging two nodes pointing to themselves) .. but the good point of william not following a strict pattern here is that it shows that it does not matter which id you take so maybe it is even intentional :)
At 5:44 he said that because the orange component has more elements than the green component, how would the program know that when we're just performing Union(C,A), we would have to iterate through both subsets?
🎯 Key points for quick navigation: 00:01 *🔑 Explains the union and find operations in a union-find data structure.* 00:17 *📝 Creates a bijective mapping between objects and integers to construct an array-based union-find.* 01:05 *🗃️ Stores the mappings in a hash table for efficient lookup.* 01:34 *📐 Initially, each node in the array points to itself as a root node.* 02:30 *🔗 To unify objects, the smaller component's root node is set as the parent of the larger component's root node.* 04:34 *🧰 Explains the process of merging smaller components into larger ones during unification.* 06:24 *🌳 If two objects belong to the same component, no unification is needed.* 07:42 *🔍 To find the component an element belongs to, follow the parent nodes until reaching the root node.* 08:41 *🚩 The number of components equals the number of remaining root nodes and never increases.* 09:48 *⚡ Path compression, covered in the next video, improves the time complexity of union-find operations.* Made with HARPA AI
Great video, but I didn't understand the remarks :/ More precisely the statements: "we would have to update all the children of a node" and "the number of components is equal to the number of roots remaining"
Thank for the nice video and concise understandable explanation. I am still wondering why we merge it as child of the root, instead child of the node as per the unify instructions
you want to unify to the root to create the smallest depth of steps from root to leaf. same concept as when you unify two different sized groups, you unify the smaller group to the larger. path compression is a technique, that William isn't using here, that will actually reduce the depth of all groups to 2. the root and the child.
Hey. What would happen in 5:22 if we had to union Node A with Node K? Would we attach J to C or J to K? As far as i understood we check which Union has more elements, and then attach the root node of the Union with less Elements to the Node we want to union it with.
we also have to keep track of how big the subtrees are right? the array structure we have is only keeping track of vertices? unless otherwise for every iteration we count how many elements have that same root node value which would be O(n)? But we can make it O(1)?
Good day! In the remarks session, @10:15 => it says that in the current implementation, there is 5 hops to find out whether roots of two components are same or not. However, in the array-based implementation, every value of indexes point right to the root node. So, isnt it always 1 hop for each? Maybe I'm missing something. Sry for this
> every value of indexes point right to the root node example from the video does not use path compression (and you can verify that there are 5 hoops by looking on array - 7:40)
would it be also valid if I use hashmaps and hashsets instead? map: { a: {} b: {} .... } merge(a, b) { combined = new Set(map.[a], map.[b]) map[a] = combined map[b] = combined } find(a) { return map[a] }
from 5:27 could we merge the orange component to the green component? to be more precise, Node C points to J. Here J become parent of C can we do that ? If not, please tell why ?
what if there are three nodes in group orange and in group green and we try union operation of union (orange, green) .... do we arbitrarily choose the group for the root node ?
blazzy95 The choice of the successor root node is arbitrary. Generally I merge the smaller group into the larger one but this does not affect functionality
Hey William... Thanks for making and sharing such nice videos on DS and Algorithm. Do you have slack channel or Discord Server where we can connect with you and discuss on these topics directly ?
I didn't quite understand the concept after I watched this 3 times, so watched ua-cam.com/video/ayW5B2W9hfo/v-deo.html and then came back to this video and totally loved the explanation. Thanks much for uploading.
Well "bro" what are you doing here?.... this is supposed to help you with studying... first priority wasnt for you to giggle like a little girl behind your laptop screen....... Nonetheless i hope you find topic matter more accomodating to your needs (TIP: Keeping up with the kardashians, moonshiners etc. are prime sources of entertainment for your ilk)
I found myself losing track of his train of thoughts or mid sentence sometimes, playing this at 1.5 speed really helped me understand it better!
this is literally saving my life and WAY easier to understand than the class I'm taking lol. thank you!!
Do you have education loan to repay?
Seriously, youtube educators save our lives.
good video, 1.25 speed makes it perfect.
More like 2.0 :D
@@uzeyirveli yess
@@user-rf4vc7mt4d man you are dope please keep commenting on videos
love your username lol@@user-rf4vc7mt4d
Man you are so underrated, you create amazing videos with concise explaination.
Path compression is what makes Union Find an absolute *BEAST* of a Data Structure xD
Thanks man, just by listening to you and listening to you and seeing the illustration it kind of nailed the point to me, that union-find is pretty much just a generalization of grouping. Not necessarily "grouping" as some specific algorithm, but any problem that you come across which can be solved by grouping elements together like Kruskal's MST
It pains me to see good videos like this are hidden in the algorithm while shitty videos with no efforts have so many views. Keep up the good work william.
Maybe I'm missing something but at 3:44 we are grouping the elements and shouldn't there be a pattern to who becomes who's parent ex. the lower ID becomes the parent or the first element that we pass to the function is the parent? Because first two examples are (C,K) = (4,9) = 4 is parent (lower id ), second example (F, E) = (0,1) = 0 is parent ( lower id ), and then in the third one (A, J) = (5, 6) = 6 is parent? I know this is not the point of the video but shouldn't it follow the same logic if there's any? Later on it makes sense that we are merging the smaller component into the bigger one to flatten the tree. Great video overall didn't mean to be a party pooper :P
same problem for me the same logic shoould be used throughout in my opinion
yeah, you are correct, william is not following any strict pattern here .. when doing it with code you would probably always take either the smaller or bigger id in those cases (merging two nodes pointing to themselves) .. but the good point of william not following a strict pattern here is that it shows that it does not matter which id you take so maybe it is even intentional :)
@@timgoppelsroeder121 I agree with both of you.
Good video! Helped understand everything
And I watched in 1.0x 😂 i dont know why people find it hard to understand
Classes are hell; this is much easier, thank you.
Not quite sure why K is child of C, but F is child E. According to first approach - E should be a child of F
Very descriptive. Thank you!
Very nice concept of implementation of kruskal using union-find
At 5:44 he said that because the orange component has more elements than the green component, how would the program know that when we're just performing Union(C,A), we would have to iterate through both subsets?
great explanation
thank you so much🥰🥰
i dont understand why you switched the definition of parent-son mid execution in the example with the letters
all your videos are really helpful. thank you so much.
🎯 Key points for quick navigation:
00:01 *🔑 Explains the union and find operations in a union-find data structure.*
00:17 *📝 Creates a bijective mapping between objects and integers to construct an array-based union-find.*
01:05 *🗃️ Stores the mappings in a hash table for efficient lookup.*
01:34 *📐 Initially, each node in the array points to itself as a root node.*
02:30 *🔗 To unify objects, the smaller component's root node is set as the parent of the larger component's root node.*
04:34 *🧰 Explains the process of merging smaller components into larger ones during unification.*
06:24 *🌳 If two objects belong to the same component, no unification is needed.*
07:42 *🔍 To find the component an element belongs to, follow the parent nodes until reaching the root node.*
08:41 *🚩 The number of components equals the number of remaining root nodes and never increases.*
09:48 *⚡ Path compression, covered in the next video, improves the time complexity of union-find operations.*
Made with HARPA AI
Thanks for making this video. It was very helpful!
Great video, but I didn't understand the remarks :/
More precisely the statements:
"we would have to update all the children of a node" and "the number of components is equal to the number of roots remaining"
these videos are really phenomenal I appreciate it!
Thank for the nice video and concise understandable explanation.
I am still wondering why we merge it as child of the root, instead child of the node as per the unify instructions
you want to unify to the root to create the smallest depth of steps from root to leaf. same concept as when you unify two different sized groups, you unify the smaller group to the larger.
path compression is a technique, that William isn't using here, that will actually reduce the depth of all groups to 2. the root and the child.
im confused where those instructions came from. I think you made those up right? What would be an applicable problem to replace these instructions?
I love your videos a lot. Thanks
Beautiful!
Awesome channel! So easy to understand!
Hey. What would happen in 5:22 if we had to union Node A with Node K? Would we attach J to C or J to K? As far as i understood we check which Union has more elements, and then attach the root node of the Union with less Elements to the Node we want to union it with.
Hey, you went to my University! Awesome work!
we also have to keep track of how big the subtrees are right? the array structure we have is only keeping track of vertices? unless otherwise for every iteration we count how many elements have that same root node value which would be O(n)? But we can make it O(1)?
Good day!
In the remarks session, @10:15 => it says that in the current implementation, there is 5 hops to find out whether roots of two components are same or not.
However, in the array-based implementation, every value of indexes point right to the root node. So, isnt it always 1 hop for each?
Maybe I'm missing something. Sry for this
> every value of indexes point right to the root node
example from the video does not use path compression (and you can verify that there are 5 hoops by looking on array - 7:40)
Great video, thank you so much!
would it be also valid if I use hashmaps and hashsets instead?
map: {
a: {}
b: {}
....
}
merge(a, b) {
combined = new Set(map.[a], map.[b])
map[a] = combined
map[b] = combined
}
find(a) {
return map[a]
}
In the case of two components having same amount of elements and being asked to merge which way is the arrow going to point ? Thanks,
you can arbitrarily choose either one and merge it in as the child of the other tree/component.
great videos man !
does every node track the size of its tail?
This question might be really dumb but how do I do the mapping (object to number)? Thanks for the help and for the awesome video!
array
Just use a hashmap
from 5:27 could we merge the orange component to the green component?
to be more precise, Node C points to J. Here J become parent of C
can we do that ? If not, please tell why ?
@Patrick Watts number of hops ? I don't get it :/
This is just a weighted union find right?
Your description has self-loop to the same video.
Shoulda used union find lol
Thanks
Great video!! Thank you:)
what if there are three nodes in group orange and in group green and we try union operation of union (orange, green) .... do we arbitrarily choose the group for the root node ?
blazzy95 The choice of the successor root node is arbitrary. Generally I merge the smaller group into the larger one but this does not affect functionality
Hey William... Thanks for making and sharing such nice videos on DS and Algorithm. Do you have slack channel or Discord Server where we can connect with you and discuss on these topics directly ?
To people like me, who didn't read the description- watch his first video first: ua-cam.com/video/0jNmHPfA_yE/v-deo.html
Epic Video :)
is it ok if you are not being consistent?
ChavoTV yes, union is commutative. You should however map the smaller to the larger component due to the run time of the find operation.
in min 3.55, I think E should = 1
My first thought was that E should be 1 too. Then i watched video twice, he randomly defined parent in each union :)
x1.5
code samples would be more helpful than just diagrams
I didn't quite understand the concept after I watched this 3 times, so watched ua-cam.com/video/ayW5B2W9hfo/v-deo.html and then came back to this video and totally loved the explanation. Thanks much for uploading.
I'm mystified now
bro, can you literally make it ANYMORE boring? I doubt it... -_-
wow ruuude. it's literally an informational video and the material is really well explained. i don't think it's boring
Well "bro" what are you doing here?.... this is supposed to help you with studying... first priority wasnt for you to giggle like a little girl behind your laptop screen....... Nonetheless i hope you find topic matter more accomodating to your needs (TIP: Keeping up with the kardashians, moonshiners etc. are prime sources of entertainment for your ilk)
Thanks