Union Find - Union and Find Operations

Подписаться 173 тыс.

Просмотров 246 тыс.

50% 1

Learn about the Disjoint Set (Union Find) union and find operations.
Related Videos:
Union find intro: • Union Find Introduction
Union find kruskal's algorithm: • Union Find Kruskal's A...
Union find union and find: • Union Find - Union and...
Union find path compression: • Union Find Path Compre...
Union find code: • Union Find Code
Data Structures Source Code:
github.com/williamfiset/algor...
====================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix ===================================
Practicing for interviews? I have used, and recommend `Cracking the Coding Interview` which got me a job at Google. Link on Amazon: amzn.to/3cvMof5
A lot of the content on this channel is inspired by the book `Competitive Programming` by Steven Halim which I frequently use as a resource and reference. Link on Amazon: amzn.to/3wC2nix

Опубликовано:

13 июл 2024

Ссылка:

Скачать:

Готовим ссылку...

Добавить в:

Мой плейлист

Посмотреть позже

Комментарии : 74

@terrordoger7837 2 года назад

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!

@gabrielahernandez4236 4 года назад

this is literally saving my life and WAY easier to understand than the class I'm taking lol. thank you!!

@adhishmalviya2408 3 года назад

Do you have education loan to repay?

@turuus5215 Год назад

Seriously, youtube educators save our lives.

@scriptkiddie6151 3 года назад

Man you are so underrated, you create amazing videos with concise explaination.

@bharathateja2797 5 лет назад

all your videos are really helpful. thank you so much.

@spaceburgers 6 лет назад

these videos are really phenomenal I appreciate it!

@marilynmosala8018 7 лет назад

Awesome channel! So easy to understand!

@lfhao7969 5 лет назад

good video, 1.25 speed makes it perfect.

@uzeyirveli 4 года назад

More like 2.0 :D

@user-rf4vc7mt4d 4 года назад

@@uzeyirveli yess

@tombrady7390 3 года назад

@@user-rf4vc7mt4d man you are dope please keep commenting on videos

@victoriaye3441 3 года назад

love your username lol@@user-rf4vc7mt4d

@DillonHuff 3 года назад

Thanks for making this video. It was very helpful!

@akshatbhutra7278 4 года назад

Very nice concept of implementation of kruskal using union-find

@ale-hl8pg Год назад

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

@kartikxramesh 4 года назад

Path compression is what makes Union Find an absolute *BEAST* of a Data Structure xD

@krood_ 2 года назад

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.

@usagiliu2104 6 лет назад

Great video!! Thank you:)

@duo2375 Месяц назад

Very descriptive. Thank you!

@greaterthanKTWS 6 лет назад

Hey, you went to my University! Awesome work!

@huseyinbarin1653 Год назад

I love your videos a lot. Thanks

@lidiatjr 2 года назад

Great video, thank you so much!

@ahmad-ali14 Год назад

Classes are hell; this is much easier, thank you.

@sanskarshrivastava5193 2 года назад

great videos man !

@sallaklamhayyen9876 Месяц назад

great explanation thank you so much🥰🥰

@vijethkashyap151 Месяц назад

Beautiful!

@irvinge4641 5 лет назад

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

@ikaros9727 4 года назад

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.

@irvinge4641 5 лет назад

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] }

@Lordvibrane 4 года назад

Epic Video :)

@advandizdarevic4987 4 года назад

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

@timgoppelsroeder121 4 года назад

same problem for me the same logic shoould be used throughout in my opinion

@SaruulShafiq 2 года назад

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

@wjrasmussen666 2 года назад

@@timgoppelsroeder121 I agree with both of you.

@subee128 3 месяца назад

Thanks

@Dan-tg3gs 3 года назад

im confused where those instructions came from. I think you made those up right? What would be an applicable problem to replace these instructions?

@JinggaBlitz 2 года назад

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

@ChrisCox-wv7oo 2 года назад

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.

@blazzy95 6 лет назад

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 ?

@WilliamFiset-videos 6 лет назад

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

@rhusselcombo7696 Месяц назад

🎯 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

@only4music725 3 года назад

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,

@khailai5204 3 года назад

you can arbitrarily choose either one and merge it in as the child of the other tree/component.

@shahriarmim4696 5 лет назад

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 ?

@shahriarmim4696 5 лет назад

@Patrick Watts number of hops ? I don't get it :/

@undefinedrahulraj 3 года назад

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 ?

@zuowang5481 3 года назад

does every node track the size of its tail?

@ouroboros7388 2 года назад

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!

@alkhiljohn7640 Год назад

array

@gradientO 6 месяцев назад

Just use a hashmap

@terrordoger7837 2 года назад

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?

@user-jx8uz6tb6k 4 года назад

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

@krzysztof9287 3 года назад

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

@sebastianrollino741 3 года назад

This is just a weighted union find right?

@vasudevgawde4767 4 года назад

Your description has self-loop to the same video.

@knobtwista 4 года назад

Shoulda used union find lol

@JanacMeena 3 года назад

To people like me, who didn't read the description- watch his first video first: ru-vid.com/video/%D0%B2%D0%B8%D0%B4%D0%B5%D0%BE-0jNmHPfA_yE.html

@chavotv8752 6 лет назад

is it ok if you are not being consistent?

@josh100CH 4 года назад

ChavoTV yes, union is commutative. You should however map the smaller to the larger component due to the run time of the find operation.

@chavotv8752 6 лет назад

in min 3.55, I think E should = 1

@myeverymusic 5 лет назад

My first thought was that E should be 1 too. Then i watched video twice, he randomly defined parent in each union :)

@MykhailoKovalykUA 2 месяца назад

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

@know1374 4 года назад

I'm mystified now

@pedrobraga4944 Год назад

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"

@EranM Месяц назад

x1.5

@mizutofu 4 года назад

code samples would be more helpful than just diagrams

@trava4156 4 года назад

bro, can you literally make it ANYMORE boring? I doubt it... -_-

@gabrielahernandez4236 4 года назад

wow ruuude. it's literally an informational video and the material is really well explained. i don't think it's boring

@timgoppelsroeder121 4 года назад

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)