Thanks :)

Welcome 😀

Nice :)

😂

Welcome :)

Thanks :)

Welcome bro

Welcome :)

I am honoured :)

Thanks

Welcome

Thanks :)

Thanks

Welcome :)

Thanks :)

Welcome

👍🏼

Welcome :)

Thanks :)

Welcome 😊

@@techdose4u sir plz keep uploading videos ✨😇

Thanks

Welcome

GOOD JOB!! PLUS: rank!=height, only in some case both can be same other wise not. rank of individual nodes can be calculated and heights as well but the tracking of height of every node becomes harder and harder everytime path compression is invoked, so, rank is preferred thus Union by Rank. Below is a GFG problem. I am just trying to give you a better understanding. Input: 5 // number of nodes and nodes are 1,2,3,4,5 4 // number of queries to perform U 1 3 //query1 = union of 1 and 3 C 1 2 // query2 = are 1 and 2 connected (do they have same parent? ): ANS = no U 1 5 //query3 = union of 1 and 5 C 3 5 // query2 = are 3 and 5 connected (do they have same parent? ): ANS = yes Output: initial parent array! 12345 initial rank array! 11111 1 2 ::: are connected? : 0 3 5 ::: are connected?: 1 final parent array! 12141 final rank array! 21111

:)

Welcome

Thanks ❤️

Thanks

Welcome :)

:)

Thanq bhai 😅

:)

Welcome 😀

It's pretty easy to apply path compression :) you just need to use 1 word.

It is not actually dp. But you can think of like that because you wanna know the result at once :)

Worst case O(N) and avg case will not be O(log N). Log N is very very less than N. Try to take larger values of N and see the difference. Log N can be true for a balanced tree structure.

Please read the proof for logN

Please reply and clear this doubt

same is the doubt i refered striver graph series, gfg article and then this video no body is changing rank after compression :( which should be done !

Can you mention the line numbers in the code for others to get clear referance. Thank you.

@@techdose4u line no. 20 and 21 in sublime text!(not in github one)

@@techdose4u Please reply! is there anything wrong in argument?

I think if we don't use those two lines, tree's height will grow faster as we are not adding the component to the parent but we are adding it to some other node!

I already told that height and rank are 2 different things :)

Please read this proof: en.wikipedia.org/wiki/Proof_of_O(log*n)_time_complexity_of_union%E2%80%93find

So wrong in complexity analysis

Thanks

Please read the proof for this :)

@@techdose4usir I saw one on wikipedia tooooo much maths haha but still thanks for nice video

@@sanjayjoshi8807 that's why I didn't explain :)

Maybe it is a bit late, and you already got the answer somewhere else, but I think this is a legit question, and should be answered here. You basically answered it yourself. Finding the correct rank is would be in O(n), because you need to check the distance of each node to the root. There are basically 3 scenarios, that can happen: 1) The compressed path was not part of the longest path: Then the rank does not change no matter what 2) The compressed path was part of the longest path, and there exists another path of that length: Then the rank also does not change 3) The compressed path was part of the longest path, and there exists no other path of that length: Then you would need to update the rank. So you have to find the newly longest path. And for that you must travel all paths, because all paths are candidates for the newest longest path. All path means all nodes, means O(n). Now the video states, that the find operation acts in O(log(n)) (Which is not exactly correct in a worst case analysis, only in an amortized analysis, but correct enough for the discussion). Going from logarithmic time to linear time is an exponential blow up, that we want to avoid wherever possible ;)

Rank is not height. Initially it is the height but after compression, height is less than rank

@@techdose4u what is rank actually? please elaborate this. I am in confusion

@@abhishekjaiswal6492 just a way to make efficient union op

You can choose anyone to become parent and increase the rank of absolute parent by 1.

He has explained this in the video itself

You are right... but let me explain you why we do not need to do this. 1. Let's change the rank Ex, set - 1, has skewed tree of 4->3->-2->1.... 1 is parent. so, rank = 3 and when we do find(4), rank actually become to 1... but when we join set -1 with set -2 having, 5->7->8 where 8 is parent and logically this has rank 2... now think, if we join set - 1 (considering rank -1) to set- 2, each element of set -1 has to compress it path separately because all are them pointing to 1.. so when you find path of 4 then 4->1->8. so, path of 3,2 only compress when you find them... 2. DO not change the rank. same example, 4->3->-2->1.... 1 is parent. so, rank = 3 and when we do find(4), rank is same.. NOw, under stand this logic, actually rank is saying, (higher the rank, more number of nodes have been compressed by it.) so, 4,3,2, -> 1 (same rank = 3) and 5,7 -> 8 (same rank = 2. ) when we join less rank with more, only 5,7 need to compress it path on next find operation. I don't know this is perfect example or not.. but I tried to explain as good as I can.

Actually I have explained the reason for your query in the video itself. Please rewatch. Also, rank for the same height may be different and rank is not guaranteed to be equal to height always. So, it will be confusing to understand if you use the name rank by height.

I have similar doubt, lets say we have two trees, 3-> 2->1->5 (rank = 3)and 6->7->8(rank=2), now we did operation find(3,2) so by path compression the first tree would become 1->5,2->5, 3->5 (rank=3, height=1) now if we take the union of the two trees. According to ranks the height of final tree would become 3 but if we made 6 as parent of 5 then we could have achieved height 2. So why are we not doing like this if our aim is just to keep the height minimum?

Yea

@@techdose4u thanks

Initially height and rank was same. But due to compression, height of tree changes but rank doesn't. That's the difference explained in the video.

@@techdose4u rank will always remain same irrespective of what graph is?

No

So as to increase the rank of the resulting tree after union

Right. I think I have uncommeted. In the previous code I forgot to comment it :)

Neither of them.

@@techdose4u Okay need to rewatch video

Sure :) I think you will get it himanshu coz I have mentioned explicitly that rank is not height of tree. It's just a different value altogether because we will do compression and so height will change but rank won't. As soon as we compress, everything changes :)

Nice :) You count each milliseconds :P

@@techdose4u no the editor shows the execution time xD

Nice :P

@@aayush5474 please provide question link or name.. on gfg, i couldn't find it..

And to be frank could you please explain little slow and more detailed as u did in the initial videos if possible.

oh

hey u into sprituality?

​@@mayankverma8520 sometime spirituality has nothing to do with gods.......but research work with physics and GAN architectures.

@@veerabhimanyusingh779 what are you even talking about? you and MAYANK SHARMA???

@@shaquille.oatmeal8301 just remain confused brother........!