G-53. Most Stones Removed with Same Row or Column - DSU
Vložit
- čas přidán 13. 07. 2024
- GfG-Problem Link: bit.ly/3QHZuE6
C++/Java/Codes and Notes Link: takeuforward.org/data-structu...
DP Series: • Striver's Dynamic Prog...
SDE Sheet: takeuforward.org/interviews/s...
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.geeksforgeeks.org/co...
Code "takeuforward" for 20% off on sys-design: get.interviewready.io?_aff=takeuforward
Crypto, I use the Wazirx app: wazirx.com/invite/xexnpc4u
Take 750 rs free Amazon Stock from me: indmoney.onelink.me/RmHC/idje...
Earn 100 rs by making a Grow Account for investing: app.groww.in/v3cO/8hu879t0
Linkedin/Instagram/Telegram: linktr.ee/takeUforward
---------------------------------------------------------------------------------------------------------------------------
![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.
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
Understood!
THE BEST Graph series ever! Thanks a lot for this!
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.
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
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..
Understood! Super amazing explanation as always, thank you very much!!
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 🔥
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.
When i start thinking that now i can tackle questions as you do, you just amaze me up with something extraordinary.... Superb explanation
Thanks bhai for everything. We're with you
How many videos remaining vai?
This is the best graph series so far😁
BHAIYA YOU ARE SINGLE HANDELY HELPING ALL OF US, no one really does this, please keep going in life and thank you vvvv much!
UNDERSTOOOOD BHAIYA PLEASE CONTINUE
Question becomes easy after watching your videos.🙌
Great approach and explanation.
Understood!! Great explanation
understood man
Great question, never thought of taking whole row or col as a node
same dude this never came to my mind before
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
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?
You are a legend💕❤️
Thanks bhaiya for using English so that everyone could understood u
very well done, Thanks a ton for the help.........🙏🏻🙏🏻🙏🏻
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
Understood !, thanks man
great writing codes without any errors thats the reason you are Software engineer at Google Hope one day i will be like you
Amazing thinking
what an explanation striver
awesome explanation
great explanation
cant believe that i've come so far in graph series. Kind of proud of myself now!
Thank you sir 🙏
understoooddd!!
Bhai 1 million karwao bhai ke jaldi se
hamare liye itna kuch kar rahe hai bhaiya
Understood!
if someone had told that i solve without watching this video I would have quit coding
Superb vide0 ,Understood
U were right bro👍
understood, Thanks a lot...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
understood thanks bhaiya
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 ..😇😇🫂
Understood Explanation!!
Understood❤❤❤
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?
Great Video
Understood 🔥🔥
Understood.
Thanks🙌
Bhaiya please make video on Convex Hull algorithm and concepts like dp on trees and Heavy Light Decomposition.
*unordered_set* can be used instead of *unordered_map*
The idea of resolving rows and cols and connecting them is absolutely amazing. ♨♨♨♨
understood!!!
UNDERSTOOD
understood
Amazinggggg✌️
Understood 👍
get well soon bhaiya
@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.
great
tok sometime to understand but really helpful
Understood✌️
Understood
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
Understood 😃
understood sir
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
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
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;
}
};
understood!!!!!!!!!!!!!!
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)
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.
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
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
How to think of this in an interview 🤯
Hey Striver Plz Make a vedio on
Vertex Clover Problem
Two Clique Problem
Minimum Cash Flow
striver is a gem in the field of DSA/CP ...superb playlist 🔥
Hashmap is not required striver sir , We can just use parent[] and size[] to count the no of connected components.
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.
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?
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
@@unknownuyio9133 its that the nodes for row starts with one and similarly nodes from col start with one instead of zero
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 🙏🙏
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.
Understood!!
Another approach using DFS:
void dfs(int ind,vector& stones,vector& vis)
{
vis[ind]=1;
for(int i=0;i
Pass maxRow + maxCol +2 as size , to avoid runtime error
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;
}
How many **MORE** videos will be uploaded for GRAPH Series?
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
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
I have a doubt after finding the connected components why cant we iterate on size array and add it in our answer by subtracting one from the size of each component.
Bhaiya ye graph series meye or kitne videos honge ?
Striver bhai, How can someone come up with this intuition during an interview 😢😢
Good to know arnub goswami , inspired your speaking skills 😃
We can also use stones as node. Just use two map to store the first encountered stones.
So for a node is there is a node present at that row then union with it or else update the current node to that row and similarly for column.
class DisjointSet{
private:
vector parent,size;
public:
DisjointSet(int n){
parent.resize(n);
size.resize(n,1);
for(int i=0;i=size[ulp_v]){
parent[ulp_v]=ulp_u;
size[ulp_u]+=size[ulp_v];
}
else{
parent[ulp_u]=ulp_v;
size[ulp_v]+=size[ulp_u];
}
}
//extra function to find the no of actual component.
int countComp(){
unordered_set us;
for(int i=0;i
The answer was just in front of our eyes. We just had to connect the dots(pun intended).
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
if anyone is getting runtime error in leetcode while running the code just update the size of disjoint set ds to maxrow + maxcol + 2
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
Next series??
This is the first question which I didn't understand or was not convinced about taking row+col as nodes. The question constraint clearly states grid can be of max [10^4][10^4]. And if stone is present in that last cell i.e grid[10000][10000] then using a list of size 20000 is not at all recommended in interviews. Your sol S.C is O(20000) is not acceptable!! Expected somewhat better and clean approach, from you!!