@@SatyamEdits suru mei difficult lgega ....but questions solve krte jao....nhi solve ho to solutions dekho..editorials dekho....U will improve in few months .....CPalgorithms website pe various algorithms read kr sakte ho
Brute force is giving wrong answer when Test case [1,0],[0,1] According to @striver answer must be (n - no. of components) i.e 2-1=1 but in leetcode it gives answer=0 for this test case
This is a hard problem , Even knowing that one stone will be left behind in a connected component requires good observation , for example ✅ ✅ ✅✅✅✅✅ ✅ ✅ ✅ Need to smartly canceling out stones to get to left 1.
@@iamnoob7593 The observation is that remove the stone which is connected to least number of stones first. Keep on doing this until you get only 1 stone remaining in the component.
We actually don’t need a Hashmap/set. We can simply write another method/function in disjoint set class which gives valid components count using the logic - traverse through the parent array and whenever we get parent[i]==i, we check if size[i]>1. If yes, we simply increase validComponents count and return it after the iteration. In a nutshell, all nodes with invalid components will have parent as itself but won’t have size greater than 1
@@spandanrastogi7144 In that case the size itself will become 2 and satisfy above condition. You can take example by adding one more column in between 2 and 3 of Striver's diagram. Also this is getting accepted in GFG.
@@bhavuks6554 Instead of counting the number of components, why can't we do "answer += (ds.size[i]-1) like he showed in the video. This is not working and I am not able to understand why it it not working
@@AdityaKumar-be7hx That's because ds.size[i] is not actually the number of stones in a component. If you union two nodes which are already present in a component, the size does not increase, but the number of stones increases by 1 for that component. For example: node 3 (row 3) and node 7 (column 2) are already in a component, so the size won't increase but the number of stones increases
At 19:44, we actually need to take anything greater than maxRow+maxCol in ds. This is because if we take the example of [[1,1]], maxRow = 1, maxCol = 1 + 1 + 1 = 3 but the parent size will only be 3 (to store values of 0,1,2 not 3) thus giving runtime error due to array out of bounds during unionBySize or unionByRank.
Bro, in video no. 46 the length of size, rank and parent is (n + 1). So, it would be like (1 + 1 + 1 + 1) = 4. Therefore, we wouldn't get runtime error. If I am wrong please correct me 😅. Whereas Thank You for this example, it made the Understanding more clear.
There is another approach to this question, which seems to be more intuitive. The very core intent of the solution lies in finding the number of components we have. Given that we have n stones where ith stone is placed at coordinates (stones[i][0],stones[i][1]) . Any stone is connected to another stone which lies either in the same row or the same column as the current stone. Maintain two maps namely row and col which would map the row/col to an array which consists list of all stones present in that particular row/col. For any given stone check if there exists any other stone in that row or col , if it does call the union function from Disjoint class to merge the current stone to the component . Consider stones as nodes number from 1 to n. I've attached the code below: class Disjoint{ public: vector parent,size; Disjoint(int n){ parent.resize(n+1); size.resize(n+1,1); for(int i=0;i
it's not working , ig there will be a issue in this method. Lets say we have a stone whose neighbour in same row is connected to different component and a neighbour in same coloumn is connected to different component. than how will you assign parent to it?
use this class DisJointSet { int[] parent; int[] size; int max; int N; DisJointSet(int n) { this.parent = new int[n]; this.size = new int[n]; this.N = n; this.max = 0; for (int i = 0; i < n; i++) { parent[i] = i; size[i] = 1; } } int findParent(int node) { if (parent[node] == node) return node; return parent[node] = findParent(parent[node]); } void unionBySize(int u, int v) { int PU = findParent(u); int PV = findParent(v); if (size[PU] > size[PV]) { size[PU] += size[PV]; parent[PV] = PU; } else { size[PV] += size[PU]; parent[PU] = PV; } } int numOfComponents() { for (int i = 0; i < N; i++) { if (findParent(i) == i) max++; } return max; } } class Solution { public int removeStones(int[][] stones) { HashMap mpX = new HashMap(); HashMap mpY = new HashMap(); int n = stones.length; DisJointSet ds = new DisJointSet(n); for (int i = 0; i < n; i++) { int x = stones[i][0]; int y = stones[i][1]; if (mpX.containsKey(x)) { ds.unionBySize(mpX.get(x), i); } mpX.put(x, i); if (mpY.containsKey(y)) { ds.unionBySize(mpY.get(y), i); } mpY.put(y, i); } return n - ds.numOfComponents(); } }
@@dhruvnagill9391 Same brother had a solution where I was doing BFS and finding each and every stone to create components instead of combining rows and columns. Spend 2 hours figuring out TC : n^2 and SC : n^2 solution
Hello striver bhaiya From the bottom of my heart... I just want to thank you so much... Have completed all of your series till date... Including 53 videos of new graph series too... Submitted every single problem... Only because of you iam able to master all these tough data structures... Please keep doing what you are doing... Thanks again.. P.S: This graph series is the best. No cap. Looking forward to remaining few videos so that i can wrap up graphs too..
There is another approach without using map . So we have to find the connected components of stones and then deduct it from the total no of stones but we don't want to count single nodes as a component. For this we can use the size array of our Disjoint Set class and use it to find the nodes which are single and skip it while counting components. Here is the implementation - int maxRemove(vector& stones, int n) { int maxRow=0; int maxCol=0; for(auto it:stones){ maxRow=max(it[0],maxRow); maxCol=max(it[1],maxCol); } DisjointSet ds(maxRow+maxCol+1); for(auto it:stones){ int row = it[0]; int col = it[1] + maxRow + 1; if(ds.findUPar(row)!=ds.findUPar(col)) ds.unionBySize(row,col); } int cnt=0; for(int i = 0; i < maxRow + maxCol + 1; i++) if(ds.parent[i] == i && ds.size[i] > 1) cnt++; return n - cnt; }
Learnt a lot from you @striver , will be forever grateful for that , thanks a lot , have immense respect for you bhaiya. Thanks for everything, specially for DP series 🔥
Amazing explanation. I am having trouble with Disjoint Set problems, but will checkout your videos for explanation. To avoid using disjoint set, you can solve this problem treating it as Counting Islands (DFS + set), and the answer would be len(stones) - numIslands . Excellent videos, you have gained a new sub.
I think on line 68 the size of the disjoint set should be (mxRow + mxCol + 2). Becuase here we have taken 0 based indexing. Let's understand this with an example 1. Suppose mxRow = 4 which means rows are 0,1,2,3,4 2. mxCol = 3 which means cols are 0,1,2,3 Adding 1 and 2 we get total size = (4+1) + (3+1) = 4 + 3 + 2.
Understood, thanks. For all others, increase the size of disjoint set to maxRow+maxCol+2, the logic is quite intuitive, and you can easily figure it out on your own.
We can also do this problem by mapping every cell to some numerical values, Now traverse and for each cell, check is there any cell same having same row or col of that cell, if found setUnion(map({row, col}, map({otherRow, otherCol), and atlast sum all the component size - 1 TC: O(N^2) Code: class Solution { public: class dsu { public: std::vector parent, _size; dsu(int n) { parent.resize(n + 1, 0); _size.resize(n + 1, 0); for (int i = 0; i < parent.size(); i++) { parent[i] = i; _size[i] = 1; } } int getParent(int u) { if (parent[u] == u) return u; return parent[u] = getParent(parent[u]); } void setUnion(int u, int v) { int unode = parent[u]; int vnode = parent[v]; if (unode != vnode) { if (_size[unode] > _size[vnode]) std::swap(unode, vnode); parent[unode] = vnode; _size[vnode] += _size[unode]; } } }; int removeStones(vector& num) { int n = num.size(); std::map inox; int count = 0; for (int i = 0; i < n; i++) { inox[{num[i][0], num[i][1]}] = count; count++; } dsu ds(count); for (int i = 0; i < n; i++) { int row = num[i][0]; int col = num[i][1]; for (int j = 0; j < n; j++) { if (i != j) { int trow = num[j][0]; int tcol = num[j][1]; if (row == trow || col == tcol) { int u = inox[{row, col}]; int v = inox[{trow, tcol}]; if (ds.getParent(u) != ds.getParent(v)) ds.setUnion(u, v); } } } } int sum = 0; for (int i = 0; i < count; i++) { if (ds.getParent(i) == i) sum += ds._size[i] - 1; } return sum; } };
this question can be solved using simple dfs approach count number of components using dfs ,check if any node is present in same row or column; code- //{ Driver Code Starts // Initial Template for C++ #include using namespace std; // } Driver Code Ends class Solution { public: bool check(vector&stone1,vector&stone2){ if(stone1[0]==stone2[0] || stone1[1]==stone2[1]) return true; return false; }
void dfs(vector&vis,vector&stones, int node){ vis[node]=1;
for(int i=0;i t; while (t--) { int n; cin >> n; vector adj; for (int i = 0; i < n; ++i) { vector temp; for (int i = 0; i < 2; ++i) { int x; cin >> x; temp.push_back(x); } adj.push_back(temp); } Solution obj; cout
Simpler Implementation with the same idea: class DisjointSet { public: vector rank, parent, size; DisjointSet(int n) { rank.resize(n+1, 0); parent.resize(n+1); size.resize(n+1); for(int i = 0;i
19:49 Striver i guess that +1 is actually required .Lets say the number of rows were 5 (means we get maxRow as 4) and number of cols were 4 (means maxCol as 3) . Means here we require a total of 9 nodes(0,1,2,3,4,5,6,7,8) .in your disjoint set code you are initializing all the vector with n(the passed size)+1 . so if you dont do +1 at line 68 the passed size will go as & 7(4+3) and the total size inside the Disjoint set code will become 8(i.e only 0 1 2 3 4 5 6 7 will be entertained) which will ultimately leave the last(8) component and result in runtime error. Thats why when u send +1 at line 68 the size passed beocmes 8 and the additional +1 in your disjoinset code make it a total of 9 (by adding one more into 8)😊 so that every node gets entertained . By the way great lecture. Thanku so much. 😊😊😊😊
alt approach: consider the stones as the nodes in dsu, instead of considering the rows/cols (can optimize the visited array size, i was just lazy) code-> (AC on LC) class DS { public: vectorparent,size; DS(int n) { size.resize(n,1); parent.resize(n); for(int i=0; i=size[ulp_y]) parent[ulp_y]=ulp_x, size[ulp_x]+=size[ulp_y]; else parent[ulp_x]=ulp_y, size[ulp_y]+=size[ulp_x]; } }; class Solution { public: int removeStones(vector& stones) { //there are n stones, so I am making a dsu with the nodes as the n stones int n=stones.size(); //the coords can be anything from 0 to 1e4 //also the rows and cols need to be dealt separately as visited vectorvisX(1e4+1,-1), visY(1e4+1,-1); DS dsu(n); for(int i=0; i
High level intuition behind why max number of stones which can be removed from a component of size k is k-1. A stone can be removed if it shares either the same row or the same col as another stone that has not been removed. We can restate this as follow. Two stones are connected if they share the same row or column. We can only remove one of the stones, but not both. Now consider 3 stones, S1, S2, and S3 such that {S1, S2} are connected, {S2, S3} are connected, however, {S1, S3} are not directly connected. If we remove S1 or S3 first, we can remove one additional stone from the remaining two stones, thus total of two stones. However, if we remove S2 first, we cannot remove any additional stones, since removal of S2 breaks the component into two singleton sets {S1} and {S3}, and S1, S3 cannot be removed since they are the last remaining stones in their respective singleton sets. Thus, the order in which stones are removed DOES matter. However, it turns out that if we remove stones such that least connected stones are removed before more connected stones (intuitively, if stones are linked in a line pattern, remove stones at the end before those in the middle. If stones are arranged in a star pattern, remove stones on the corner before those in the center), we can remove *ALL BUT 1* stone from that component without generating additional components. Thus, for a component with k stones, if we remove stones in an optimal way, we can remove total k-1 stones. The problem then reduces to essentially using a Disjoint set with stones represented as nodes, connecting stones which share the same row/col, and then finding the ans as ans = (size(c1)-1) + (size(c2)-1) + ... + (size(cm)-1) where {c1, c2, ..., cm} are the m components. To easily find the size of each component, we can use 'unionbysize' heuristic.
A more intuitive way is just take the stones as vertices and the same row/column stones connection as edges. Created an edges vector for the same and its easier to implement as a disjoint set ds. Now we can implement kruskal's algo and check for number of connected components and subtract it with total stones to get the removed stones. class Disjoint{ private: vector par; vector sz; public: Disjoint(int n){ for(int i=0;i=sz[parV]){ sz[parU]+=sz[parV]; par[parV]=parU; } else{ sz[parV]+=sz[parU]; par[parU]=parV; } } int findUnConnectedStones(int n){ int ans=0; for(int i=0;i
It's impossible to come up with the working solution of this question in interview if haven't solved this already. I thought of the connected component but could think of DSU and implementation
This is a hard problem , Even knowing that one stone will be left behind in a connected component requires good observation , for example ✅ ✅ ✅✅✅✅✅ ✅ ✅ ✅ Need to smartly canceling out stones to get to left 1.
guys in every video striver is asking to subscribe and like the videos so don't be lazy and do it, this is the least you can do if you find the video helpful
I just noticed that instead of using a map to store the nodes where stones are present, we could simply check through the parent and size/rank structure of our disjoint set class as below: for(int i=0;i1) cnt+=1; } What I noticed was that if a coordinate has a stone, then it's row and column will be attached to each other in our disjoint set, only the empty rows and empty columns will remain single.
Understood !! Thanks a lot bhaiya You are doing a great job All best wishes to you and Happy Diwali 🪔 Can you please let us know how many more videos are you planning to make in Graph series ??
Instead of treating each row and col separately we can just travers the grid - 2times (col wise and row wise) -> we can use (row*n + m) method to number each block. Now while traversing row wise we just need to store the 1st guy and then connect rest of 1's to it in that particular row and similarly we need to do coloumn wise and this is how we can get all components . Now we just need to see no. of different parents and subtract them from total number of stones and hence our question is solved. :) (While deleting make sure that size > 1 for that particular parent)
In disjointSet() class you have taken size of parent, rank all having size n+1, therefore (maxRow+maxCol+1) is working otherwise for n of parent and rank it will be (maxRow+maxCol+2) ?
At 1:36 when you are trying to remove stone from matrix[0][2] because there is another stone in the same column at matrix[3][2] why we remove stone of matrix[0][2] we could have remove the stone of position matrix[3][2] first , by doing so there is no need of removing the stone at position 0,2 because then it no longer have stone that share the same row or col. Any response would be highly appreciated 🙏🙏
If we would remove stone at 3,2 the stone placed at 3,1 couldn't be removed further. In that case we would get an answer 3. But we have to maximize the removal of stones. So we have done that. And we got answer 4
you will not be able to declare the parent array with indices. lets say you take the pair in the parent. But then you would need to declare the size of parent as (mxrow * mxcol) and in the worst case according to constraints mxrow=mxcol= 10^4 , so, this will result into 10^8 and you can't declare an array of size 10^8. . . Hope it'll help you :)
@@vishalsinghrajpurohit6037 just take the stones array and treat each index as a node. You don't need to multiply row and col. Run a n^2 loop and connect two stones if either their rows or columns are same.
Because there are some nodes which are not contain stone and doesn't go for union and that's why they also are ultimate parents of themselves and we traverse through then they will count as a individual component which lead to a wrong answer
we can do that too, look at my code : do this after union of row and cols int size[]=new int[n+m]; for(int arr[]:grid){ int x=find(arr[0]); size[x]++; } int ans=0; for(int i=0; i0) ans++; } return grid.length-ans;
This series is best for many reasons ..one of them are your techniques to explain any problem and its approach are awesome many of the time I don't even watch coding part ..😇😇🫂
@take u forward thanks for the amazing videos. Just wanted to ask 1 thing. Is there a discord server where people can connect ask doubts regarding the DSA sheet that you have shared.
Striver bhaiyaa 1 request. Kindly delete all the toxic comments, from those thumbnail waali ldki's channel. They don't care about studies or placement at all. Just unemployed toxic simps, coming here to spread toxicity. Thank u
I just treated each stone as a node, run a n^2 loop through stones and connected all stones that pairwise share a row or a column. Your code can give memory limit exceed if maxrow and maxcol are too large, but my code has more runtime than yours.
@@anjalitiwari486 He is talking about the approach that was used in the previous DSU video's involving 2d Matrix. But the reason that approach was not used here was cause the expected Time complexity O(N+K) and that approach would give you TLE
Hey,can anyone please tell why is this not working? I'm doing a union by size and then adding ds.size[i]-1 for each ultimate parent but it's giving me wrong ans in leetcode class DisjointSet { public: vector rank, parent, size; DisjointSet(int n) { rank.resize(n + 1, 0); parent.resize(n + 1); size.resize(n + 1); for (int i = 0; i
I am having difficulty in understanding the code. 1. Why need the dimensions as n as in n the dimension of matrix is given? I mean what is the meaning of maxRow and maxCol? 2. Why did we use unordered_map?
I Have written the same code, same Disjointset class but still getting WA in LeetCode & GFG for [[3,2],[3,1],[4,4],[1,1],[0,2],[4,0]]. Following is my code, did I do anything wrong? P.S. I have been using the same disjoint set class for previous questions. int removeStones(vector& stones) { int n = stones.size(); //no. of stones int maxRow = 0; int maxCol = 0; for(auto it: stones){ maxRow = max(maxRow, it[0]); maxCol = max(maxCol, it[1]); } DisjointSet ds(maxRow + maxCol + 1); unordered_map stoneNode; for(auto it: stones){ int nodeRow = it[0]; int nodeCol = it[1] + maxRow + 1; //eg: 2nd col = 1 + rowSize + 1 ds.unionByRank(nodeRow, nodeCol); stoneNode[nodeRow] = 1; stoneNode[nodeCol] = 1; } int count = 0; for(auto it: stoneNode){ if(ds.findUPar(it.first) == it.first){//this means its a parent, we get no. of components count++; } } return n - count; }
![Google Coding Interview Question and Answer - Most Stones Removed with Same Row or Column [LeetCode]](http://i.ytimg.com/vi/beOCN7G4h-M/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
Thanks a lot for this wonderful playlist sir. May i know how many videos are left in this series sir?
Bhaiya your CP sheet is very difficult.....even easy questions are difficult....
@@SatyamEdits suru mei difficult lgega ....but questions solve krte jao....nhi solve ho to solutions dekho..editorials dekho....U will improve in few months .....CPalgorithms website pe various algorithms read kr sakte ho
Brute force is giving wrong answer when Test case [1,0],[0,1]
According to @striver answer must be (n - no. of components) i.e 2-1=1 but in leetcode it gives answer=0 for this test case
@@ankusharora5551 there are 2 components watch video again
The idea of treating each row and each column as a sole node in the disjoint set - is just amazing❤🔥❤🔥
This is a hard problem , Even knowing that one stone will be left behind in a connected component requires good observation , for example
✅
✅
✅✅✅✅✅
✅
✅
✅
Need to smartly canceling out stones to get to left 1.
@@iamnoob7593 The observation is that remove the stone which is connected to least number of stones first. Keep on doing this until you get only 1 stone remaining in the component.
100%
We actually don’t need a Hashmap/set. We can simply write another method/function in disjoint set class which gives valid components count using the logic - traverse through the parent array and whenever we get parent[i]==i, we check if size[i]>1. If yes, we simply increase validComponents count and return it after the iteration. In a nutshell, all nodes with invalid components will have parent as itself but won’t have size greater than 1
@@spandanrastogi7144 in that case also its size will be 2, it is connected with row and col hence size=2
@@spandanrastogi7144 In that case the size itself will become 2 and satisfy above condition. You can take example by adding one more column in between 2 and 3 of Striver's diagram. Also this is getting accepted in GFG.
Or at last you could simply do:
int cnt = 0;
for(int i=0; i 1)cnt++;
return n-cnt;
@@bhavuks6554 Instead of counting the number of components, why can't we do "answer += (ds.size[i]-1) like he showed in the video. This is not working and I am not able to understand why it it not working
@@AdityaKumar-be7hx That's because ds.size[i] is not actually the number of stones in a component. If you union two nodes which are already present in a component, the size does not increase, but the number of stones increases by 1 for that component.
For example: node 3 (row 3) and node 7 (column 2) are already in a component, so the size won't increase but the number of stones increases
At 19:44, we actually need to take anything greater than maxRow+maxCol in ds. This is because if we take the example of [[1,1]], maxRow = 1, maxCol = 1 + 1 + 1 = 3 but the parent size will only be 3 (to store values of 0,1,2 not 3) thus giving runtime error due to array out of bounds during unionBySize or unionByRank.
Thank You so much for this example. It really helped
Bro, in video no. 46 the length of size, rank and parent is (n + 1). So, it would be like (1 + 1 + 1 + 1) = 4.
Therefore, we wouldn't get runtime error.
If I am wrong please correct me 😅.
Whereas Thank You for this example, it made the Understanding more clear.
There is another approach to this question, which seems to be more intuitive.
The very core intent of the solution lies in finding the number of components we have. Given that we have n stones where ith stone is placed at coordinates (stones[i][0],stones[i][1]) . Any stone is connected to another stone which lies either in the same row or the same column as the current stone.
Maintain two maps namely row and col which would map the row/col to an array which consists list of all stones present in that particular row/col.
For any given stone check if there exists any other stone in that row or col , if it does call the union function from Disjoint class to merge the current stone to the component . Consider stones as nodes number from 1 to n. I've attached the code below:
class Disjoint{
public:
vector parent,size;
Disjoint(int n){
parent.resize(n+1);
size.resize(n+1,1);
for(int i=0;i
it's not working , ig there will be a issue in this method. Lets say we have a stone whose neighbour in same row is connected to different component and a neighbour in same coloumn is connected to different component. than how will you assign parent to it?
use this
class DisJointSet {
int[] parent;
int[] size;
int max;
int N;
DisJointSet(int n) {
this.parent = new int[n];
this.size = new int[n];
this.N = n;
this.max = 0;
for (int i = 0; i < n; i++) {
parent[i] = i;
size[i] = 1;
}
}
int findParent(int node) {
if (parent[node] == node)
return node;
return parent[node] = findParent(parent[node]);
}
void unionBySize(int u, int v) {
int PU = findParent(u);
int PV = findParent(v);
if (size[PU] > size[PV]) {
size[PU] += size[PV];
parent[PV] = PU;
} else {
size[PV] += size[PU];
parent[PU] = PV;
}
}
int numOfComponents() {
for (int i = 0; i < N; i++) {
if (findParent(i) == i)
max++;
}
return max;
}
}
class Solution {
public int removeStones(int[][] stones) {
HashMap mpX = new HashMap();
HashMap mpY = new HashMap();
int n = stones.length;
DisJointSet ds = new DisJointSet(n);
for (int i = 0; i < n; i++) {
int x = stones[i][0];
int y = stones[i][1];
if (mpX.containsKey(x)) {
ds.unionBySize(mpX.get(x), i);
}
mpX.put(x, i);
if (mpY.containsKey(y)) {
ds.unionBySize(mpY.get(y), i);
}
mpY.put(y, i);
}
return n - ds.numOfComponents();
}
}
Understood!
THE BEST Graph series ever! Thanks a lot for this!
if someone had told that i solve without watching this video I would have quit coding
I did it without watching the video. But my solution took n^2 TC
@@dhruvnagill9391 Same brother had a solution where I was doing BFS and finding each and every stone to create components instead of combining rows and columns. Spend 2 hours figuring out TC : n^2 and SC : n^2 solution
Hello striver bhaiya
From the bottom of my heart... I just want to thank you so much...
Have completed all of your series till date... Including 53 videos of new graph series too...
Submitted every single problem...
Only because of you iam able to master all these tough data structures...
Please keep doing what you are doing...
Thanks again..
P.S: This graph series is the best. No cap.
Looking forward to remaining few videos so that i can wrap up graphs too..
Proud of u fam.
BHAIYA YOU ARE SINGLE HANDELY HELPING ALL OF US, no one really does this, please keep going in life and thank you vvvv much!
understood man
Great question, never thought of taking whole row or col as a node
same dude this never came to my mind before
cant believe that i've come so far in graph series. Kind of proud of myself now!
There is another approach without using map .
So we have to find the connected components of stones and then deduct it from the total no of stones but we don't want to count single nodes as a component.
For this we can use the size array of our Disjoint Set class and use it to find the nodes which are single and skip it while counting components.
Here is the implementation -
int maxRemove(vector& stones, int n) {
int maxRow=0;
int maxCol=0;
for(auto it:stones){
maxRow=max(it[0],maxRow);
maxCol=max(it[1],maxCol);
}
DisjointSet ds(maxRow+maxCol+1);
for(auto it:stones){
int row = it[0];
int col = it[1] + maxRow + 1;
if(ds.findUPar(row)!=ds.findUPar(col))
ds.unionBySize(row,col);
}
int cnt=0;
for(int i = 0; i < maxRow + maxCol + 1; i++)
if(ds.parent[i] == i && ds.size[i] > 1)
cnt++;
return n - cnt;
}
How many videos remaining vai?
This is the best graph series so far😁
Learnt a lot from you @striver , will be forever grateful for that , thanks a lot ,
have immense respect for you bhaiya.
Thanks for everything, specially for DP series 🔥
Amazing explanation. I am having trouble with Disjoint Set problems, but will checkout your videos for explanation. To avoid using disjoint set, you can solve this problem treating it as Counting Islands (DFS + set), and the answer would be len(stones) - numIslands . Excellent videos, you have gained a new sub.
Hi. Can you share the code for this logic?
UNDERSTOOOOD BHAIYA PLEASE CONTINUE
great writing codes without any errors thats the reason you are Software engineer at Google Hope one day i will be like you
Question becomes easy after watching your videos.🙌
I think on line 68 the size of the disjoint set should be (mxRow + mxCol + 2).
Becuase here we have taken 0 based indexing.
Let's understand this with an example
1. Suppose mxRow = 4 which means rows are 0,1,2,3,4
2. mxCol = 3 which means cols are 0,1,2,3
Adding 1 and 2 we get total size = (4+1) + (3+1) = 4 + 3 + 2.
In the disjoint set algorithm he's considering the size array as [v+1] that's the reason he's getting a arrayoutof bound index error
//{ Driver Code Starts
import java.util.*;
import java.lang.*;
import java.io.*;
class GFG {
public static void main(String[] args) throws IOException {
Scanner sc = new Scanner(System.in);
int T = sc.nextInt();
while (T-- > 0) {
int n = sc.nextInt();
int[][] arr = new int[n][2];
for(int i=0;i
@@saseerak8763 thanks
oh my god thanks so much. i was wondering what's the problem for so long
Understood, thanks. For all others, increase the size of disjoint set to maxRow+maxCol+2, the logic is quite intuitive, and you can easily figure it out on your own.
Bhai 1 million karwao bhai ke jaldi se
hamare liye itna kuch kar rahe hai bhaiya
When i start thinking that now i can tackle questions as you do, you just amaze me up with something extraordinary.... Superb explanation
You are a legend💕❤️
Thanks bhaiya for using English so that everyone could understood u
Thanks bhai for everything. We're with you
*unordered_set* can be used instead of *unordered_map*
very well done, Thanks a ton for the help.........🙏🏻🙏🏻🙏🏻
We can also do this problem by mapping every cell to some numerical values, Now traverse and for each cell, check is there any cell same having same row or col of that cell, if found setUnion(map({row, col}, map({otherRow, otherCol), and atlast sum all the component size - 1
TC: O(N^2)
Code:
class Solution {
public:
class dsu
{
public:
std::vector parent, _size;
dsu(int n)
{
parent.resize(n + 1, 0);
_size.resize(n + 1, 0);
for (int i = 0; i < parent.size(); i++)
{
parent[i] = i;
_size[i] = 1;
}
}
int getParent(int u)
{
if (parent[u] == u)
return u;
return parent[u] = getParent(parent[u]);
}
void setUnion(int u, int v)
{
int unode = parent[u];
int vnode = parent[v];
if (unode != vnode)
{
if (_size[unode] > _size[vnode])
std::swap(unode, vnode);
parent[unode] = vnode;
_size[vnode] += _size[unode];
}
}
};
int removeStones(vector& num) {
int n = num.size();
std::map inox;
int count = 0;
for (int i = 0; i < n; i++)
{
inox[{num[i][0], num[i][1]}] = count;
count++;
}
dsu ds(count);
for (int i = 0; i < n; i++)
{
int row = num[i][0];
int col = num[i][1];
for (int j = 0; j < n; j++)
{
if (i != j)
{
int trow = num[j][0];
int tcol = num[j][1];
if (row == trow || col == tcol)
{
int u = inox[{row, col}];
int v = inox[{trow, tcol}];
if (ds.getParent(u) != ds.getParent(v))
ds.setUnion(u, v);
}
}
}
}
int sum = 0;
for (int i = 0; i < count; i++)
{
if (ds.getParent(i) == i)
sum += ds._size[i] - 1;
}
return sum;
}
};
this question can be solved using simple dfs
approach count number of components using dfs ,check if any node is present in same row or column;
code-
//{ Driver Code Starts
// Initial Template for C++
#include
using namespace std;
// } Driver Code Ends
class Solution {
public:
bool check(vector&stone1,vector&stone2){
if(stone1[0]==stone2[0] || stone1[1]==stone2[1]) return true;
return false;
}
void dfs(vector&vis,vector&stones, int node){
vis[node]=1;
for(int i=0;i t;
while (t--) {
int n;
cin >> n;
vector adj;
for (int i = 0; i < n; ++i) {
vector temp;
for (int i = 0; i < 2; ++i) {
int x;
cin >> x;
temp.push_back(x);
}
adj.push_back(temp);
}
Solution obj;
cout
Simpler Implementation with the same idea:
class DisjointSet {
public:
vector rank, parent, size;
DisjointSet(int n) {
rank.resize(n+1, 0);
parent.resize(n+1);
size.resize(n+1);
for(int i = 0;i
Nice but time complexity of this code is O(n^2) but the code given by striver has O(n) time complexity.
Alternative Approach: Treat each stone as a node
class DisjointSet {
map rank, size; // Rank and size for pairs
map parent; // Parent map for pairs
public:
// Constructor takes a vector of vectors to initialize the DSU
DisjointSet(const vector& nodes) {
for (const auto& node : nodes) {
pair p = {node[0], node[1]};
parent[p] = p; // Each pair is its own parent initially
rank[p] = 0; // Initial rank is 0
size[p] = 1; // Initial size is 1
}
}
// Find ultimate parent of a pair with path compression
pair findUParent(pair u) {
if (u == parent[u]) {
return u;
}
return parent[u] = findUParent(parent[u]);
}
// Union by rank for pairs of pairs
void unionByrank(pair edge) {
pair u = edge.first;
pair v = edge.second;
pair up_u = findUParent(u);
pair up_v = findUParent(v);
if (up_u == up_v) return;
if (rank[up_u] < rank[up_v]) {
parent[up_u] = up_v;
}
else if (rank[up_v] < rank[up_u]) {
parent[up_v] = up_u;
}
else {
parent[up_v] = up_u;
rank[up_u]++;
}
}
// Union by size for pairs of pairs
void unionBysize(pair edge) {
pair u = edge.first;
pair v = edge.second;
pair up_u = findUParent(u);
pair up_v = findUParent(v);
if (up_u == up_v) return;
if (size[up_u] < size[up_v]) {
parent[up_u] = up_v;
size[up_v] += size[up_u];
}
else {
parent[up_v] = up_u;
size[up_u] += size[up_v];
}
}
};
class Solution {
private:
vector findEdgeList(vector& coordinates) {
unordered_map row_map, col_map;
for (auto& c : coordinates) {
int row = c[0];
int col = c[1];
pair coord = {row, col};
row_map[row].push_back(coord);
col_map[col].push_back(coord);
}
set edges;
for (auto& c : coordinates) {
int row = c[0];
int col = c[1];
pair coord = {row, col};
for (auto& point : row_map[row]) {
if (point != coord) {
edges.insert({min(coord, point), max(coord, point)});
}
}
for (auto& point : col_map[col]) {
if (point != coord) {
edges.insert({min(coord, point), max(coord, point)});
}
}
}
return vector(edges.begin(), edges.end());
}
struct pair_hash {
template
size_t operator()(const pair& p) const {
auto h1 = hash{}(p.first);
auto h2 = hash{}(p.second);
return h1 ^ h2;
}
};
public:
int removeStones(vector& stones) {
vector edges = findEdgeList(stones);
DisjointSet ds(stones);
for(auto& edge : edges){
ds.unionByrank(edge);
}
unordered_map ulp;
for(auto& s : stones){
pair stone = {s[0], s[1]};
auto up_s = ds.findUParent(stone);
ulp[up_s]++;
}
int result=0;
for(const auto& [key, value] : ulp){
if(value != 1){
result += (value - 1);
}
}
return result;
}
};
19:49 Striver i guess that +1 is actually required .Lets say the number of rows were 5 (means we get maxRow as 4) and number of cols were 4 (means maxCol as 3) . Means here we require a total of 9 nodes(0,1,2,3,4,5,6,7,8) .in your disjoint set code you are initializing all the vector with n(the passed size)+1 . so if you dont do +1 at line 68 the passed size will go as & 7(4+3) and the total size inside the Disjoint set code will become 8(i.e only 0 1 2 3 4 5 6 7 will be entertained) which will ultimately leave the last(8) component and result in runtime error.
Thats why when u send +1 at line 68 the size passed beocmes 8 and the additional +1 in your disjoinset code make it a total of 9 (by adding one more into 8)😊 so that every node gets entertained .
By the way great lecture. Thanku so much. 😊😊😊😊
understood, Thanks a lot...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
what an explanation 🔥....literally!!!!!!!!!!!!!!!
alt approach: consider the stones as the nodes in dsu, instead of considering the rows/cols
(can optimize the visited array size, i was just lazy)
code-> (AC on LC)
class DS
{
public:
vectorparent,size;
DS(int n)
{
size.resize(n,1);
parent.resize(n);
for(int i=0; i=size[ulp_y]) parent[ulp_y]=ulp_x, size[ulp_x]+=size[ulp_y];
else parent[ulp_x]=ulp_y, size[ulp_y]+=size[ulp_x];
}
};
class Solution
{
public:
int removeStones(vector& stones)
{
//there are n stones, so I am making a dsu with the nodes as the n stones
int n=stones.size();
//the coords can be anything from 0 to 1e4
//also the rows and cols need to be dealt separately as visited
vectorvisX(1e4+1,-1), visY(1e4+1,-1);
DS dsu(n);
for(int i=0; i
I did the same damn thing 😅
High level intuition behind why max number of stones which can be removed from a component of size k is k-1.
A stone can be removed if it shares either the same row or the same col as another stone that has not been removed. We can restate this as follow.
Two stones are connected if they share the same row or column. We can only remove one of the stones, but not both. Now consider 3 stones, S1, S2, and S3 such that {S1, S2} are connected, {S2, S3} are connected, however, {S1, S3} are not directly connected. If we remove S1 or S3 first, we can remove one additional stone from the remaining two stones, thus total of two stones. However, if we remove S2 first, we cannot remove any additional stones, since removal of S2 breaks the component into two singleton sets {S1} and {S3}, and S1, S3 cannot be removed since they are the last remaining stones in their respective singleton sets. Thus, the order in which stones are removed DOES matter. However, it turns out that if we remove stones such that least connected stones are removed before more connected stones (intuitively, if stones are linked in a line pattern, remove stones at the end before those in the middle. If stones are arranged in a star pattern, remove stones on the corner before those in the center), we can remove *ALL BUT 1* stone from that component without generating additional components.
Thus, for a component with k stones, if we remove stones in an optimal way, we can remove total k-1 stones.
The problem then reduces to essentially using a Disjoint set with stones represented as nodes, connecting stones which share the same row/col, and then finding the ans as
ans = (size(c1)-1) + (size(c2)-1) + ... + (size(cm)-1)
where {c1, c2, ..., cm} are the m components.
To easily find the size of each component, we can use 'unionbysize' heuristic.
A more intuitive way is just take the stones as vertices and the same row/column stones connection as edges. Created an edges vector for the same and its easier to implement as a disjoint set ds. Now we can implement kruskal's algo and check for number of connected components and subtract it with total stones to get the removed stones.
class Disjoint{
private:
vector par;
vector sz;
public:
Disjoint(int n){
for(int i=0;i=sz[parV]){
sz[parU]+=sz[parV];
par[parV]=parU;
}
else{
sz[parV]+=sz[parU];
par[parU]=parV;
}
}
int findUnConnectedStones(int n){
int ans=0;
for(int i=0;i
Bhaiya please make video on Convex Hull algorithm and concepts like dp on trees and Heavy Light Decomposition.
It's impossible to come up with the working solution of this question in interview if haven't solved this already.
I thought of the connected component but could think of DSU and implementation
This is a hard problem , Even knowing that one stone will be left behind in a connected component requires good observation , for example
✅
✅
✅✅✅✅✅
✅
✅
✅
Need to smartly canceling out stones to get to left 1.
I solved it using bfs wont say unsolvable but yeah definitely a bit hard
damn , wtf, ultimate approach striver, Just amazing , how to even think of this 🤯
is it something we regulary use , in soft engg or what? just curious
guys in every video striver is asking to subscribe and like the videos so don't be lazy and do it, this is the least you can do if you find the video helpful
Great approach and explanation.
I just noticed that instead of using a map to store the nodes where stones are present, we could simply check through the parent and size/rank structure of our disjoint set class as below:
for(int i=0;i1)
cnt+=1;
}
What I noticed was that if a coordinate has a stone, then it's row and column will be attached to each other in our disjoint set, only the empty rows and empty columns will remain single.
it must be for(int i=0;i1)
{
cnt++;
}
} because here we have to traverse every row and col
how you all can solve these questions ,it becomes very difficult for me , i can't solve without watching vid ...Ah it's too tough for me i think
Thank you sir 🙏
Understood! Super amazing explanation as always, thank you very much!!
Understood !!
Thanks a lot bhaiya
You are doing a great job
All best wishes to you and Happy Diwali 🪔
Can you please let us know how many more videos are you planning to make in Graph series ??
9 more
@@karanveersingh5535 how do you know bro ?
@@ece_a-65_parthbhalerao8 Check Striver's A2Z Sheet
How to think of this in an interview 🤯
get well soon bhaiya
U were right bro👍
what an explanation striver
Understood 🔥🔥
Understood!! Great explanation
Instead of treating each row and col separately we can just travers the grid - 2times (col wise and row wise) -> we can use (row*n + m) method to number each block. Now while traversing row wise we just need to store the 1st guy and then connect rest of 1's to it in that particular row and similarly we need to do coloumn wise and this is how we can get all components . Now we just need to see no. of different parents and subtract them from total number of stones and hence our question is solved. :) (While deleting make sure that size > 1 for that particular parent)
connected conponent mentioned DSU!!!!
Understood!!
Another approach using DFS:
void dfs(int ind,vector& stones,vector& vis)
{
vis[ind]=1;
for(int i=0;i
striver is a gem in the field of DSA/CP ...superb playlist 🔥
tok sometime to understand but really helpful
The idea of resolving rows and cols and connecting them is absolutely amazing. ♨♨♨♨
In disjointSet() class you have taken size of parent, rank all having size n+1, therefore (maxRow+maxCol+1) is working otherwise for n of parent and rank it will be (maxRow+maxCol+2) ?
yes (maxRow+1+maxCol+1)
but why bro i am having difficulty to understandthis
@@JavidIqbal7 its that the nodes for row starts with one and similarly nodes from col start with one instead of zero
Superb vide0 ,Understood
Amazing thinking
Thanks Striver
understood striver
At 1:36 when you are trying to remove stone from matrix[0][2] because there is another stone in the same column at matrix[3][2] why we remove stone of matrix[0][2] we could have remove the stone of position matrix[3][2] first , by doing so there is no need of removing the stone at position 0,2 because then it no longer have stone that share the same row or col. Any response would be highly appreciated 🙏🙏
If we would remove stone at 3,2 the stone placed at 3,1 couldn't be removed further. In that case we would get an answer 3. But we have to maximize the removal of stones. So we have done that. And we got answer 4
awesome explanation
understood thanks bhaiya
understood bhaiya
Hey striver. It would have been a lot more clever if we used the index of the coordinate as node for DSU. Reduces the complexity like anything.
Even I thought of it but I was not able to solve. Can you share your code if you've solved it using that method?
you will not be able to declare the parent array with indices. lets say you take the pair in the parent. But then you would need to declare the size of parent as (mxrow * mxcol) and in the worst case according to constraints mxrow=mxcol= 10^4 , so, this will result into 10^8 and you can't declare an array of size 10^8.
.
.
Hope it'll help you :)
@@vishalsinghrajpurohit6037 just take the stones array and treat each index as a node. You don't need to multiply row and col. Run a n^2 loop and connect two stones if either their rows or columns are same.
Pass maxRow + maxCol +2 as size , to avoid runtime error
There is no need to hashmap to find number of valid components
int NC=0;
for(int i=0;i
Thanks🙌
thanks for the great video
why do we use a hashmap? Why can't we just iterate from 0 to all nodes and see the unique parents like we've done prev?
Because there are some nodes which are not contain stone and doesn't go for union and that's why they also are ultimate parents of themselves and we traverse through then they will count as a individual component which lead to a wrong answer
we can do that too, look at my code :
do this after union of row and cols
int size[]=new int[n+m];
for(int arr[]:grid){
int x=find(arr[0]);
size[x]++;
}
int ans=0;
for(int i=0; i0) ans++;
}
return grid.length-ans;
@@adityakhare2492 Thanks bhai. Makes sense!
@@adityakhare2492 thanks bro
I was also looking for this answer since last 2 days
Understood Explanation!!
Understooddddd ❤
Hey bro how striver is calculating maxrow and maxcol I am not able to understand it how to get it.pliz help
If we iterate through loop we will get maxrow=2 and maxcol=2 how is it making sense of having a dsu of 5
Thank you !!!
Cant we do this problem using DP ? For each stone, either we don't remove it or we remove it and recurse for other stones and get the maximum answer.
Understood !, thanks man
Good to know arnub goswami , inspired your speaking skills 😃
This series is best for many reasons ..one of them are your techniques to explain any problem and its approach are awesome many of the time I don't even watch coding part ..😇😇🫂
Hey Striver Plz Make a vedio on
Vertex Clover Problem
Two Clique Problem
Minimum Cash Flow
Understood 😃
Great Video
Understood✌️
solution which combines indivisual stones (gives correct ans ,by exceeds time for larger cases)
class DisjointSet
{
public:
vector parent;
vector rank;
DisjointSet(int n)
{
parent.resize(n);
rank.resize(n,0);
for(int i=0;i
@take u forward thanks for the amazing videos. Just wanted to ask 1 thing. Is there a discord server where people can connect ask doubts regarding the DSA sheet that you have shared.
Understood.
Understood
Striver bhaiyaa 1 request.
Kindly delete all the toxic comments, from those thumbnail waali ldki's channel.
They don't care about studies or placement at all. Just unemployed toxic simps, coming here to spread toxicity.
Thank u
Hashmap is not required striver sir , We can just use parent[] and size[] to count the no of connected components.
I just treated each stone as a node, run a n^2 loop through stones and connected all stones that pairwise share a row or a column. Your code can give memory limit exceed if maxrow and maxcol are too large, but my code has more runtime than yours.
Interesting! Can you share the code pls?
@@anjalitiwari486 He is talking about the approach that was used in the previous DSU video's involving 2d Matrix. But the reason that approach was not used here was cause the expected Time complexity O(N+K) and that approach would give you TLE
understood sir
got the approach but couldnt get how to connect them as dsu
Amazinggggg✌️
Hey,can anyone please tell why is this not working?
I'm doing a union by size and then adding ds.size[i]-1 for each ultimate parent but it's giving me wrong ans in leetcode
class DisjointSet {
public:
vector rank, parent, size;
DisjointSet(int n) {
rank.resize(n + 1, 0);
parent.resize(n + 1);
size.resize(n + 1);
for (int i = 0; i
UNDERSTOOD
How many **MORE** videos will be uploaded for GRAPH Series?
The answer was just in front of our eyes. We just had to connect the dots(pun intended).
Understood!
I am having difficulty in understanding the code. 1. Why need the dimensions as n as in n the dimension of matrix is given? I mean what is the meaning of maxRow and maxCol? 2. Why did we use unordered_map?
I Have written the same code, same Disjointset class but still getting WA in LeetCode & GFG for [[3,2],[3,1],[4,4],[1,1],[0,2],[4,0]]. Following is my code, did I do anything wrong? P.S. I have been using the same disjoint set class for previous questions.
int removeStones(vector& stones) {
int n = stones.size(); //no. of stones
int maxRow = 0;
int maxCol = 0;
for(auto it: stones){
maxRow = max(maxRow, it[0]);
maxCol = max(maxCol, it[1]);
}
DisjointSet ds(maxRow + maxCol + 1);
unordered_map stoneNode;
for(auto it: stones){
int nodeRow = it[0];
int nodeCol = it[1] + maxRow + 1; //eg: 2nd col = 1 + rowSize + 1
ds.unionByRank(nodeRow, nodeCol);
stoneNode[nodeRow] = 1;
stoneNode[nodeCol] = 1;
}
int count = 0;
for(auto it: stoneNode){
if(ds.findUPar(it.first) == it.first){//this means its a parent, we get no. of components
count++;
}
}
return n - count;
}