Okay, so now we're going to talk about the union and find operations we can do on the union side, or the disjoint. Set. This is the video where I demystify how those actually work internally. So to create our union find, the first thing we're going to do is we're going to construct a by ejection, or simply a mapping between our objects and the integers in the range zero inclusive to an inclusive, assuming we have n elements. So this step in general is actually not necessary. But as soon to allow us to create an array based unit find, which is very efficient and also very easy to work with.

So if we have some random objects, and we want to assign a mapping to them, then we can do so arbitrarily. As long as each element maps to exactly one number. So that is my random by ejection. And we want to store these mappings perhaps in the hash table, so you can do a look up on them and determine what everything is mapped to. Next, we're going to construct an array. And each index is going to have an associated object and this is possible through our mapping.

So for instance, in the last slide, a was mapped to five, so slot five, or index five is going to be a slot. So what you see in this picture is at the top is that array we just created, which contains our mapping And in the center is just a visual representation of what's going on. The value in the array for each position is currently the index, which it is at. This is because originally, every node is a root node, meaning it maps to itself. But as we perform the instructions on the left of unifying groups together, or objects together into groups, we're going to find that we're going to change the values in our array to map to other letters. And specifically, the way we're going to do it is for some index i in our array, index is parent is going to be whatever index is at position.

I So, for instance, if we want to unify C and K, we look at C and K, and we discover that C has a root node of four, and K as a root of nine. So either sees one from case parent, or case don't want to see its parent. And I chose that case parent is going to be see. So now at index nine, which is case position, I'm going to put a four because I know that C is a four. So next, F and E are going to do a similar type of thing. And I'm going to say that f is going to be s parent is going to be E. So at s position, which is one I'm going to put a zero because E is zero.

Similar thing for MJ But here's where things get a bit more interesting. So now we want to use phi and B. So if I look at a has a six in itself, but six is J, so I know that as the root node for group greens, J, and B is a single node because it's a self loop. In general, I'm going to merge smaller components into the larger ones. So now, bees are pointed j, because the green groups root node was J. So I want to merge C and D. So I find the root node of D, which is the and find the root node C, which is seeing and I'm going to merge the spark component the into the larger component, which is The orange group.

Now DS wants to be part of the orange group. Now I want to merge D and I. So similar thing happens, and I now points to C. Now, I want merge L and F. So F parent is E. So I'm going to merge L and to be into the red group. I want to merge C and A. So this is an interesting example. So I find a C's root node, which happens to be C, I find a root node which is J.

Now, component, orange has four elements, but component, green only has three. So I'm going to merge the green component into the orange component. So now j is going to point to seat So I want to unify NB. So I do. So if I go up, it's called the parent nodes until I reach a root node. A parent is J J's parent C. So I know that a belongs to the orange group.

And if I do a similar thing with B, I also discovered that B's parent is also C, which is the orange group. So I don't need to unify them. They're already unified together. So H and J, G. They currently don't have a group, so I'm going to arbitrarily merge them into a new group. So the blue group, so h, f. So if I look, HS parent is G and s parent is he the right components larger some you merge the blue group into it. And now, since g was the root node i make it point to E, which was also the root node.

Now I want to merge H and B. So H is root node is E, if we follow up the chain from H to G, and B's root node is C, because we go from B to J to C. So now since the orange component is larger than the red component, we're going to point the root of the red component to the root of the orange component. So enough points to see. Okay, and note that in this example, I'm not using a technique called path compression. This is something we're going to look at in the next video which is an optimization on the union find. To summarize, if we want to find out which component a particular element maps to, what we have to do is find the root of that component by following All the parent nodes until we reach self loop or a node whose parent is itself and that will uniquely determine which component that element belongs to.

And to unify two components together, what we do is we find the root nodes of each component. And then, if the root nodes are different, because if they're the same, then they belong to the same component already. So if they're different, make one of the root nodes point to the become the parent of the other room. So just some remarks about this union find data structure. So in general, we don't really aren't union elements. Just because this would be inefficient as we'd have to update all the children which point to that note, we don't have access to those.

But we could probably in theory, keep track of that. I just don't see any Application currently but there, there might be also remarked that the number of components in our unified is going to be equal to the number of root nodes remaining. Because each root node is responsible for a component, and also remarked that the number of root nodes never increases, that always decreases because all we do is unified components, so components only get bigger and bigger and bigger. Now, we want to talk about the complexity of the Union find. So I said in the first video that the US plan has an amortized time complexity. However, the implementation of this show you does not have no more ties to complexity.

Not yet, not without the past compression, which is something we're going to look at in the next video, which is what makes the unifying an absolute beast of a data structure. You must watch the next video But just as an example, if we need to check, if H and B belong to the same group or a different group, it's going to take five hops in the worst case, and well, potentially much more. So H, always find the root node, which is C, and then we go from B and find the root node of C. So this takes quite a few hops. So in the next video, I'm going to be covering path compression. So absolutely, make sure you watch that video. It's what makes you find so great.

And also, if you're interested in some source code for the union find, go check out my GitHub repository with all these data structures I've been covering. So guys, thank you for watching, and I'll catch you next time.