you are literally the best teacher anyone can get,I feared DSA so much since my basics were weak thanks a lot your videos are super addictive,I have actually started liking DSA,in college used to hate it :)
Sir, your explanations skills are exceptional, i bought an unacademy course but comparatively your explanations are far better than that paid course, really there is no sense of paying any DSA course online if your videos are available.
Hi striver I am final year student I watch your content from my second year turst me I follow lot of content and also purchase course on DSA and i didn't clear my concept when i saw your Amazing DP Playlist and graph ,recursion it just 🔥 I just advice my junior of college to watch your content your content was literally bro amazing I just want to tell that in u way solved the various question/ problem it just clear all the topic in that way of minute u r amazing please never stop doing this it's really hlep alot people with such a content and aslo I cracked amazon recently Thanks to you to provide such a amazing content Thank you so much🔥🔥🔥🔥🔥
There is one more way of doing it. By manipulating the DSU snippet. Initializing parent array with -1 and making parent[node]=node when we iterate the operators array. The space complexity is little lesser as we don't always need to initialize the visit and parent array of size (n*m). Instead we are initializing it with size of operators.size(). But the way striver Bhai has written and explained is clean. Here is my code.. class DisjointSet{
This approach feels more natural and intuitive. Since each query effectively adds one cell land mass to the graph, the total land mass after Q queries would be atmost Q (considering the possibility of duplicate queries). The adjacency of two land cells on the matrix then corresponds to edges connecting those cells (and their components in the DS). The interal state of DS also more accurately captures the true number of components at each step, as opposed to the approach presented in the video where internal state of DS treats singleton water cells as components as well.
Understood........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻. Before I checked the complete video, I just watched the video till 6:00 and was able to derive the complete solution by myself........😀😀😀😀😀😀...........This increases confidence.....😎😎😎😎😎😎. Thanks a lot Striver Brother.........You are doing a very great job......God Will surely bless you.........😇😇😇😇😇😇
initially, initialize the visited array by 0, and make a count variable to store the number of island groups. 1) pickup querie that is(row,column) in the given operations. 2) check whether Querie is visited or not visited:: => If it is not visited mark it as visited and make the count increase by 1, then go for its neighbors if a neighbor is found to have 1 then connect the previous neighbor to the new neighbor by dsu, and decreases the count by 1 as connections form and add to our ArrayList. => If it is visited then store the same count in the list.initially, initialize the visited array by 0, and make a count variable to store the number of island groups. 1) pickup querie that is(row,column) in the given operations. 2) check whether Querie is visited or not visited:: => If it is not visited mark it as visited and make the count increase by 1, then go for its neighbors if a neighbor is found to have 1 then connect the previous neighbor to the new neighbor by dsu, and decreases the count by 1 as connections form and add to our ArrayList. => If it is visited then store the same count in the list.
Thank you so much for the effort. I request to please add a lecture on Minimize Malware Spread or Minimize Malware Spread 2 problem also. These are kind of unique patterns of Union Find.
The reason for using Union instead of decrementing island count on every directional match : If the upper direction already merged two islands into one, the left direction won't contribute further because the union(u, v) function will check the updated ultimate parents of the two cells. If they now share the same parent, it returns False, preventing any redundant merging and maintaining the correct island count.
If the path compression is not updated according to the latest unions, it is not safe to compare parents before compressing right? It might not always return latest ultimate parent. What is the idea behind comparing without ensuring compression? Am I missing something?
Can someone help me with this why here memset work int vis[n][m]; memset(vis,0, sizeof vis); where as int vis[n][m] = {0}; doesn't work for test case 23 aren't both the code serving same purpose?
can we solve this question just like the most stones removed with same row or column approach if anyone knows or have an idea about it pls do reply thanks in advance
alternate solution using pairs: ig better to read! // User function Template for C++ class Solution { public: class DisjointSet{ public: vector rank; vector parent; DisjointSet(int n , int m ){ rank = vector(n,vector(m,0)); parent = vector(n,vector(m,{0,0})); for(int i =0 ; i
Why can't we use parent array for finding parent instead of findparent function. When we use unionByrank or size ,we are assigning ultimate parents to nodes,then parent array should give us ultimate parent ?
I also had the same doubt but no ! consider this ds where 1 3 5 are connected now there's another ds 6 7 so 7's parent is 6 right? but when we connect this ds with the prior ds 7's parent is still not changed the only change in the parent is of 6 and 7's parent still remains 6 . So consider the possibility that there are tons of nodes. It would fail. I hope this clears up. Please correct me if I'm wrong.
Can any one help me to figure out what mistake I have done over here int fun1(int u,vector&parent){ if(u==parent[u]){ return u; } return parent[u]=fun1(parent[u],parent); } void union1(int u,int v,vector&rank,vector&parent){ int parentU=fun1(u,parent); int parentV=fun1(v,parent); if(parentU==parentV) { return; } else if(rank[parentU]==rank[parentV]){ parent[parentU]=parentV; rank[parentV]++; } else if(rank[parentU]>rank[parentV]){ parent[parentV]=parentU; } else { parent[parentU]=parentV; } } vector numOfIslands(int n, int m, vector &operators) { // code here int i,j; vector parent(n*m,0); vector rank(n*m,0); vector vis(n,vector(m,0)); vector ans; for(i=1;i
@@thaman701, nhi main abhi seekh hi rha hun... Striver ke videos se kafi kuch seekhne ko mila... Isi ke playlist se DP bhi seekhi... Kunal Kushwaha ke videos se Tree and baki data structures seekhe... Sabhi ko local IDE pe code karke usme proper comments daal daal ke rakha hun... Abhi 2 maheene hue hain sab seekhte hue... Revise krne ka time nhi Mila abhi kyuki abhi system design bhi seekhna hai... Waise mujhe kam time lagega kyuki Mai 8 sal ka experienced hun...
![[#2024MAMA] G-DRAGON - 무제(Untitled, 2014)+POWER+HOME SWEET HOME+뱅뱅뱅+FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/Ox29z5Nf1Uk/mqdefault.jpg)
![[#2024MAMA] BIGBANG (빅뱅) - 뱅뱅뱅 (BANG BANG BANG) + FANTASTIC BABY | Mnet 241123 방송](http://i.ytimg.com/vi/EQsYfiPR9uM/mqdefault.jpg)
Let's continue the habit of commenting “understood” if you got the entire video. Please give it a like too,.
Do follow me on Instagram: striver_79
understood
very hard working bhaiyaaa😮💨🥵
you are literally the best teacher anyone can get,I feared DSA so much since my basics were weak thanks a lot your videos are super addictive,I have actually started liking DSA,in college used to hate it :)
understood
The Kind of Excitement you show in your face while explaining.
Sir, your explanations skills are exceptional, i bought an unacademy course but comparatively your explanations are far better than that paid course, really there is no sense of paying any DSA course online if your videos are available.
Hi striver
I am final year student I watch your content from my second year
turst me I follow lot of content and also purchase course on DSA and i didn't clear my concept
when i saw your Amazing DP Playlist and graph ,recursion it just 🔥
I just advice my junior of college to watch your content
your content was literally bro amazing
I just want to tell that in u way solved the various question/ problem it just clear all the topic in that way of minute
u r amazing please never stop doing this it's really hlep alot people with such a content
and aslo I cracked amazon recently
Thanks to you to provide such a amazing content
Thank you so much🔥🔥🔥🔥🔥
hey can you share the questions that were asked you during the interview rounds and in OA
Amazon wow program...
Hi maam , aap kis college se hai . kya aap mujhe kuch guide kr skti hai currently i am in second year student .
This question was asked to one of my friend in thoughtspot round 1 interview for SDE Intern role.
The explanation was perfect and also this problem marks the beginning of dsu in matrices !!
Understood. Thanks for laying emphasis on Code Quality
Understood !!!
This series is Gem Mine 🙌🙌 thank you for your hard work
his explanation drew an image in my brain, I was able to code that in 1 go.
There is one more way of doing it. By manipulating the DSU snippet. Initializing parent array with -1 and making parent[node]=node when we iterate the operators array.
The space complexity is little lesser as we don't always need to initialize the visit and parent array of size (n*m). Instead we are initializing it with size of operators.size().
But the way striver Bhai has written and explained is clean. Here is my code..
class DisjointSet{
public:
vectorrank,parent,size;
DisjointSet(int n){
rank.resize(n+1,0);
for(int i=0;i
Thanx vishal for sharing your approach
This approach feels more natural and intuitive. Since each query effectively adds one cell land mass to the graph, the total land mass after Q queries would be atmost Q (considering the possibility of duplicate queries). The adjacency of two land cells on the matrix then corresponds to edges connecting those cells (and their components in the DS). The interal state of DS also more accurately captures the true number of components at each step, as opposed to the approach presented in the video where internal state of DS treats singleton water cells as components as well.
Understood........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻.
Before I checked the complete video, I just watched the video till 6:00 and was able to derive the complete solution by myself........😀😀😀😀😀😀...........This increases confidence.....😎😎😎😎😎😎.
Thanks a lot Striver Brother.........You are doing a very great job......God Will surely bless you.........😇😇😇😇😇😇
Thank you for your relentless hardwork even on Diwali ❤️😊❤️😊
Happy Diwali !
Thank You So Much for this wonderful video.......................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
Understood! Super excellent explanation as always, thank you very much!!
initially, initialize the visited array by 0, and make a count variable to store the number of island groups.
1) pickup querie that is(row,column) in the given operations.
2) check whether Querie is visited or not visited::
=> If it is not visited mark it as visited and make the count increase by 1, then go for its neighbors
if a neighbor is found to have 1 then connect the previous neighbor to the new neighbor by dsu,
and decreases the count by 1 as connections form and add to our ArrayList.
=> If it is visited then store the same count in the list.initially, initialize the visited array by 0, and make a count variable to store the number of island groups.
1) pickup querie that is(row,column) in the given operations.
2) check whether Querie is visited or not visited::
=> If it is not visited mark it as visited and make the count increase by 1, then go for its neighbors
if a neighbor is found to have 1 then connect the previous neighbor to the new neighbor by dsu,
and decreases the count by 1 as connections form and add to our ArrayList.
=> If it is visited then store the same count in the list.
Thank you so much for the effort. I request to please add a lecture on Minimize Malware Spread or Minimize Malware Spread 2 problem also. These are kind of unique patterns of Union Find.
The reason for using Union instead of decrementing island count on every directional match :
If the upper direction already merged two islands into one, the left direction won't contribute further because the union(u, v) function will check the updated ultimate parents of the two cells. If they now share the same parent, it returns False, preventing any redundant merging and maintaining the correct island count.
understood ......very close to finish this series....thanku striver
excellent explanation!! application of disjoint set data structure explained nicely..Thanks
U r the best teacher 🙏
Understood!!
I wish I started watching your videos earlier when I was learning tree and stuff man
Amazing boss....going to complete the series soon❤
Thank you sir 😊
i coded myself sir. such a nice feeling for me.
@takeUforward please share the time complexities as you did in the previous videos.
Time complexity = O(k*4*4*alpha) where k = operators.size();
N*M also for creating the grid ig
Question was very logical ... congrats for 0.6 Million subscribers striver !!
I was just stuck on "most-stones-removed-with-same-row-or-column" Ah I wish I had say your video earlier... 2d UnionFind is tough to undertstand!
Understood.... Amazing Explanation🙌🙌
Understood. Thank YOU, STRIVER. Immense love and respect dude💋💋
Understood. Hats off to you
understood great approach striver.
Disjoint set: Dynamic Graph and Connections and Connections
Understood bhaiya 🙏❤️
We can also use arr[pos/rows][pos%rows]
Hare Krishna..! understood
Understood, Great explanations
understanding approach is so easy but when it comes to coding it on my own I get stuck for hours
Can I consider only the coordiantes given in the input as nodes and count the no of connected components at each step ??
What an explanation man !👏👏
thank you sir for a lot of effort for us
Thanks Striver!
understood,awesome explanation
I always eagerly wait for your videos.
If someone say you can't do anything in life ,show them 4:25 ,move on and work hard.
You are a GEM!! Thank you very much
"understood" 🙂
East or West , Striver is the best😍,BST Series❤🔥 Graph❤🔥
If the path compression is not updated according to the latest unions, it is not safe to compare parents before compressing right? It might not always return latest ultimate parent. What is the idea behind comparing without ensuring compression? Am I missing something?
understood sir
Awesome explanation🔥🔥🔥
OP Explanation 🔥
Amazing as always! Thanks a ton!!!
Understood thanks a lot 👍
Understood as always 😃
Thank you 🙏
this was a tough one
Too good
Understood
Superb
Understood!
Thanks🙌
Can someone help me with this
why here memset work
int vis[n][m];
memset(vis,0, sizeof vis);
where as
int vis[n][m] = {0};
doesn't work for test case 23 aren't both the code serving same purpose?
Understood 🔥🔥
understood 💖💖💖💖💖
Understood.
thanks boss
understood.
Understood❤
helpful
understooddddd
understood🤩
Nice
Understood!!
Understood✌️
time complexity?
understoodd
understood!!!
Nokia Algorithm - "Connecting People(Island) 😶"
can we solve this question just like the most stones removed with same row or column approach if anyone knows or have an idea about it pls do reply thanks in advance
understood!
Anyone who asks me how to start dsa i tell them watch striver😂
understood🔥🔥🔥
understood💯
understood sir 🩷
Understood:)
Understood
understood
Striver OP
great
Link for this problem on GFG?
🎉🎉🎉🎉🎉🎉
Loved the explaination !!
How many videos will be there in this graph playlist
around 57 i think
alternate solution using pairs: ig better to read!
// User function Template for C++
class Solution {
public:
class DisjointSet{
public:
vector rank;
vector parent;
DisjointSet(int n , int m ){
rank = vector(n,vector(m,0));
parent = vector(n,vector(m,{0,0}));
for(int i =0 ; i
US
Why can't we use parent array for finding parent instead of findparent function.
When we use unionByrank or size ,we are assigning ultimate parents to nodes,then parent array should give us ultimate parent ?
I also had the same doubt but no ! consider this ds where 1 3 5 are connected now there's another ds 6 7 so 7's parent is 6 right? but when we connect this ds with the prior ds 7's parent is still not changed the only change in the parent is of 6 and 7's parent still remains 6 . So consider the possibility that there are tons of nodes. It would fail. I hope this clears up. Please correct me if I'm wrong.
unionbyrank is not working in this question. if anyone know the reason please reply
Union by rank is just an optimization to the disjoint set algorithm. You must be missing something. Can you post your code down here?
bro code is working absolutly fine i think u made some mistake in union by rank function. drop your code maybe we can help u.
US :)) !!!!!!
Can any one help me to figure out what mistake I have done over here
int fun1(int u,vector&parent){
if(u==parent[u]){
return u;
}
return parent[u]=fun1(parent[u],parent);
}
void union1(int u,int v,vector&rank,vector&parent){
int parentU=fun1(u,parent);
int parentV=fun1(v,parent);
if(parentU==parentV)
{
return;
}
else if(rank[parentU]==rank[parentV]){
parent[parentU]=parentV;
rank[parentV]++;
}
else if(rank[parentU]>rank[parentV]){
parent[parentV]=parentU;
}
else
{
parent[parentU]=parentV;
}
}
vector numOfIslands(int n, int m, vector &operators) {
// code here
int i,j;
vector parent(n*m,0);
vector rank(n*m,0);
vector vis(n,vector(m,0));
vector ans;
for(i=1;i
When he drew with the red pen on the grid for the last two queries, what was drawn will make you laugh. 😆 😆
Comment understood if you really did. 🤪🤪
Ling ban gya tha.😂
Bhai ek baat bata to is qs m hamne row*m + col kia h pr humne numbering to di hi ni h matrix ko to kaise pta lagega konsa cell h krke
@@thaman701 , aapko query me sabhi nodes ke coordinates diye hote hain... Unhi coordinates se aapko cell number nikalna hota hai
@@arvindjaiswal8013 bhai aap graphs ke algorithm ko revise krte ho kya or krte ho to kaise krte ho kitne kitne din m
@@thaman701, nhi main abhi seekh hi rha hun... Striver ke videos se kafi kuch seekhne ko mila... Isi ke playlist se DP bhi seekhi... Kunal Kushwaha ke videos se Tree and baki data structures seekhe... Sabhi ko local IDE pe code karke usme proper comments daal daal ke rakha hun... Abhi 2 maheene hue hain sab seekhte hue... Revise krne ka time nhi Mila abhi kyuki abhi system design bhi seekhna hai... Waise mujhe kam time lagega kyuki Mai 8 sal ka experienced hun...