hey everyone welcome back to the channel I hope you guys are doing extremely well so in this video we're going to learn about the most important topic in the graph series which is the disjoint set data structure it's a very very important topic why this is commonly asked in almost all interviews and the online assessments as well so you need to master this topic and in order to master this topic you have to watch this video and all the follow-up problems that I'll be solving in the next part of this graph Series so let's understand why is this joints a data structure used so imagine I give you something like one two three four and I give you other portion like five six seven this is a single graph but it has two components first one is this second one is this now suddenly someone will come up and say hey does one and five belong to the same component or not I will determine you'll pick up one and you'll start a DFS travel one two three four and the traversal is complete you could not find five since you could not find five in the DFS traversal of one in that component you'll be like they do not belong to the same component you did a DFS traversal and that's a Brute Force how much time will the DFS traversal Take N plus e that's the complexity the DFS or the BFS takes already discussed this uh in the previous section of the graph series if you do not know DFS or BFS go back and watch it so the brute force is going to take a kind of linear time complexity so this is where something like disjoints that comes in and says hey I'm going to do the same thing in constant time you ask me does one and five belong to the same component I'm gonna tell you in constant time either a yes or a no that's the use case of this joint set data structure and one more thing it is usually used in dynamic graphs graphs which keep on changing graphs which keep on changing their configuration at every moment what do you mean by exactly changing configuration I'll explain you that in the later part so this joint set gives us two options one is finding the parent that's one of its main functionality and the other main functionality is union now this Union can be done with two methods one is rank other one is size I'll be discussing both of them but so primarily it gives you two functions find parent and Union now I did talk about dynamic graphs graph changing configurations so let's understand this now what do you mean by these things these are all edges there's an edge between five and six okay so initially what we assume is one two three four five six seven everyone is alone so initially before all these edges formation every node is single single right so you have one two what it means is I'm asking you to connect one two so that is what union does for you remember this whenever I say connect one to Union in disjoint set will do it for you we'll talk about uh Union in details but as of now uh know the higher level of Union Union will go and connect so what I'll do is I'll go and connect okay done next two and three connect one next four and five current four and five next six and seven connect six and seven so you see the graph is changing at every instant but you'll be like what's driver wait this is our graph is formed but what happens here is if I stop the formation over here and I give you a question where after this formation I suddenly ask you hey does 4 and 1 belong to the same component or not you will say no why because 4 as of now is here one as of now is here till this point they are not in the same component so the answer will be no so in any stage someone might come up and ask you because the graph is changing at every step but I can ask you a question at any step and you should be able to answer that in constant time that is what this joint set will do and I'll explain you how it does next five and six let's connect five and six next three and seven let's connect three and seven now if I ask you the same question does one and four belong two like after performing all the operation does one and four belong to the same component your answer to that will be yes they do belong to the same component understood so you saw till here the graph was something different the moment you perform the next two operations the graph was a combined one so I can ask you this particular question or any u and v belong to the same component at any particular time so this is the use case of disjoint set data structure now let's quickly check out what is find parent and what is Union exactly so in order to implement uh disjoint set data structure we can Implement Union in two ways one is the rank the other one is the size so I can follow two ways of doing it okay but initially I'll be teaching you the rank I'll be coding you up showing you how to write a clean code so that it can be reused in almost all the problems and then I'll be teaching you the size one so the video will be uh First Union by rank then Union by size okay so let's understand right so in order to implement Union by rank we will be requiring couple of arrays one is the rank array while the other one is the parent array which will serve for finding parent I'll explain you so let's quickly assign the rank and the parent arrays okay so the initial configuration is very very simple what we do is we assign a rank array with the same size of the number of nodes since the graph is one based indexing I start the array from one so everyone is assigned to zero okay so what does rank 0 mean so if you see this particular note there is no one beneath it so it means there is no one beneath it zero nodes beneath it but eventually with the optimizations that we will do the meaning will change so I'll explain you throughout the course so now we have a parent array now remember initially everyone is the parent of himself now what does parent mean parrot parent okay right above guy that is what is the definition of the parent which is stored here again over the course of this lecture the definition of parent will change as we do multiple optimizations in order to obtain a constant time complexity so this is what we currently have let's quickly start the operations so let's quickly write the pseudo code for the union of U comma V so remember the step one is very very simple the step one says find Ultimate parenthesis find Ultimate parent of u and v what is the meaning of ultimate parent I'll explain you and we can term this as uh ultimate apparently ultimate parent of u and v let's term this as pu and PV pu means ultimate parent of view PV means ultimate parent of PV Now find rank of those ultimate parents find rank of pu PV find rank of ultimate parents not u and v ultimate parents okay now connect smaller rank to larger rank smaller rank to larger rank always in case of equality you can connect anyone to anyone we will explain that as we move okay cool we have understood or I've written the pseudo code okay let's Now quickly uh check out the first operation that has been asked for us it says Union of one two so what I do is I have one so I go and look at the parent of one what is the ultimate parent you have a bunch of notes the guy at the top is known as the ultimate parent okay so for one who is the ultimate parent one itself for two two is the ultimate parent so I can see as of now the ultimate parent of one is one and the ultimate parent of two is two what is the rank of both can I say the rank of both is as of now zero if you carefully see both the ranks are zero so if they are equal rank you can actually connect any one to anyone very very important you can go ahead and connect either you can connect like one here or either you can connect to it is completely your choice so what you do is you will go ahead and take this two and say can you please connect with or I can change the color can you please collect connect with two and you'll go to that now your above parent is one now remember you connected two to one right both of them had same level both of them were equal height they took it and connected so the height increased and if the height increased the rank will also increase by one the rank will also increase by one done perfect next two three and this is where again the next thing comes who is the ultimate parent of two let's use the ultimate parent of two it's one over here and is the one the top guy it is so the ultimate parent of two is one who is the ultimate parent of three p itself what's the rank rank of uh this particular one is one rank of this particular three is three if c one is one three is zero sorry it will be zero who is the greater guy this one the three will come up and get connected the smaller guy comes up and gets connected to the larger one so three is connected to this now I'll go and erase this connected do I do anything to the ranks no you will not do anything to the ranks why because it still has a height of one because you connected a smaller to the larger so the larger is not going to increase it's not going to increase so thereby we keep the same height perfect next connect foreign 4 was the ultimate pattern of five five what's the rank 0 0 connect anyone to anyone so what I'll do is I'll go ahead and connect five to four and I'll erase this I'll increase I'll update the parent of five to four and the other thing that uh by the way I forgot to update the parent of three it will be one so but the other thing I'll do is I'll increase the rank by one because two same guy is connected height increases so done of next connect so what is the next thing connect six and seven so ultimate parent of six is six ultimate parent of seven is seven the ranks are zero so what you'll do is you will connect seven to six you'll update seventh power into six it'll update the rank of six to one this is how you can easily connect okay done so apparently I can just remove this as well so as of now this is where we stand what's the next step it says connect five and six so perfect so who is the ultimate parent of five let's see ultimate parent of 5. 5 is here so 5's parent is four who is actually the top boss who's actually the top boss that is the Ultimate Fan now I've been asked to connect six so six parent is six six is parent is six himself so I'll give a parent is six let's write the rank rank of four if you see is one rank of six if you see is one do you agree you do agree so apparently I can say that okay fine we have someone of the same ranks so either this can go and get attached here either this can go and attach it so you can do as you wish so what I'll do is I will just go ahead and take the six and make it attached to seven oh sorry to four done and now I'll omit this remember one thing you attached six to four so the parent of six will be four the parent of six will be four remember this very very well okay next what is the other thing that you will do you will have to increase the rank why because you had four or five you got six seven both of the ranks if you carefully see four and six at a rank one so since you attached same guys height will if you see the height increased so apparently you go ahead and say the rank to increase by one more so the rank will be two so this is where we stand till we have not performed the last step now if if I kind of understood everything now suddenly if someone comes up and says does let me write it uh does one and seven or do one and seven belong to same compo if I ask you this question the answer is no but how will you find out this is where something like find parent will help this is where something like fine parent will come into picture okay so since I'm saying find parent will come into picture let's understand so when I'm saying does 1 and 7 belong to the same component I look at the parent of one it's one I look at the parent of seven it is six so I'll be like okay the parents are different they are not a tweet you should not do like this just imagine you were having a ate here imagine nice I'll ask does eight and seven belong to the same component now something to notice we are not creating a graph we are creating a different data structure over here a graph is not being created okay different data structure is being created if I ask you if 8 and 7 belong to the same component ideally they should but if you will look at the parent then a would have stored five seven would have stored six both have different parents can you actually tell on the basis of parents or do you need the ultimate parent the top guy the boss need the boss you need the ultimate parent so this is why if I'm asking who's the parent of seven you say the parent of seven is four so you go seven and you see six you see six you see four uc4 uc4 oh I'm the boss that's why my parent is me that's why you say the parent ultimate parent boss is Sport and the boss for one is one so both have different ultimate parents if both have different ultimate parents you say they do not belong to the same component this is the use of fine pan now since you are creating a kind of a tree structure the tree will increase in depth with more number of edge additions the tree will increase increase increase so it will end up taking login it is theoretically proven the table uh the tree will increase and will end up taking logarithmic of n if you just apply Union by rank because in order to find the parent of 7 you have to go from seven to six from six you have to go to four and at 4 you find he is himself so you get the top boss or the ultimate parent that's going to take you a logarithmic of time but wait that's why you said it works in constant it does we apply something as path compression okay so what I do is I say okay someone did ask me to find the parent of seven so what did I do I went to six because six was his right father or the next parent and success parent was four and four says and the parent so you can write something like this okay I went from seven to six six to four so I know the four is the parent so once you have figured out Seven's parent is four and since we are just dealing with parents and that is what I require because of aim main goal is to figure out who is the ultimate parent so can I say once I've gone to seven to six to four and once I figured out the parent of seven is four can I actually say let's I don't need this link anymore uh I don't need this link anymore because I know Seven's parent is not food so can I change Seven's parent to four I can because the next time if someone again comes up and says me hey does 2 and 7 belong to the same component and you again go and call find parent you will not move like seven six four because this time 7 will directly go to four and it will find him to be the boss so he did a path compression you did a path compression you said once I will just compress you and then I know that Hey listen your parent is this guy I know this I don't need to go via sex imagine the tree to be longer imagine the tree or something like this just imagine take it as an imagination imagine the tree was something like this and someone said find a parent of five so what would uh will you ideally do it'll go to Five you'll go to four you'll go to three you'll go to two you'll go to one and at one you'll find he's the parent himself and he'll say one is the parrot you will say one is the parent but what I will do is I'll do a path compression I know one is the parent and one will be the parent of two also so I'll say two is directly on it one will be the ultimate parent of three as well so I'll say one will be the ultimate parent of four as well so I'll just remove this and say and I know five ultimate parent will be one so apparently a tree which was something like this if you do path compression on finding parent of five four three two one and you get two as the parent it returns to sorry it returns one it returns one it returns one it returns one because you went when to end went and you backtracked to get one one one so what I'll do is when this guy will return basically when this guy will return one I'll say three your ultimate parent is one why are you connected to two why are you wasting your time getting connected to two could be like yes does make sense let me connect to one before I be like yes I'm also wasting time I will be like I'm wasting time everyone goes and gets connected so this is how the graph will change now under one we will have to we will have three we will have four we will have five directly directly yes so you know this is for sure and next time when someone comes up and says find parent of food I'll be like array one direct low one because four is connected to one and one is the ultimate parent someone comes up and says find parent of five take one one is directly connected ultimate parent so this is what the path compression technique is if someone is asking me parent everyone in the path whom I encounter I'll replace their links and attach it to the direct parent but here comes a slight twist I'll attach it to the direct parent so it's fine so what we usually do is we attach it to the direct parent and that's what we call as path compression okay remember this so as of now we have something like this now what will happen the next three and seven will come so I'll be like you have to attach Three N Sub so we know three ultimate parent is one and that's very easily found because 3 is directly attached to one but when I try to found out I find out the seven I'll have to find the parent of seven which goes to 6 which goes to 4 and in order to find the parent we will end up doing a path compression we will end up doing a path compression so let's be honest let's do the path compression which will be something like this and I'll find the ultimate parent of 7 to be 4 who is connected to himself right but if you do this the tree will be something like this and the rank of four if you carefully observe is 2. but actually you have 5 6 and 7. ID the rank will also decrease but we cannot do it we cannot do it because we are not sure of it because the rank cannot be reduced in while path compression the simple reason is imagine you had something like this and someone asked you to find parent of eight so you went ahead and found parent of eight and path compressed see you reduced one section of the tree but the other section is still having a bigger length so the rank cannot be here uh cannot be reduced so that's why we call it as a rank and not height if we can reduce it we would have called it as a height but since it cannot be reduced we call it as a rank rank in the sense means this guy is bigger than this guy sorry opposite this guy is bigger than this guy that's it that's the meaning of right this guy is higher ranked than me got it so the moment you find the parent of 7 to be 4 I find the rank to be 2 which means this is the bigger guy so the smaller guy will this time come up and get attached to the sky so what will happen is this guy will come up and get attached to this one so ultimately we will have so ultimately what we will have is uh the parent of seven will be 4 and I'll attach one two four so what will happen the parent of 1 will now become 4 correct so if I just read uh draw it it's going to look something like this one attached here and two and three attached to this guy correct so will the rank change no it's still the larger guy attaching the smaller to the larger guy will not impact because the rank of one if you remember was one the rank of four was two so we are not storing the height because during path compression the height will shrink so this is how easily we can do it but after this someone comes up and says hey uh does three and uh six belong to the same component what you'll do we'll call the find parent for three and it will find you the parent to be ultimate ultimate tree one one four for himself so again a path compression will happen yes when you find the parent three will give you as four so the path compression will also happen Point Parent of three will give you four find parent of six will be directly four so both of them have same parent or ultimate parent so they belong to the C form quite easy you since you're compressing the tree since you're compressing the tree a tree will be always a very limited size in order to find parent if to do limited traversals always got it so thereby the time complexity in order to perform the union operation is bigo of 4 Alpha now this four Alpha has a huge mathematic derivation which is not required in interviews you can say four Alpha which is as good as constant because the Alpha's value is very very close to one so it is as good as a constant and in order to find parent it is also for Alpha so overall the data structure works in we go of 4 Alpha remember this okay so the question comes up whatsoever how do we do path compression you might be thinking how do you do path compression because it looks scary because if you are connected to this then you're connected to this then you're connected to this then you're connected to this how do you path comes it's very simple so price parent is for postparent is three threes parent is two two's parent is one and one's parent is one so what you can do is you can backtrack so you can write something as find parent and you can give the node U okay and what will happen is you will say If U is equal to equal to parent of U then return this U so basically what does this mean if at any moment one comes one will be equal to equal to parent of one because parent of one is himself I'll return the parent as one that's the piece because that is where you stop otherwise you will be like can you please return find parent of parent of you what does this mean imagine I give you five what will happen it will go and say parent of five what's parent of five four we'll go and say find parent of four so next time find parent of four will happen does not obey again it will say find parent of parent of four because parent of four three so it'll go on so the recursion will be something like this function of five calls function of 4 calls function of three calls function of 2 calls function of 1 at 1 the base case is executed and when it is executed it returns one so this 2 which called which you would have called here what you'll do is you'll say parent of U will be 2. so when it will return up it will return with 1. next you'll again return one you'll again return one so now three will also keep one parent of three is one next you'll all also return one so now parent of four will also be one next you'll also return one so parent of five is equal to one so everyone in term will assign one to it in if everyone assigns one to it so automatically all the links will be path compressed and pointing to one and and all these links will be destroyed perfect so I hope you have understood everything about the Union by Rank and the path compression now it's time to code it up so I'll try to create the data structure in a class so that going forward in the upcoming problems we can use that snippet of code to solve almost all the problems so we have a class of uh this joint set nothing to worry like don't don't get too worried about a class very simple it's a very simple thing what's the initial configuration initial configuration required a rank and a parent so just have it and declare everything afterwards public so all the functions can be reused outside so now go ahead and declare the Constructor what's the construction uh what is the Constructor rather so if you remember I said you initially rank will be marked with zeros parent will be marked with themselves that is what we do so we say rank dot resize of n plus 1 comma 0 1 plus 1 imagine it's a one based indexing graph we need the nth index as well if it's a zero based fine but declaring uh declaring it as one n plus one will work for both one base as well as zero based similarly we can Define parent dot resize of n plus 1 and we can keep it and then we can go ahead from 0 very very important to go till n or one based indexing [Music] this is how the Constructor will look like now what does disjoint set give you it gave you find Ultimate parent right so this will be the note and for this you have to find the ultimate parrot so we know one thing if node is equal to equal to the parent of node this is the ultimate parent for sure so you go ahead and return the node but if it is not then you call the ultimate parent and say go to its parent and then look for parent parent parent parent but this is the normal logarithmic guy we need the path compression so this is where I can say whenever it Returns the value I'll store it so that in future if someone comes up and does ask me the same question I can tell him that this is the parent so this is where the path compression comes in next what I'll do is I'll be like okay void Union by rank is what I need to implement Union by rank so I'll have node U and node V which I have to combine so ultimate parent of like it's the ultimate parent of U will be find Ultimate parent of U similarly you can say ultimate parent of V will be find Ultimate parent of V now I can say if ultimate of U is equal to Ultimate of v i can simply return what does this mean if they're belonging to the same component I don't need right but if they are not belonging to the same component I go ahead the first thing I do is I check if the guy U is smaller than the guy V right so if V is the greater guy the smaller goes and gets attached to the greater guy so the smaller will now say okay I'll go and have the parent as v no change in rank because if a smaller guy gets attached to the uh larger one there will be no increase or that still stays the larger right next else if rank of ultimate of V if this is the Lesser guy rank of ultimate of EU if this is the Lesser guy then I say the opposite I say parent of rank sorry parent of ultimate of V goes and gets attached to you of it done but what if they are same if they're same I'll sell attach V to U you can do the other way as well YouTube is okay as well and rank off ultimate of you will increase because that is where I am attaching it to be attached to you so the larger one will grow in size so this is what I will do once I've done this I can say the union is done this is how our data structure will look like how can we use this snippet of code so I'll just hard code it to show you how can we use it it's pretty simple so you can be like disjoints at DS what is the number of nodes so in our case it was one so I can have it as disjoint set of seven so it will call this Constructor and have the initial configuration ready for us next will be I'll call it Union by Rank and the first thing was 1 comma 2 if you remember in our example right so we'll have it one comma two so I'll quickly add all these uh things so next was 2 comma three if you remember let's add 2 comma 3 next was uh four comma five so let's add four comma five next to a six comma seven let's add six comma seven next was five comma six let's add five comma six and the next to us if you remember well enough from the example the next was 3 comma seven so I'll be adding up this but before adding up three comma seven let's quickly check if 3 and 7 belong to the same component or not same or not okay so what I'll do is I'll call the find Ultimate parent for three and I will say okay do you have equal to equal to seven like d belong to the same like do you have the same boss same ultimate parent if you do then same as the same all else I will say not same I'll go and say not same right perfect done and after connecting them I will again check for the same so as of now let's uh have a quick run and see if it is giving us correct answer so I'll just go and compile this so on compiling it is saying no they do not belong to the same and if I go ahead and move it to the next guy it will actually say that they belong to the C first time it says uh not same then on combining it says same so this is how you can always use the data structure if you want to have two disjoint set data structure you can go as DS1 you can have two different objects of this class and you can have two different graphs in two different data structures so this code can always be reused in almost all the problems because it covers up zero based indexing graphs as well as one based indexing graphs now a question might be coming to your head but striver we did not understand why connect smaller to larger like what's the idea of connecting smaller to larger the first idea is I don't want to increase the height for an example if I have one two I have a three four five just for an example empty so if I connect the larger to the smaller see what will happen one two three four five six so basically the height increases and if the height increases like we will do path compression for sure but if the height increases what happens is now in order to find the parent of six we'll have to travel six five four three and then one so we're taking a longer distance so imagine someone would have said for four so yeah actually taking a longer distance and if you do the opposite way which is saying let's connect like you keep three four five six and let's connect one and two so if you see for six the distance taken is shorter even for five the distance taken is shorter even for four the distance taken is shorter but for these the distance will increase like for two the distance will be now more because over here towards just traveling once and getting the ultimate but over here it has to travel to one then to three but the number of nodes over here are lesser so the travel time to all the notes computed will be less so over here the number of nodes are larger the travel time all the nodes will be larger so to give you a Clear Vision imagine we had something like this imagine okay five six seven eight okay and we had one two now if you attach this guy to this guy what will happen is in order to find the parent of seven seven will go to six to four three to one similarly for eight six four three one similarly four five four three one right so this will take longer time this will take longer time this will take longer time more nodes will take longer time whereas if you attach this to this they will take the similar time that they were taking and only two notes will take slightly longer time which is okay this is the reason we attach smaller to larger first to keep it shrinked second is to make sure that the time taken and finding of the parents is as minimal as possible so you must be thinking striver if that's the case why are we using something like Union by rank because after path compression it doesn't even gives us the height because the height is distorted after path compression can we use something as size which keeps a track of what is the size of the component I think we can I think we can so that's what we will be doing okay so so what I will try to teach you now is Union by size we know find parent we know path compression but instead of rank we'll be using the Union by size so over here the same thing will happen we will have a size array of the same size so let's quickly declare the size array of seven size so the initial configuration will be very straightforward we will have a size and everyone will be of size 1 why because everyone is itself a component when we start off with so everyone is going to be having a size of one and we know one more thing that the parent will be themselves so this is what we take now to start off with very simple we say one comma two we say one has a size of one two also has a size of one so both are similar size so it doesn't matter whom you attach so I go ahead and attach two over here the moment you attach two to one size of one will increase to two because it took a size of one got attached to it so the size increased by it okay next is two to three very important point to realize now one has a size of two and remember the parent of two is this time one so one has the size of two and three has a size of one so this is the smaller goes and gets attached to one so goes and gets attached to one the size will again increase by one why because 3 was the size of one perfect done and three will be having a parent of one so this is also done next is four and five so what I'll do is I'll just omit this and I'll just assign 5 to the sky and 5 is parent will be 4 and 4 will increase the size of two next will be six and seven so I'll assign and I'll increase the size over here perfect done next is why you understand so next is so 6 comma 7 is done next is 5 comma six so that is five five is here with four and six is here so both of them if you see out of size 2 size 2 theme size so what you'll do is probably you can take six and get attached to this done the sixes parent will be four six is parent will be four and since you're attaching a size 2 to 4 the size will increase by two not by one so basically this is keeping a track of how big is this this is keeping a track of how big is this this is also done next will be 3 comma seven so for three it's one which is a size of three three size component for seven if you see seven has this which is nothing but a four size component this is a smaller one so this will go and attached so when you try to find the ultimate parent of seven definitely path compression will happen here's the first step next for three the parent is one so this goes and attach Force size will be increased by three the four will be having a size of seven so you can keep a track of size and this actually is much more uh like induced intuitive you can say instead of the rank I don't find the rank to be that much intuitive but I feel I find uh this Union by size to be much more intuitive than Union by rank because it kind of makes sense where you are storing the size because rank is distorted so what I'll do is I'll try to copy the same thing so I'll try to copy the same thing and I'll create in the same function I'll just create Union by size because everything else will stay same Union by size and now what I'll do is I will say okay fine I know one thing for sure now I'm doing a comparison on the size so size of this if lesser than size of this then I'll be like okay I will take the ulp you attach to the ultimate parent of V done next the size of the ultimate parent of V because it is getting attached to will be increased by ultimate parent interview else now will there be an equal case if there is an equal case you still attach it right so we can just write an else instead of writing else if greater and then else because an equal doesn't matter whom you attach to right so I'll just take this and I'll just change this to V I'll change this to U I'll change this to U and I'll change the story that's it so this is how the Union by size will work and what I'll do is now remember if you're implementing a data structure either use by rank or either use by size don't use both of them together don't use both of them together because we have to declare a size this time so let's quickly declare a size and over here what I can say is size dot resize n plus 1 and I can go ahead and say size of I is initially one that's the initial configuration and I've written the Union by size then I have everything as Union by size let's quickly do a compile and see if it is working fine foreign okay not same not same strange so over here there was a v you have to make it U again now we can compile and see if it is running fine yes not same and C so this is how you can easily create a snippet of code which has Union by rank as well as Union by size what is the time complexity which one is better both are of the same time complexity because we are still attaching them still creating trees still having the path compression so both of them will take we go of 4 Alpha which is as good as a constant will like will the interviewer ask you about for Alpha no because it's it has a very very huge mathematic derivation you can probably Google and read about it for interviews if you tell them that poor Alpha is near about constant that's more than okay because what they look for is do you know the logic do you understand this in depth or not that please focus on that part as much as you can so yeah before ending up this video I was checking out our Channel stats nearly 50 of the people who watch our videos do not subscribe to us so please do consider subscribing to us it's a very very honest request and yes if you understood it in by rank even by size path compression the code snippet I think you should hit that like button and if you haven't uh checked out our DP series and the SDC the links will be in the description please make sure you check them out and here with this I'll be wrapping up this video let's put in some other video tell them I take care [Music]