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!

[@hwp438]

holy shit. I was able to solve this problem without looking at any solutions and videos. Still watching this to see your approach. I would like to thank you for videos, they are wonderful.

[@SahilVanarse-n4x]

Onething I learned from him is writing a clean code with perfection and no errors

[@souvik33and37]

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

[@yashshukla1637]

Set for Deduplication: Use set to avoid counting duplicate components in adjacent cells. Path Compression: Always compress paths in DSU to keep operations efficient. Union by Size: Merge smaller components into larger ones to optimize DSU further. Handling 4 Directions: Use pre-defined direction arrays for adjacency checks in 2D grids. Example: python Copy code directions = [(0, 1), (1, 0), (0, -1), (-1, 0)] # Right, Down, Left, Up Grid Dimensions in Formulas: Understand how rows and columns translate to indices for efficient computations.

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

[@AyushKumar-uu8vc]

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

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

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

[@shubhanshugupta9754]

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

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

[@imPriyansh77]

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

[@adarshnegi4785]

Thanks Bro

[@nikhilkoushik9083]

15:50 Excellent logic bro🙌🙌🙌

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

[@stith_pragya]

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

[@chiragPatel22c]

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

[@dummydum-ih4mt]

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

[@_Dream_Dive_]

Solving a Hard question without any help was not possible before him.

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

[@KeerthiReddyKolan]

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

[@cinime]

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

[@ayushjain386]

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

[@sal2054]

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

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

[@raghavmanish24]

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

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

[@AbhishekPandey-dj2eo]

One of the best explaination by striver ❤

[@UECAshutoshKumar]

Thank you sir 😁

[@bvnandhan3073]

Thats some awesome contenttt Mannnn , DSA == 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;

[@beinghappy9223]

One of the most amazing problem and explanation

[@Chandraprakash-kx4ic]

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

[@psurya3053]

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

[@uavishal777]

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

[@abhirupbasu3386]

Loved the problem.Excellent explanation

[@ByteBattle123]

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

[@kirtisachapra9030]

Wonderful explanation!!

[@ASHUTOSHMAURYA-tz9xd]

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

[@avdharna1978]

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

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

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

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

[@rishabhgupta9846]

understood,great content

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

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

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

[@SatyamKumar-bw4vi]

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

[@bhavya8608]

awesome explanationss!!

[@hiteshnagothu887]

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

[@madhavgaur7096]

Great Problem

[@sahilgupta1225]

class Solution: def dfs(self, row, col, grid, del_row, del_col, n): cnt = 1 for i in range(4): nrow = row + del_row[i] ncol = col + del_col[i] if 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 :)

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

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

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

[@amanbhadani8840]

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

[@lakshsinghania]

wtf "whity milk" bruh sus

[@tirthdoshi1337]

Great video !

[@rounaq_khandelwal]

Love you Striver!

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

[@abhishekkuntare4640]

Striver you are the life saver !

[@mohakhiphop]

1 am coders gang 👩‍💻

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

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

[@pulkitchausali1354]

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

[@samikshyasahoo9010]

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

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

[@udaytewary3809]

Understood bhaiya 🙏❤️

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

[@knowledge-n9z1w]

What to do if he says we can flip atmost k cells for this problem .. Any suggestions ?

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

[@santoshb7776]

Can't we just use a simple DFS algo to calculate ?

[@sekhharr]

could code after your hints Thanks for this aweesome playlist

[@adebisisheriff159]

Thanks striver!!!

[@im_ykp]

Can't we add the parent in the set

[@lingasodanapalli615]

Understood Clearly

[@dailydestress6189]

Can anyone explain Why is the loop necessary at line 110 ?

[@uavishal777]

is this question on Leetcode?

[@natansh05]

Legendary 🫡🫡

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

[@AryanMathur-gh6df]

UNDERSTOOD!!!

[@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)]);

[@anuragbadli123]

i have a doubt in line 99 when i use components.insert(ds.par[newr*n+newc]) instead of components.insert(ds.findUpar(newr*n + newc)) i am getting wrong ans but why ..?

[@kushagragupta149]

bcz size is stored in ultimate parent thats why we save the ultimate parent of a island(the group of connected ones)

[@-VLaharika]

Understood 👍

[@gangsta_coder_12]

Understood 🔥🔥

[@gautamsaxena4647]

Understood bhaiya

[@harshtripathi2287]

Hey Striver, Great Explaination although I am having a doubt... I tried to code it up myself and while inserting into set i used something like components.insert(ds.parent[adjNode)); which gave me a wrong answer. I am not sure why this happened..

[@deepakkumarthakur9665]

components.insert( ds.findUPar(adjNode)); this may help

[@visheshagrawal8676]

same bro ds.findUpar is working but why ds.parent is not working as initially we have join the nodes by ds.unionbysize and it should have updated there parents to findUpar but few test cases failed in this

[@pj-nz6nm]

@@visheshagrawal8676 when you call findparent() it will compress the path and would give root node but if u do this parent[adjnode] u will get the immediate parent not the final parent;

[@learnwithayush7838]

Understaand I have fallen in love with this guy

[@herculean6748]

Thanks🙌

[@mriduljain6809]

Understood😊😊

[@RenukagangaDevakoti]

Thank you sir

[@suryakiran2970]

Understood❤

[@sg627k]

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.

[@tirthpatel4498]

wonderfull explanation ever hats off 🫡🔥🔥

[@subratkumar7359]

Can anyone help me with line no 97. components.insert(ds.findUPar(new * n + newc); Here we are finding the ultimate parent of that adjNode using parent function... but can it be done like this components.insert(ds.parent[new * n + newc]) as we have already stored the ultimate parent of every node during the step 1 ??

[@rohanpatil8417]

Yes you can.

[@subratkumar7359]

@@rohanpatil8417 well I wrote the same line in leetcode and got it incorrect.

[@visheshagrawal8676]

I also got incorrect if someone get the answer please tell me hey striver if you read this comment do tell us this is the most common doubt

[@MrAkshay2711]

Quick question...but first great explanation HATSS OFF. My question being how are we seeing if the cell as previously visited or not. Since we are perfoming 4 dirs movement for every cell but I am not able to understand how are we not confirming of not visited the same cell again.

[@krishanpratap3286]

set is ensuring that

[@MrAkshay2711]

@@krishanpratap3286 No bro. I am talking about the inital for the first for loop in which we are moving in all four dirs. How are we making sure that the previosuly visited cell is not visited again

[@krishanpratap3286]

@@MrAkshay2711 ds main dall rahe nah toh visited ka matlab hoga already ds main hoga toh usse if statement main ignore kar denge

[@krishanpratap3286]

Like jab ds main union karenge and same parent aayega toh auto return kar jayega woh

[@MrAkshay2711]

@@krishanpratap3286 ok ok got it thanks

[@pawandeepchor89]

Hey great video !! Just one question can't we avoid the last n*n loop by just doing maxSize = max(maxSize, uf.size[uf.getParent(0)])? i.e. if all are ones in grid

[@deviprasad_bal]

yeah, it works

[@raunakkumar6144]

Yeah I was also thinking the same.

[@sunilpanchal1498]

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.

[@pulkitsinghchouhan5207]

Striver 6 new videos on dsu are awesome and it helped in understanding of the concept very well. Pls make videos on how to use kruskal and prism algorithm to solve problems on gfg and leetcode.

[@paritoshkumar5005]

yes @striver please do this it will be of big help

[@ACUCSPRADEEPB-up9ne]

Understood ✌️