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
@rohitn63332 жыл бұрын
Thanks a lot for this wonderful playlist sir. May i know how many videos are left in this series sir?
@SatyamEdits2 жыл бұрын
Bhaiya your CP sheet is very difficult.....even easy questions are difficult....
@rishav1442 жыл бұрын
@@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
@ankusharora55512 жыл бұрын
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
@jaswinders2670 Жыл бұрын
@@ankusharora5551 there are 2 components watch video again
@sayantaniguha85192 жыл бұрын
The idea of treating each row and each column as a sole node in the disjoint set - is just amazing❤🔥❤🔥
@iamnoob7593 Жыл бұрын
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.
@rahulsangvikar79737 ай бұрын
@@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.
@yashshukla1637Ай бұрын
100%
@adwaitmhatre75612 жыл бұрын
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
@herculean6748 Жыл бұрын
@@spandanrastogi7144 in that case also its size will be 2, it is connected with row and col hence size=2
@niteshchaudhary4724 Жыл бұрын
@@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 Жыл бұрын
Or at last you could simply do: int cnt = 0; for(int i=0; i 1)cnt++; return n-cnt;
@AdityaKumar-be7hx Жыл бұрын
@@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
@parinav10 Жыл бұрын
@@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
@dhruvrawat7023 Жыл бұрын
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.
@nihalrawat1431 Жыл бұрын
Thank You so much for this example. It really helped
@sumitmaurya109 Жыл бұрын
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.
@we_crood Жыл бұрын
if someone had told that i solve without watching this video I would have quit coding
@dhruvnagill93915 ай бұрын
I did it without watching the video. But my solution took n^2 TC
@shauryatomer10585 ай бұрын
@@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
@nagatanujabathena63192 жыл бұрын
Understood! THE BEST Graph series ever! Thanks a lot for this!
@harshmittal3128 Жыл бұрын
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
@tejassankhla126411 ай бұрын
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?
@agrawalmitesh43953 ай бұрын
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(); } }
@shreyarawatvlogs6920 Жыл бұрын
cant believe that i've come so far in graph series. Kind of proud of myself now!
@divyareddy76222 жыл бұрын
BHAIYA YOU ARE SINGLE HANDELY HELPING ALL OF US, no one really does this, please keep going in life and thank you vvvv much!
@gsmdfaheem2 жыл бұрын
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..
@devanshsingh26 ай бұрын
Proud of u fam.
@AlokSingh-jw8fr2 жыл бұрын
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.
@saseerak87632 жыл бұрын
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
@saseerak87632 жыл бұрын
//{ 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
@cr7johnChan2 жыл бұрын
@@saseerak8763 thanks
@capybarapika Жыл бұрын
oh my god thanks so much. i was wondering what's the problem for so long
@AS-gf3ci4 күн бұрын
19:48 -> Small correction, we will always require totalNodes >= (maxRow + maxCol + 1), +1 is very much required. Anything more than that will also work but this the bare min. no. of nodes required to solve this problem.
@Rajat_maurya2 жыл бұрын
understood man Great question, never thought of taking whole row or col as a node
@lakshsinghania Жыл бұрын
same dude this never came to my mind before
@tousifjaved34852 жыл бұрын
How many videos remaining vai? This is the best graph series so far😁
@pacomarmolejo34922 жыл бұрын
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.
@anjalitiwari4862 жыл бұрын
Hi. Can you share the code for this logic?
@huungryyyy5 ай бұрын
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. 😊😊😊😊
@techtoys-tx9th2 жыл бұрын
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 🔥
@mohdkhaleeq74682 жыл бұрын
great writing codes without any errors thats the reason you are Software engineer at Google Hope one day i will be like you
@nitinkumar59742 жыл бұрын
Bhai 1 million karwao bhai ke jaldi se hamare liye itna kuch kar rahe hai bhaiya
@hamzaarif6945 Жыл бұрын
*unordered_set* can be used instead of *unordered_map*
@ce029chirag6 Жыл бұрын
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
@divyareddy76222 жыл бұрын
UNDERSTOOOOD BHAIYA PLEASE CONTINUE
@TheDev05 Жыл бұрын
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; } };
@sauravchandra10 Жыл бұрын
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.
@kunalchaudhary28082 жыл бұрын
Question becomes easy after watching your videos.🙌
@rupeshjha47172 жыл бұрын
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
@iamnoob7593 Жыл бұрын
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.
@pogpieunited33798 ай бұрын
I solved it using bfs wont say unsolvable but yeah definitely a bit hard
@snehadeepАй бұрын
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; }
@ShivamArorabec20 күн бұрын
Thought the same thing bro
@codingvibesofficial2 жыл бұрын
You are a legend💕❤️ Thanks bhaiya for using English so that everyone could understood u
@stith_pragya Жыл бұрын
very well done, Thanks a ton for the help.........🙏🏻🙏🏻🙏🏻
@deepanshuthakur14010 ай бұрын
When i start thinking that now i can tackle questions as you do, you just amaze me up with something extraordinary.... Superb explanation
@anshulagarwal66822 жыл бұрын
Bhaiya please make video on Convex Hull algorithm and concepts like dp on trees and Heavy Light Decomposition.
@rajK29_ Жыл бұрын
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.
@priyanshugagiya4515 Жыл бұрын
it must be for(int i=0;i1) { cnt++; } } because here we have to traverse every row and col
@_B_Yashika7 ай бұрын
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
@getgoin22172 жыл бұрын
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
@swetakumari73056 ай бұрын
How to think of this in an interview 🤯
@stith_pragya Жыл бұрын
understood, Thanks a lot...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻
@FooBar-lb5wf4 ай бұрын
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.
@ksankethkumar7223 Жыл бұрын
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
@sayandey2492 Жыл бұрын
Nice but time complexity of this code is O(n^2) but the code given by striver has O(n) time complexity.
@priyapandey89512 ай бұрын
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
@KittyMaheshwari2 жыл бұрын
Thanks bhai for everything. We're with you
@JohnWick-oj6bw2 жыл бұрын
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
@AkshatTambi7 ай бұрын
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
@kunalkhallar96995 ай бұрын
I did the same damn thing 😅
@kinshuk17432 жыл бұрын
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.
@abhaykumarsingh3884Ай бұрын
There is no need to hashmap to find number of valid components int NC=0; for(int i=0;i
@mriduljain6809 Жыл бұрын
Understood!! Another approach using DFS: void dfs(int ind,vector& stones,vector& vis) { vis[ind]=1; for(int i=0;i
@ece_a-65_parthbhalerao82 жыл бұрын
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 ??
Understood! Super amazing explanation as always, thank you very much!!
@japneetsingh3306 Жыл бұрын
get well soon bhaiya
@harcharansingh199711 ай бұрын
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 🙏🙏
@subratamandal29245 ай бұрын
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
@utkarshpal93772 ай бұрын
damn , wtf, ultimate approach striver, Just amazing , how to even think of this 🤯
@utkarshpal93772 ай бұрын
is it something we regulary use , in soft engg or what? just curious
@notsodope72272 жыл бұрын
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?
@adityakhare24922 жыл бұрын
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
@HarshitMaurya2 жыл бұрын
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;
@notsodope72272 жыл бұрын
@@adityakhare2492 Thanks bhai. Makes sense!
@shivangmathur61122 жыл бұрын
@@adityakhare2492 thanks bro I was also looking for this answer since last 2 days
@iamnoob7593 Жыл бұрын
Hashmap is not required striver sir , We can just use parent[] and size[] to count the no of connected components.
@Rajat_maurya2 жыл бұрын
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) ?
@rishabhgupta98462 жыл бұрын
yes (maxRow+1+maxCol+1)
@JavidIqbal72 жыл бұрын
but why bro i am having difficulty to understandthis
@raunakkumar6144 Жыл бұрын
@@JavidIqbal7 its that the nodes for row starts with one and similarly nodes from col start with one instead of zero
@gautamgupta71487 ай бұрын
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)
@GyaanGrave2 жыл бұрын
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.
@stephen97262 жыл бұрын
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?
@vishalsinghrajpurohit6037 Жыл бұрын
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 :)
@Dontpushyour_luck Жыл бұрын
@@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.
@Dontpushyour_luck Жыл бұрын
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 Жыл бұрын
Interesting! Can you share the code pls?
@RajatSingh-vs6wu Жыл бұрын
@@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
@abhirupray24949 ай бұрын
Great approach and explanation.
@viralshah3162 ай бұрын
got the approach but couldnt get how to connect them as dsu
@r_uhi0510 ай бұрын
Understood!! Great explanation
@harshkanani6605 Жыл бұрын
what an explanation striver
@Now_I_am_all_fired_up2 жыл бұрын
Hey Striver Plz Make a vedio on Vertex Clover Problem Two Clique Problem Minimum Cash Flow
@xhortsclub3 ай бұрын
we intialise size of disjoint ds as maxrow+maxcol+1 , here +1 is not for safety reason it is exact size of disjoinset ds because of , let number of rows is n and number of column is m so maxrow updated as n-1 and maxcol updated as m-1 so we do +1 to intialize size of ds as n+m-1==maxrow+maxcol+1 .
@kr_ankit1232 жыл бұрын
The idea of resolving rows and cols and connecting them is absolutely amazing. ♨♨♨♨
@isheep9025 Жыл бұрын
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
@salmankhader1258 Жыл бұрын
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.
@tusharmishra81902 жыл бұрын
How many **MORE** videos will be uploaded for GRAPH Series?
@naveensingh47632 жыл бұрын
U were right bro👍
@gangsta_coder_12 Жыл бұрын
Understood 🔥🔥
@adarshmv2618 ай бұрын
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!!
@mayanksaurabhmayanksaurabh92712 жыл бұрын
@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.
@techatnyc73204 ай бұрын
Thanks Striver
@pmshowbynaman16 күн бұрын
what is the need of max rows and max column simply can't I create the disjoint set of size n*m+1
@vaibhavsharmaiiitu9319 Жыл бұрын
Amazing thinking
@beinghappy9223 Жыл бұрын
Pass maxRow + maxCol +2 as size , to avoid runtime error
@kothapalliavinashkumar86992 жыл бұрын
tok sometime to understand but really helpful
@GeniuslyTensai2 жыл бұрын
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?
@NishilPatel-d2m6 ай бұрын
I didn't find the idea of treating a row as node very intuitve,
@AS-gf3ci4 күн бұрын
This is more intuitive & will take lesser space in the set. Instead of calling union on nodeRow & nodeCol, call it for rowParent & colParent for(auto &it : stones) { //Connecting different nodes to their parent to form a disjoint set component int nodeRow = it[0]; int nodeCol = it[1] + maxRow + 1; int rowParent = ds.findParent(nodeRow), colParent = ds.findParent(nodeCol); if(rowParent != colParent) ds.unionByRank(rowParent, colParent); st.insert(rowParent); st.insert(colParent); }
@WasimKhan-fd1ub2 жыл бұрын
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 ..😇😇🫂
@metalmuscles0711 ай бұрын
Striver bhai, How can someone come up with this intuition during an interview 😢😢
@iamnoob7593 Жыл бұрын
Superb vide0 ,Understood
@saurabhshakya53672 жыл бұрын
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; }
@leepakshiyadav16432 жыл бұрын
awesome explanation
@rishav1442 жыл бұрын
striver is a gem in the field of DSA/CP ...superb playlist 🔥
@HarshitMaurya2 жыл бұрын
Understood !, thanks man
@panjatushar2 жыл бұрын
Bhaiya ye graph series meye or kitne videos honge ?
@shauryatomer10585 ай бұрын
thanks for the great video
@netviz86733 ай бұрын
connected conponent mentioned DSU!!!!
@rohanlambar47256 ай бұрын
Thank you !!!
@huungryyyy5 ай бұрын
understood striver
@gouravkashyap74872 жыл бұрын
Next series??
@yashhhh80122 жыл бұрын
Understood Explanation!!
@abhishek__anand__ Жыл бұрын
Great Video
@himanshutiwari34425 ай бұрын
Pls explain the line number 74 and 75
@huungryyyy5 ай бұрын
Here we just mapped the index where the stone is actually present . doing this we are only considering the points at which stones are actually present .After which with the help of these mapped points we check the number of components by getting all the unique ultimate parents .Lets say instead of using map you would have marked everything upto maxrow+maxcol+2 as one. in this case you would have got more unique ultimate parents because here accidentally you will consider those points also where no stone is present . and obviouslly those accidental points will have themselves as the ultimate parent therefore creating more number of unique parents. Hope i was able to explain .
@rakshitpandey34811 ай бұрын
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
@k.nayaneedeepak75036 ай бұрын
Understooddddd ❤
@thaman7016 ай бұрын
Hey bro how striver is calculating maxrow and maxcol I am not able to understand it how to get it.pliz help
@thaman7016 ай бұрын
If we iterate through loop we will get maxrow=2 and maxcol=2 how is it making sense of having a dsu of 5
@herculean6748 Жыл бұрын
Thanks🙌
@visheshagrawal8676 Жыл бұрын
if anyone is getting runtime error in leetcode while running the code just update the size of disjoint set ds to maxrow + maxcol + 2