G-53. Most Stones Removed with Same Row or Column - DSU

[@takeUforward]

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

[@rohitn6333]

Thanks a lot for this wonderful playlist sir. May i know how many videos are left in this series sir?

[@SatyamEdits]

Bhaiya your CP sheet is very difficult.....even easy questions are difficult....

[@rishav144]

@@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

[@ankusharora5551]

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

[@sayantaniguha8519]

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.

[@rahulsangvikar7973]

@@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.

[@adwaitmhatre7561]

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.

[@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

[@tejassankhla1264]

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?

[@agrawalmitesh4395]

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(); } }

[@nagatanujabathena6319]

Understood! THE BEST Graph series ever! Thanks a lot for this!

[@AlokSingh-jw8fr]

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.

[@saseerak8763]

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

[@saseerak8763]

//{ 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

[@cr7johnChan]

@@saseerak8763 thanks

[@sayankabir9472]

oh my god thanks so much. i was wondering what's the problem for so long

[@AkshatTambi]

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

[@kunalkhallar9699]

I did the same damn thing 😅

[@shreyarawatvlogs6920]

cant believe that i've come so far in graph series. Kind of proud of myself now!

[@Rajat_maurya]

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

[@divyareddy7622]

BHAIYA YOU ARE SINGLE HANDELY HELPING ALL OF US, no one really does this, please keep going in life and thank you vvvv much!

[@tousifjaved3485]

How many videos remaining vai? This is the best graph series so far😁

[@gsmdfaheem]

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..

[@devanshsingh2]

Proud of u fam.

[@FooBar-lb5wf]

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.

[@techtoys-tx9th]

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 🔥

[@we_crood]

if someone had told that i solve without watching this video I would have quit coding

[@dhruvnagill9391]

I did it without watching the video. But my solution took n^2 TC

[@shauryatomer1058]

@@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

[@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

[@kunalchaudhary2808]

Question becomes easy after watching your videos.🙌

[@deepanshuthakur140]

When i start thinking that now i can tackle questions as you do, you just amaze me up with something extraordinary.... Superb explanation

[@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_Yashika]

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

[@divyareddy7622]

UNDERSTOOOOD BHAIYA PLEASE CONTINUE

[@priyapandey8951]

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

[@anshulagarwal6682]

Bhaiya please make video on Convex Hull algorithm and concepts like dp on trees and Heavy Light Decomposition.

[@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; } };

[@nitinkumar5974]

Bhai 1 million karwao bhai ke jaldi se hamare liye itna kuch kar rahe hai bhaiya

[@codingvibesofficial]

You are a legend💕❤️ Thanks bhaiya for using English so that everyone could understood u

[@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.

[@hamzaarif6945]

*unordered_set* can be used instead of *unordered_map*

[@stith_pragya]

very well done, Thanks a ton for the help.........🙏🏻🙏🏻🙏🏻

[@mohdkhaleeq7468]

great writing codes without any errors thats the reason you are Software engineer at Google Hope one day i will be like you

[@huungryyyy]

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. 😊😊😊😊

[@pacomarmolejo3492]

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.

[@anjalitiwari486]

Hi. Can you share the code for this logic?

[@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.

[@KittyMaheshwari]

Thanks bhai for everything. We're with you

[@rupeshjha4717]

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.

[@pogpieunited3379]

I solved it using bfs wont say unsolvable but yeah definitely a bit hard

[@utkarshpal9377]

damn , wtf, ultimate approach striver, Just amazing , how to even think of this 🤯

[@utkarshpal9377]

is it something we regulary use , in soft engg or what? just curious

[@stith_pragya]

understood, Thanks a lot...........🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@gautamgupta7148]

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)

[@getgoin2217]

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

[@UECAshutoshKumar]

Thank you sir 🙏

[@oqant0424]

what an explanation 🔥....literally!!!!!!!!!!!!!!!

[@abhirupray2494]

Great approach and explanation.

[@iamnoob7593]

Hashmap is not required striver sir , We can just use parent[] and size[] to count the no of connected components.

[@japneetsingh3306]

get well soon bhaiya

[@kr_ankit123]

The idea of resolving rows and cols and connecting them is absolutely amazing. ♨♨♨♨

[@ece_a-65_parthbhalerao8]

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 ??

[@karanveersingh5535]

9 more

[@ece_a-65_parthbhalerao8]

@@karanveersingh5535 how do you know bro ?

[@stephen9726]

@@ece_a-65_parthbhalerao8 Check Striver's A2Z Sheet

[@harshkanani6605]

what an explanation striver

[@swetakumari7305]

How to think of this in an interview 🤯

[@kothapalliavinashkumar8699]

tok sometime to understand but really helpful

[@WasimKhan-fd1ub]

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 ..😇😇🫂

[@adarshmv261]

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!!

[@JohnWick-oj6bw]

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

[@cinime]

Understood! Super amazing explanation as always, thank you very much!!

[@Now_I_am_all_fired_up]

Hey Striver Plz Make a vedio on Vertex Clover Problem Two Clique Problem Minimum Cash Flow

[@naveensingh4763]

U were right bro👍

[@rishav144]

striver is a gem in the field of DSA/CP ...superb playlist 🔥

[@r_uhi05]

Understood!! Great explanation

[@techatnyc7320]

Thanks Striver

[@beinghappy9223]

Pass maxRow + maxCol +2 as size , to avoid runtime error

[@xhortsclub]

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 .

[@huungryyyy]

understood striver

[@vaibhavsharmaiiitu9319]

Amazing thinking

[@netviz8673]

connected conponent mentioned DSU!!!!

[@mriduljain6809]

Understood!! Another approach using DFS: void dfs(int ind,vector& stones,vector& vis) { vis[ind]=1; for(int i=0;i

[@GyaanGrave]

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.

[@stephen9726]

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.

[@kinshuk1743]

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.

[@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

[@iamnoob7593]

Superb vide0 ,Understood

[@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

[@Rajat_maurya]

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) ?

[@rishabhgupta9846]

yes (maxRow+1+maxCol+1)

[@JavidIqbal7]

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

[@leepakshiyadav1643]

awesome explanation

[@judgebot7353]

understood thanks bhaiya

[@gautamsaxena4647]

understood bhaiya

[@shauryatomer1058]

thanks for the great video

[@yashhhh8012]

Understood Explanation!!

[@metalmuscles07]

Striver bhai, How can someone come up with this intuition during an interview 😢😢

[@NishilPatel-d2m]

I didn't find the idea of treating a row as node very intuitve,

[@notsodope7227]

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?

[@adityakhare2492]

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

[@HarshitMaurya]

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;

[@notsodope7227]

@@adityakhare2492 Thanks bhai. Makes sense!

[@shivangmathur6112]

@@adityakhare2492 thanks bro I was also looking for this answer since last 2 days

[@gangsta_coder_12]

Understood 🔥🔥

[@viralshah316]

got the approach but couldnt get how to connect them as dsu

[@dhirenparekh2646]

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

[@mayanksaurabhmayanksaurabh9271]

@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.

[@ratneshagarwal1086]

At time 2 remove matrix 4x3 . Remove 0 0, 3 2, 4 3. Only 3 sholud be answer i think

[@ManishSingh-ll4ws]

Good to know arnub goswami , inspired your speaking skills 😃

[@vishious14]

I tried solving this on my own without actually counting the number of components and this is my working approach. class Solution { public int removeStones(int[][] stones) { int n = stones.length; DisjointSet ds = new DisjointSet(n); for(int i=0;i

[@rohanlambar4725]

Thank you !!!

[@rakshitpandey348]

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

[@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

[@manasranjanmahapatra3729]

Understood.

[@tusharmishra8190]

How many **MORE** videos will be uploaded for GRAPH Series?

[@AryanMathur-gh6df]

UNDERSTOOD

[@sukhpreetsingh5200]

Understood

[@GeniuslyTensai]

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?

[@abhishek__anand__]

Great Video

[@gouravkashyap7487]

Next series??

[@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.

[@herculean6748]

Thanks🙌

[@HarshitMaurya]

Understood !, thanks man

[@abhinavbhardwaj3372]

understood sir

[@k.nayaneedeepak7503]

Understooddddd ❤

[@thaman701]

Hey bro how striver is calculating maxrow and maxcol I am not able to understand it how to get it.pliz help

[@thaman701]

If we iterate through loop we will get maxrow=2 and maxcol=2 how is it making sense of having a dsu of 5