I don't think anyone will dare to make a detailed video on this Qn. I salute you . Respect from me and my hostel mates who just watched this masterpiece
Bro, just one more thing, can we expect some bootcamp or a roadmap course from March as you said you are busy in February, which will cover good amount of DSA questions and System Design concepts for interviews.
u are literally the best explainer i have seen in my 2 years of college journey , can u make a series on oops for plaement purpose . Their are many resources available but they dont explain the way you do, even a one shot video would be enough
Thanks a lot Yash. Sure i will cover OOPS soon. Meanwhile you can try my OOPS crash course material in my Github repo : github.com/MAZHARMIK/OOP_Crash_Course_Cpp
Nice video: 2 points of improvement 1)DSU me rank update ni ho rhi hai which will increase the TC from O(1) to O(Log E) 2)Searching for count can be done in O(N) without sorting for (int &u : nodes) mp2[obj.find_parent(u)]++; for(auto &i:mp2){ ans+=i.second*(i.second-1)/2; }
Use map instead of unordered_map for storing val_to_nodes as map stores in increasing order by default. We want to iterate from smaller values to higher values. All test cases won't pass with unordered_map.
the main idea behind this is we are starting from a small value and adding in the set and when we are finding that some node is active or not. if some node is not active then it means it has some bigger value then we are not going to consider that
I tried to understand the TC from Leetcode : For T operations, the amortized time complexity of the union-find algorithm (using path compression with union by rank) is O(alpha(T))O(alpha(T)). Here, α(T)α(T) is the inverse Ackermann function that grows so slowly, that it doesn't exceed 44 for all reasonable TT (approximately T
You explanation was top notch, with you explanation I coded it myself, but at last when I saw you code I thought you did it in a tough way, because while counting the number of nodes with same parent we don't need to store the actual nodes, hence I think my code is a bit short and little easier to understand, especially the last part. Although you did a good job, because without you explanation I would not have been able to code this. Thanks Brother 🙌 My Code: class Solution { public: vector parent, rank; void init(int n){ parent.resize(n, 0); rank.resize(n, 0); for(int i=0; i
Hey, thanks for the detailed explanation. How do you approach if you couldn't solve this question even after 1/2 hrs? Do you look at the solution or hints or change thinking process? How much time should one invest for such questions ideally?
Hi Tuhin. Thank you for your appreciation. Actually I don’t waste much time in any Qn if I am stuck. We shouldn’t be giving more than an hour or 1-1/2 hours maximum if the Qn is hard. Then feel free to go around different approaches from different people and ensure that you understand them (that is important)
How about this solution As I am having list of edges I will make the adjecent lis out of it then using that I will find all the possible path from every node as starting node using dfs, but it will end finding double paths like if there is a path 1-5 so it will also find 5-1 so I will divide my answer by 2 and add all the number of edges which will give me my answer Will this work?
sir we can use brute force of this question like this which is understandable easily to everyone 123 / 134 testcases passed class Solution { public: int dfs(int currnode,int dest,unordered_map &adj,vector &visited,vector &vals,int value){
visited[currnode]=true; if(currnode==dest){ return true; } for(auto v : adj[currnode]){
Again visit channel for revise this important question this question is very helpful for increasing my DSU Knowledge and MiK bhayia has God level teching style :🤩
I dont understand at last why map was changed to unordered map. Because map itself will gives us sorted order by key right then how unordered map will qork why map doesnt work. Please somebody answer
Actually for DSU, the intuition is already explained in Graph Concepts playlist. I didn’t cover that here. Will try to take care from further videos. Thank you for your feedback ❤️❤️🙏🙏
Hello, can someone tell me, when I try to compute the number of duplicates in this way it gives me the wrong answer, I tried to figure but I can't seem to find the appropriate explanation? long count = 1; for(int j = 0; j < parentsHolder.size()-1; j++){ if(parentsHolder.get(j) == parentsHolder.get(j+1)){ count++; }else{ // formula result += (count * (count - 1))/2; count = 1; } } long ans = (count * (count-1))/2; result += ans;
bro best explaination ever 🔥🔥🔥, this ques is impossible to understand without you
Thanks a lot Abhimanyu 💝
I don't think anyone will dare to make a detailed video on this Qn.
I salute you . Respect from me and my hostel mates who just watched this masterpiece
Kitta pyara samjhae ho bhai...i can understand the hardwork you put to make these videos❤🥺
Thanku sir i wait for you vedio i complete both vedio of disjoint set.
❤️❤️❤️
Great Explanation & Just Loved it yarrr! Your channel soon be going to boom bro! keep it up :)
one of the toughest , U explained so good , That this explanation will remain as the top rated in YT.
♥️♥️🙏🙏
Waiting for this video
Thank you sir
This is the only best solution available on UA-cam for this video
4 videos in a single day, claps for your effort👏
Seriously, no one explained like this in any other video. you are unbelievable
Thanks bro for working hard for us that too on a Sunday
Bro, just one more thing, can we expect some bootcamp or a roadmap course from March as you said you are busy in February, which will cover good amount of DSA questions and System Design concepts for interviews.
Will plan soon Ankit. Thank you so much ❤
Thank you sir, i was waiting for your video ❤
u are literally the best explainer i have seen in my 2 years of college journey , can u make a series on oops for plaement purpose . Their are many resources available but they dont explain the way you do, even a one shot video would be enough
Thanks a lot Yash.
Sure i will cover OOPS soon.
Meanwhile you can try my OOPS crash course material in my Github repo : github.com/MAZHARMIK/OOP_Crash_Course_Cpp
@@codestorywithMIK thanks alot
Question really mein kaafi tough tha 🥲
Awesome yr.. I was searching whole day this was the best explanation for this question!!
Thanks for the great explanations as always!
Nice video:
2 points of improvement
1)DSU me rank update ni ho rhi hai which will increase the TC from O(1) to O(Log E)
2)Searching for count can be done in O(N) without sorting
for (int &u : nodes)
mp2[obj.find_parent(u)]++;
for(auto &i:mp2){
ans+=i.second*(i.second-1)/2;
}
Thank You....Great explanation of problem and concepts.
This is PERFECTION
thank you sir for great explaination .
wonderful explaination😁
My Code on Github : github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Disjoint%20Set/Number%20of%20Good%20Paths.cpp
Use map instead of unordered_map for storing val_to_nodes as map stores in increasing order by default. We want to iterate from smaller values to higher values. All test cases won't pass with unordered_map.
the main idea behind this is we are starting from a small value and adding in the set and when we are finding that some node is active or not. if some node is not active then it means it has some bigger value then we are not going to consider that
Masterpiece 🔥
nice explanation as always you can use unordered_map for storing the count of the parents for each node and you dont even need to sort .
Indeed Anand. You are right.
Thanks a lot
Nice Explanation, but can u pls explain its time and space complexity also??
I tried to understand the TC from Leetcode :
For T operations, the amortized time complexity of the union-find algorithm (using path compression with union by rank) is O(alpha(T))O(alpha(T)). Here, α(T)α(T) is the inverse Ackermann function that grows so slowly, that it doesn't exceed 44 for all reasonable TT (approximately T
Space is O(n)
You explanation was top notch, with you explanation I coded it myself, but at last when I saw you code I thought you did it in a tough way, because while counting the number of nodes with same parent we don't need to store the actual nodes, hence I think my code is a bit short and little easier to understand, especially the last part. Although you did a good job, because without you explanation I would not have been able to code this. Thanks Brother 🙌
My Code:
class Solution {
public:
vector parent, rank;
void init(int n){
parent.resize(n, 0);
rank.resize(n, 0);
for(int i=0; i
Wow. Thank you so much for sharing this 😇😇❤️❤️
such a fine explanation. thanks a lot
i think if using map for finding the finding the count may be little bit easy🙂. Anyway nice solution
Hey, thanks for the detailed explanation. How do you approach if you couldn't solve this question even after 1/2 hrs? Do you look at the solution or hints or change thinking process? How much time should one invest for such questions ideally?
Hi Tuhin. Thank you for your appreciation.
Actually I don’t waste much time in any Qn if I am stuck. We shouldn’t be giving more than an hour or 1-1/2 hours maximum if the Qn is hard.
Then feel free to go around different approaches from different people and ensure that you understand them (that is important)
you are amazing
Means a lot to me ❤️🙏😇
please start a series on segment tree
Noted 😇🙏
How about this solution
As I am having list of edges I will make the adjecent lis out of it then using that I will find all the possible path from every node as starting node using dfs,
but it will end finding double paths like if there is a path 1-5 so it will also find 5-1 so I will divide my answer by 2 and add all the number of edges which will give me my answer
Will this work?
sir we can use brute force of this question like this which is understandable easily to everyone
123 / 134 testcases passed
class Solution {
public:
int dfs(int currnode,int dest,unordered_map &adj,vector &visited,vector &vals,int value){
visited[currnode]=true;
if(currnode==dest){
return true;
}
for(auto v : adj[currnode]){
if(!visited[v] && vals[v]
Again visit channel for revise this important question this question is very helpful for increasing my DSU Knowledge and MiK bhayia has God level teching style :🤩
Means a lot 😇❤️🙏
class Solution {
public:
vectorparent;
vectorrank;
int find(int x){
if(x==parent[x]){
return x;
}
return parent[x]=find(parent[x]);
}
void Union(int x,int y){
int x_par=find(x);
int y_par=find(y);
if(x_par==y_par)return;
if(rank[x_par]>rank[y_par]){
parent[y_par]=x_par;
}else if(rank[x_par]
mind = blown;
in union function you didn't increase the size .
Best explanation
I dont understand at last why map was changed to unordered map. Because map itself will gives us sorted order by key right then how unordered map will qork why map doesnt work. Please somebody answer
map works because we wanted sorted order. unordered_map won't work in this case. you got confused which was used in place of what.
There is no intuition only story. but yeah good explanation.
Actually for DSU, the intuition is already explained in Graph Concepts playlist. I didn’t cover that here.
Will try to take care from further videos.
Thank you for your feedback ❤️❤️🙏🙏
Can you share the code please
github.com/MAZHARMIK/Interview_DS_Algo/blob/master/Graph/Disjoint%20Set/Number%20of%20Good%20Paths.cpp
@@codestorywithMIK error
Try again. Link updated
@@codestorywithMIK thank you
ok brother , DSU padh leta hu pehle.
Hello, can someone tell me, when I try to compute the number of duplicates in this way it gives me the wrong answer, I tried to figure but I can't seem to find the appropriate explanation?
long count = 1;
for(int j = 0; j < parentsHolder.size()-1; j++){
if(parentsHolder.get(j) == parentsHolder.get(j+1)){
count++;
}else{
// formula
result += (count * (count - 1))/2;
count = 1;
}
}
long ans = (count * (count-1))/2;
result += ans;
ye pehli baari me krlia tha kya aapne bhau
It took my many trials too
This is a nightmare for me
your lc username bro? btw great explanation
I found him : Mazhar_MIK
Mazhar_MIK 🙂