G-52. Making a Large Island - 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

[@harshkesharwani5112]

mx=max(mx,ds.size[ds.findUparent(0)]); This much code in the last section of code is sufficient to satisfy the case -> (1's at all places in grid)....and it is running safe...

[@adarshmv261]

Please clarify this doubt striver: while we do the union of all adj cells in a component why we are not maintaining a visited matrix?? Are we not doing redundant union-Ing without a visited??? Please clarify 🙏🏼🙏🏼🙏🏼🙏🏼

[@codecrafts5263]

such a great explanation for graph HARD question. I was always afraid of graph and could not even code basic graphs, but this series made me so comfortable with graphs that I was able to guess the answer to edge cases and other stuff intutively. Thanks for this striver!

[@NiranjanDandekar-sz3jw]

As usual a great explanatory video. Just a diiferent approach : instead of the last for loop, we can use conditional return where we can return max element if the graph does not have all 1s, else we can return max element in the size array as it will always be the ultimate parent.

[@yashaggarwal2949]

I was able to solve this problem on my own. Thanks to you for making the concepts crystal clear.

[@aakashgoswami2356]

Khao bhagwan kasam.

[@abhisheknag1929]

@@aakashgoswami2356 bro there are many genius people who solves much much higher level questions Check one time codeforces accounts you will get to know

[@satendra6200]

@@aakashgoswami2356 🤣🤣

[@mohanmanis]

Awesome 👏 solution but a nitpick, for the case where every cell has value as 1 and we have a large component then instead of looping through each cell and looking for size of parent. Instead, We can just return the number of cells. It is just to save some time. There won’t be any impact on time complexity. int mx = -1; //initialise return mx == -1 ? n * n : mx; //at last check,

[@muditkhanna8164]

or we can return the size of the ultimate parent of any node because if all are 1s the ultimate parent will have that size, no need to loop.

[@siddhantmishra4944]

@@muditkhanna8164 True.

[@priyanshkumar17]

Thanks for this comment. I also returned n * n, if mx was still -1

[@adarshnegi4785]

Thanks Bro

[@AyushKumar-uu8vc]

this is what called quality content...loved this!

[@shriyanshjain4444]

I solved Max Area of Island on leetcode using DSU in 10 minutes by myself. Thank You so much for the free resources Raj bhaiya!

[@krishnananddubey2870]

For the case where every cell has value as 1 and we have a large component then instead of looping through each cell and looking for size of parent we can simply find size of 0th element it will give same answer as its connected to all. Just a suggestion :)

[@rishavsingh5568]

Indeed

[@iamnoob7593]

Indeed

[@prakharpandey7745]

Indeed

[@anchitbhushan6172]

We can straight away say that the largest component size is n*n if there are no 0s.

[@yashveersingh1435]

Indeed

[@DivineVision201]

I am truly a fan of your teaching Style. lots of thanks for all your efforts. You are doing amazing! Thanks for the content 💌

[@dummydum-ih4mt]

Solved it myself !!!! Had this amazing feeling coming up with this solution !.

[@shubhanshugupta9754]

thanks striver, I was not able to figure out the edge case

[@sannareddymonesh7598]

Instead of adding all the components and calculating their sizes afterwards we can just check whether we have seen this component already or not using unordered set and if not seen then we can increase the size.

[@netviz8673]

exactly to do that we are using the set. How else are you going to know the visited components? You check that by finding the ultimate parent of the adjacent node. Once you find that ultimate parent lets say it is 5 how will you know that 5 has already been counted or not? You can do so by putting 5 in the set. Or the other method can be to just collect all the ultimate parents and have that many variables or array that could act like a hash and in those variables or array you could mark if that ultimate parent was visited or not.

[@souvik33and37]

so glad i coded this by myself after the explanation, thanks striver :) thanks for existing

[@KeerthiReddyKolan]

Greattttt Explanation!!! You brain works on a different level I assume. Thank you for the video

[@raghavmanish24]

understood .....very close to finish .....thanku striver

[@amanrazz2091]

for the case where all cells are 1 , instead of the last n*n loop to find the maxsize we can simply return max(ans,ds.size[0]) ; The intuition begin here is that even there exists even a single cell marked with 0, then our optimal answer would be in our ans variable and if there exists no cells with 0 then it means our first cell that 0,0 is also a part of the maximum size connected componenet;

[@nikhilkoushik9083]

15:50 Excellent logic bro🙌🙌🙌

[@AbhishekPandey-dj2eo]

One of the best explaination by striver ❤

[@stith_pragya]

Thank You So Much for this wonderful video..............🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻🙏🏻

[@lakeemangal]

Bhaiya hmko yha third for loop ki jrurt ni pdti because ham second bale loop mai 0 se jo connected uska max le lia hai. but suppose ki array mai koi 0 ni hoga to max milega ni mean saare array mai 1 aur sbhi 1 ko hmne first loop mai connected kr dia to ham directly max ko ans=max(ans,ds.size.get(0)) krke return kr skte hai. And it is working fine for me. Thank you

[@kishoregowda8210]

For the edge case where all the cells are already 1, we dont need the last for loop. we can simply return the size of 0th element. code snippet below. return result == 0 ? graph.size[graph.findBy(0)] : result;

[@uavishal777]

understood bhaiya....How can a person so much clarity ..You are a legend🔥🔥🔥🔥🔥

[@navinsaikaarthik3790]

we can use a count variable inside any of the two for loops, and can get the count of no.of one's or zeroes, in the matrix. If the count of zeroes is 0. Then we can return n*n. Or if the count of one's equals to n*n, then we can return n*n. Hence, we can skip the last for loop.

[@piyushacharya7696]

Niceeee!😎😎

[@ayushjain386]

You teach in a way. I am able to solve this question by myself. Thank you

[@vishious14]

Thanks a lot for the previous lectures striver. I was able to solve this on my own. My approach is totally like yours

[@santoshb7776]

Bro, can't we use just a simple DFS algo for this problem ?

[@vishious14]

Dfs works but you'll get a lot of complications in the code and a possible TLE.

[@psurya3053]

thankyou sir , you are simply amazing . Your enthusiasim and passion for this subject is phenomenal . god bless u.

[@cinime]

Understood! So wonderful explanation as always, thank you very much!!

[@beinghappy9223]

One of the most amazing problem and explanation

[@chiragPatel22c]

bro got so excited 2:34 😅 btw I am following your dsa sheet. finished till here.

[@Chandraprakash-kx4ic]

Understood...thank you dude...lots of love

[@abhavgoel9390]

we can skip the last loop,by setting mx=INT_MIN, then while returning we can check it its still INT_MIN then return the size of matrix, else mx

[@harshwardhanpatki846]

Thank you sir for such valuable content ❤️ 🔥🙇‍♂️ Understood!

[@UECAshutoshKumar]

Thank you sir 😁

[@lucygaming9726]

Was able to code the approach where we would do union in step 2. Realized from the video, that we don't need to do it, we can just take the count. Was stuck again when the size was getting counted twice, using set was an excellent approach. Truly a challenging hard problem, where just the knowledge of Disjoint Set was not enough :)

[@ASHUTOSHMAURYA-tz9xd]

Just Awesome Bro... speechless.. best graph series ever...thanks man...

[@amansiddiqui3218]

At the end of the code, instead of running loop for n*n, alternatively we can find the size of the 0th node and can compare with mx. Thus, we can save extra n*n time complexity. mx = max(mx, dsu.size[dsu.findUltPar(0)]);

[@bumbada1]

damn cool. genius. I was also thinking something similar but yours is better

[@abhirupbasu3386]

Loved the problem.Excellent explanation

[@bvnandhan3073]

Thats some awesome contenttt Mannnn , DSA == Striver

[@udaytewary3809]

Understood bhaiya 🙏❤️

[@mohakhiphop]

At the last , instead of traversing the whole matrix like - for(int cellno = 0; cellno < n*n ; cellno++) { ans = max(ans , ds.size[ds.ultimateParent(cellno)]); } we can simply do - ans = max(ans , ds.size[ds.ultimateParent(0)]); reason : since we have connected all the 1s in the matrix , (0 is the first '1' that would exist in matrix in case of matrix of 1s) Understood 💎 gem content 💕lll

[@mohitkamal4864]

Yes I was also thinking the same

[@hrithik7354]

what I did is set ans = -1 & at the last checked if ans == -1? n*n: ans

[@madhavgaur7096]

Great Problem

[@lingasodanapalli615]

Understood Clearly

[@akshaypatade5730]

while i was solving this problem, i found out that the given code will fail for the test case 2 1 1 1 1 Code output is giving us 5 However its correct out will be 4 So, what we could in this case is that once we have iterated over the elements in the set. We will check if the current grid element i.e. grid[i][j] = 0. If yes then mx = max(mx, sizeTotal + 1). Else mx = max(mx, sizeTotal)

[@SatyamKumar-bw4vi]

Jay Jagannath...!!!! 🙏🙏 understood

[@gautamsaxena4647]

Understood bhaiya

[@sambhavagarwal5871]

striver this is showing tle here so in in the last loop we will use this mx=max(mx,ds.size[ds.findUPar(n*n-1)]); code: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=0&&adjr=0&&adjc

[@kirtisachapra9030]

Wonderful explanation!!

[@sal2054]

Great explanation! Reminds me of Minesweeper game. 4:38 🤭

[@amanbhadani8840]

what a nice question and crystal clear, whity milk like pure explanation💥

[@lakshsinghania]

wtf "whity milk" bruh sus

[@abhishekkuntare4640]

Striver you are the life saver !

[@mohakhiphop]

1 am coders gang 👩‍💻

[@saichandu8178]

for the last part, if a matrix contains all 1's, then its just enough to find `mx = max(mx, size[findUParent[0]])`

[@r_uhi05]

Or we can return n*m

[@rishabhgupta9846]

understood,great content

[@samikshyasahoo9010]

I wish one day I'll be as good as you.

[@sekhharr]

could code after your hints Thanks for this aweesome playlist

[@Rajat_maurya]

Last for loop can be replaced by mx=max(mx,ds.size[ds.findPar(n*n-1)]); small think which i observed :)

[@krishanpratap3286]

hah yes this will also work which year u bro?

[@Rajat_maurya]

@@krishanpratap3286 4th🥲

[@raunakkumar6144]

how was ur placements

[@natansh05]

Legendary 🫡🫡

[@DevanshuAugusty]

if every element in grid is 1 than we don't need to use for loop of n*n, we just need to find the size of one ultimate parent: max_size = max(max_size, ds.size[ds.findUPar(0)]);

[@lakshmand8413]

If every cell is 1 then the mx value stays zero so if its the case no need to check for every cell again right , simply return n*n that will be the size of the ultimate parent . Correct me if i am wrong :)

[@avdharna1978]

sir last loop can be replace by if(mxSize==0){ return n*n; } return mxSize;

[@The_Shubham_Soni]

Understood.

[@-VLaharika]

Understood 👍

[@learnwithayush7838]

Understaand I have fallen in love with this guy

[@abhinavbhardwaj3372]

understood sir

[@AryanMathur-gh6df]

UNDERSTOOD!!!

[@NarendraYadav-h2u]

Hey RAJ sir, just one genuine question!🥱🥱🥱🥱 When you solve a problem for the first time in your life, how do you get this kind of intuition or logic?

[@vaibhavsoni2437]

If all the cells contains 1, then all the cells will get connected (unionBySize) and make 0 the ultimate parent. Hence, size[0] will be the maximum if all cells contain 1.

[@vishnubanjara5209]

hey striver i saw that if i declare setst outside of those loops than code is not working and if i declare set inside for loops than it runs fine why it is happening .... plz reply

[@mriduljain6809]

Understood😊😊

[@MMNayem-dq4kd]

understood.

[@bhavya8608]

awesome explanationss!!

[@AdityaKumar-be7hx]

Understood!

[@suryakiran2970]

Understood❤

[@zaiem6981]

If every cell is one than there will be only one ultimate parent. we can just return ds.size[0], or size of any other index.

[@pulkitchausali1354]

able to code myself #thanks striver for this wonderful series😇

[@rounaq_khandelwal]

Love you Striver!

[@hiteshnagothu887]

Understood. Got tips to make the code work in one go?

[@chandrachurmukherjeejucse5816]

Understood!!

[@dolbyagarwal9316]

Hey Striver, thanks for the videos. Can you please ask GFG to include Python language as well for these questions. For some I only see C and java.

[@adarshmv261]

Please clarify this doubt striver: while we do the union of all adj cells in a component why we are not maintaining a visited matrix?? Are we not doing redundant union-Ing without a visited??? Please clarify

[@gangsta_coder_12]

Understood 🔥🔥

[@manishpawar5918]

Understood

[@tirthpatel4498]

wonderfull explanation ever hats off 🫡🔥🔥

[@akashsahu2571]

thaks

[@pratyakshhhhhhhhhhhhhhhhhhhhh]

In the last point when you run the loop through all cells saying on the basis of 'what if the Matrix contains all ones'. Why we are doing that? We just had to compare it with the size of the parent of the cell 0. Am I right?

[@adebisisheriff159]

Thanks striver!!!

[@ACUCSPRADEEPB-up9ne]

Understood ✌️

[@tirthdoshi1337]

Great video !

[@anshulgoel1940]

Instead of converting row and columns to their respective index and then use it in parent array, can't we define two parent arrays one for row and one for column. This will increase space complexity from O(NXN) to O(2*NXN) but simplify the comparisons. Just a thought.

[@sunilpanchal1498]

Understood 🤩

[@netviz8673]

attention here again: Graph is changing dynamically hence always think of Disjoint Set

[@herculean6748]

Thanks🙌

[@iamnoob7593]

superb

[@rishabhraj8233]

striver makes tough concepts easy

[@nishantdehariya5769]

very nice

[@saseerak8763]

understood!

[@Aryan-vw7lt]

understoooddd

[@akarshpandey5721]

In the last step, where we are checking for the case when all grid values are 1, we can directly do it by if(mx==0) // means no 0 encountered in the grid { mx= n*n; // bcz in that case, the maximum size will always be the total number of nodes in the grid i.e. n*n } return mx;

[@anchitbhushan6172]

Nice Observation

[@roshankumarshah4032]

understood

[@adityasaxena6971]

Understood Striver

[@r_uhi05]

Understood striver