Google Coding Interview Question and Answer - Most Stones Removed with Same Row or Column [LeetCode]

[@vinceluu]

Found your channel during my leetcode prep for interviews, super concise and clear explanations! Please keep uploading solutions!

[@ShiranAfergan]

Thanks Vince! I’m working on a new one. Hopefully will be up in a week or so.

[@cs_soldier5292]

Best channel to learn how to solve questions in competitive coding systematically.

[@sahiljain2524]

Crazy Insaan!! you are great.
The way you solve and boil down to a simple formula and make the question so so easy is so insan now i am fan of your hats off to you skills

[@manokumar89]

Thanks for an amazing explanation.
1. when you showed how the first example will work in a grid by removing the stones from 1.12 onwards, you are removing in the same order as if you remove the leaves from its spanning tree. how to actually go there? if we remove randomly matching stones, it wont end up with just 1 stone.
2. why the worst case complexity of naive solution is O(n2logn) if the amortized complexity of union-find is a constant: shouldn't the complexity be O(n2)?
3. what is the complexity of the final solution?

[@ashishkumarshrivastava2257]

Amazing explanation. The diagram you used to explain made it really simple to understand.

[@ShiranAfergan]

Thanks! I’m glad it helped :)

[@deathstrokebrucewayne]

Your Explanations are just so great - To the point - No beating around the bush and extremely helpful. But you stopped making videos :(
More power to you and may we find more such videos
Admiration from India

[@ShiranAfergan]

Thanks Aadarsh! I didn’t stop, I’ve been extra busy lately but will post more soon :)

[@awfulprogrammer619]

I hope you are doing well. This is so great explanation! Keep Uploading and keep Shining!

[@jaideeppyne1880]

@Shiran Afergan There is so much clarity in your explanation! Superb.

[@ShiranAfergan]

Thanks Jaideep! I’m glad you enjoyed it :)

[@jaideeppyne1880]

Cheers from India. Looking forward to more such awesome content.

[@Vishal_ingole]

The way of explanation with visual effects is too good, Thanks for the video 😊

[@AnshulSharma-gq2vn]

Very well explained Shiran!! Kudos!

[@venkateshng2010]

I really enjoyed your explanation and the clean code you write, I am prepping for google interview next week, your channel came to me at the right time via leetcode discuss forum :) please keep making more videos

[@ShiranAfergan]

Working on it :) best of luck with your interview! 💪🏽

[@shaydratler4777]

You are very Fluent and like the visualization Thanks for the hard work

[@ShiranAfergan]

Thanks 😊 glad you enjoyed it!

[@senthilpalanisamy151]

These videos deserve more views!

[@ShiranAfergan]

Thanks Senthil :)

[@satviksharma4897]

Oh lord how I have struggled with this problem, where have you been

[@ShiranAfergan]

Haha glad it helped :)

[@choicespecss]

Thank you for your videos and content stumbled across this video looking for union find solution to this problem. I hope you continue to upload videos and content!

[@domod481]

Great explanation !! I really liked the way you explain the problem from scratch : ) Subscribed...

[@ShiranAfergan]

Thank you 🙏🏽:)

[@beksultanomirzak9803]

Astonish! thanks for your hard work

[@akashkirthik9882]

Amazing explanation ! Please keep making videos !

[@ShiranAfergan]

Thank you 😊 I’m working on it :)

[@oknd6564]

Explanation is really awesome.

[@ShiranAfergan]

Thank you 🙏🏽 😊

[@akshaygoyal2134]

Elegant solution. You have got a new subscriber :)

[@ShiranAfergan]

Thanks Akshay! I’m glad you liked it :)

[@nipunshah1373]

Splendid Explanation !

[@mlishka]

Hey .. awesome explanation. Subscribed for easy explanation. Keep up the good work. Can you please do a videos on problem : region cut by slashes.

[@domod481]

I am also looking for solution of this problem.

[@ShiranAfergan]

Thank you! Since it is also a union find question, it might take some time (i wanna do some tree, graph and recursion questions first) but seems interesting, thanks! ☺️

[@karanjkarnikhil4]

What an amazing explanation !!!!

[@ShiranAfergan]

🙏🏽🙂

[@chintamalli695]

Awesome plz continue series with Google questions

[@ShiranAfergan]

Thanks! I will :)

[@ujjwalchopra2880]

awesome explanation thank you.. keep making videos

[@ShiranAfergan]

Thanks:)

[@aditya234567]

OMG ur very good at explaining

[@ShiranAfergan]

Thank you! I’m glad you liked it :)

[@musicperson94z]

Awesome video. How can you be so good at this? Keep posting please.

[@ShiranAfergan]

Thanks Jiadong! You just need to practice :)

[@eg7eg7]

Loved your explanation! thanks

[@Victoria-dk2jm]

Perfect explanantion !!

[@ShiranAfergan]

Thanks :)

[@codingwithanonymous890]

Explained so well.

[@adityajagtap4349]

I have been going through all you videos in the list . Thanks for sharing all the knowledge .
I couldn't understand how groups were created inside a constructor of union find , like in example 6 groups are created upfront . I understand union like maintain parent as : (item index , parent value) . But couldn't really visualize when item itself is combination of two numbers.

[@adityajagtap4349]

But I got it now , item is row and column individually and instead of indexing with array which we have generally use , we have a map also we don't care about stone but only its cordinates . Being from java background parent[col] gave me feeling of index instead of keys .

[@ShiranAfergan]

I can see why it’s confusing:) I now code in Java in my job and I keep trying to use [] with maps and don’t understand why it’s not working 🙃

[@chris.w391]

Thank you! Well explained.

[@adityamishra4458]

It was superb ..... can you suggest how to come up with such way of solving how you thought of this problem. Can you suggest some good resources to study for interviews

[@ShiranAfergan]

Thanks Aditya! I plan on doing a video with tips on how to approach such problems and maybe a series on data structures and common algorithms.
For practicing I recommend LeetCode and GeeksforGeeks.

[@manokumar89]

@@ShiranAfergan +1

[@ishaankulkarni49]

great explanation! :)

[@ShiranAfergan]

Thanks :)

[@parthghosh1343]

thank you, great explanation

[@interviewprep4181]

Really nice explanation

[@ShiranAfergan]

Thanks :) glad you liked it.

[@akashgupta6711]

Awesome explanation !! Can you please tell what is the drawing tool that you use ? I was thinking of using some kind of drawing tool for my virtual interviews.

[@ShiranAfergan]

It’s an iPad pro with GoodNotes

[@akashingole]

Hi, why have you added 1 to row and column.

[@deepusasidharan2012]

Good explanation

[@ShiranAfergan]

Thanks 😊

[@ritwik121]

can you make a video on this leetcode.com/problems/accounts-merge/ and can you more graph problems like this video. this video was very good. thanks

[@ShiranAfergan]

Thanks Ritwik! I like your suggestion, i will add this question to my list. I think the next one is going to be “robot room cleaner”. Hope you enjoy it :)

[@ritwik121]

@@ShiranAfergan thanks a lot

[@mudrad1930]

It really helped ! Thanks a lot

[@ShiranAfergan]

You’re welcome :)

[@nipunshah1373]

Why rank was not updated during merging in rest 2 conditions ?

[@javierfuentes3603]

great explanation

[@ShiranAfergan]

Thanks Javier!

[@DharmendraYadav-sf4ti]

Nice Explanation

[@ShiranAfergan]

Thanks :)

[@DharmendraYadav-sf4ti]

Welcome!!

[@amanverma7375]

I am unable to understand what does count variable stores initially, can we do count = stones. size(); as well

[@harshk3351]

count will store the number of groups we have intially
No, you can not do count = stones. size() this will be wrong
just think over this example: [ [0, 0], [1,1], [2,2] ]
here:
count = stones. size() = 3 [WRONG]
count = parent.size() = 6 [row0, col0, row1, col1 like that] [ CORRECT]

[@akashjaiswal6478]

amazing explanation, thanks a lot, I have a doubt- when rank[xset]

[@ShiranAfergan]

Thanks:) it’s not an error because you only care about the rank of the root (the representative of the set) and yset is now under xset so we only need to update the rank of xset

[@eg7eg7]

Watched that video again, and I was about to comment when I saw that I already did a year ago haha :P

[@ShiranAfergan]

Haha hope you enjoyed it the second time as well 😄

[@eg7eg7]

@@ShiranAfergan I did for sure :)

[@tom3983]

amazing! thank you

[@ShiranAfergan]

I’m glad you liked it :) thanks for watching.

[@jethala138]

You are beautiful ;) Btw Thanks for the explanation😊

[@ShiranAfergan]

Thanks and you’re welcome :) glad it helped

[@akshaykhanna4295]

So max stones that can be removed = Total stones - no of connected components

[@ShiranAfergan]

Yup

[@tsonnguyen]

ur the best

[@letslive3782]

How do you even get those ideas ? I could have never thought of this problem in this manner.

[@ShiranAfergan]

Yes, it is a difficult question. The idea is to try reducing the problem to something familiar. In this case - number of connected components in a graph.

[@letslive3782]

@@ShiranAfergan Thank your very much, Shiran !!

[@ramanmanocha4800]

That's smart!!

[@pwnweb5734]

Perfect. perfeect perfect peerrrfect

[@ShiranAfergan]

Glad you liked it 😆😊

[@yash_______105]

@@ShiranAfergan can u plz plz increase frequency of uploading videos

[@garrettguitar6583]

union find? Amortzed what? Too difficult . I m not smart enough for this. Too hard. Where can I find a simple explanation of this ?

[@ShiranAfergan]

Yes, it’s a difficult question.
If you want to read up on union-find (Disjoint-set) data structure you can find a pretty detailed explanation on Wikipedia (en.wikipedia.org/wiki/Disjoint-set_data_structure ).
You can also check out this Union-Find playlist from William Fiset ruclips.net/p/PLDV1Zeh2NRsBI1C-mR6ZhHTyfoEJWlxvq

[@shivamrai7838]

thankuhh :) -/\-

[@praburajiiv]

i came up with solution within 3 min of this video. good at explaining different test cases. curious to know your instagram id 😍

[@ShiranAfergan]

Awesome :) thanks for watching. I don’t have an active instagram account.

[@eVOLUC]

babe

[@shashanksinha6966]

great explanation

[@ShiranAfergan]

Thank you :)