G-51. Number of Islands - II - Online Queries - DSU
ฝัง
- เผยแพร่เมื่อ 20 ต.ค. 2024
- GfG-Problem Link: bit.ly/3w9REfj
C++/Java/Codes and Notes Link: takeuforward.o...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.o...
Check out our Website for curated resources:
Our Second Channel: / @striver_79
In case you are thinking to buy courses, please check below:
Code "takeuforward" for 15% off at GFG: practice.geeks...
Code "takeuforward" for 20% off on sys-design: get.interviewr...?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/inv...
Take 750 rs free Amazon Stock from me: indmoney.oneli...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v...
Linkedin/Instagram/Telegram: linktr.ee/take...
---------------------------------------------------------------------------------------------------------------------------
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
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...
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.
The Kind of Excitement you show in your face while explaining.
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
This question was asked to one of my friend in thoughtspot round 1 interview for SDE Intern role.
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.........😇😇😇😇😇😇
his explanation drew an image in my brain, I was able to code that in 1 go.
Thank you for your relentless hardwork even on Diwali ❤️😊❤️😊
Happy Diwali !
Understood! Super excellent explanation as always, thank you very much!!
understood ......very close to finish this series....thanku striver
Understood!!
I wish I started watching your videos earlier when I was learning tree and stuff man
Thank You So Much for this wonderful video.......................🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
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.
excellent explanation!! application of disjoint set data structure explained nicely..Thanks
Question was very logical ... congrats for 0.6 Million subscribers striver !!
Amazing boss....going to complete the series soon❤
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. Thank YOU, STRIVER. Immense love and respect dude💋💋
understanding approach is so easy but when it comes to coding it on my own I get stuck for hours
U r the best teacher 🙏
@takeUforward please share the time complexities as you did in the previous videos.
Understood.... Amazing Explanation🙌🙌
Can I consider only the coordiantes given in the input as nodes and count the no of connected components at each step ??
i coded myself sir. such a nice feeling for me.
Time complexity = O(k*4*4*alpha) where k = operators.size();
N*M also for creating the grid ig
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!
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.
understood great approach striver.
Understood. Hats off to you
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?
What an explanation man !👏👏
understood
We can also use arr[pos/rows][pos%rows]
Understood, Great explanations
Thank you sir 😊
I always eagerly wait for your videos.
time complexity?
Understood bhaiya 🙏❤️
Thanks Striver!
thank you sir for a lot of effort for us
understood,awesome explanation
You are a GEM!! Thank you very much
Hare Krishna..! understood
"understood" 🙂
Amazing as always! Thanks a ton!!!
Awesome explanation🔥🔥🔥
understood sir
East or West , Striver is the best😍,BST Series❤🔥 Graph❤🔥
OP Explanation 🔥
understood.
Understood thanks a lot 👍
Understood!
this was a tough one
Superb
Understood
Understood as always 😃
Thank you 🙏
If someone say you can't do anything in life ,show them 4:25 ,move on and work hard.
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.
Too good
Understood
Understood👍
Understood ❤
understood 💖💖💖💖💖
thanks boss
Thanks🙌
understoodd
understooddddd
Understood 🔥🔥
understood!
helpful
understood!!!!
understood🤩
Nice
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!!
Link for this problem on GFG?
understood💯
Loved the explaination !!
Understood:)
understood🔥🔥🔥
great
understood sir 🩷
How many videos will be there in this graph playlist
around 57 i think
US
Striver OP
🎉🎉🎉🎉🎉🎉
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.
Nokia Algorithm - "Connecting People(Island) 😶"
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.
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 :)) !!!!!!
........................
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...
I tried solving this ques by a different approach . I tried to use the previous No. Of Islands problem which we did . I stored the value returned from that function after each iteration , I was not able to get the correct ans. Can anyone help??
Here is my code :
class Solution {
private :
void bfs(int row , int col, vector &vis ,vector &grid ){
vis[row][col]=1;
queue q;
q.push({row,col});
int m= grid[0].size();
int n=grid.size();
while(!q.empty()){
int row=q.front().first;
int col=q.front().second;
q.pop();
for(int delrow=-1;delrow