Technical Interview Question: Number of Islands [LeetCode]

[@pogostemoncablin4507]

I can't thank you enough, you are a great teacher. I am learning graphs from you and I'm getting over my fear of graphs because of you.

[@usmanh770]

I just went through all the big youtubers who explained this, and you explained it the best, yet you have the least subscribers - please, I urge you to keep going, you'll gain traction soon, really great quality stuff, good job!

[@AlgosWithMichael]

Thank you so much, I really appreciate that!

[@asgm1382]

I second this.

[@MohammadSalman-zq2rv]

By far the best mentor

[@koredyte]

Best video on this topic. I particularly like the 'sink' analogy, and also the fact you took the time to explain the problem in detail first!

[@AlgosWithMichael]

Thank you so much, more videos to come!

[@robertsedgewick1266]

Many explanations on youtube for this question, but this is by far the clearest! The specific naming of changeLandToWater( ) makes it so much clearer compared to dfs( )

[@AlgosWithMichael]

Thank you very much!

[@panzabamboo1901]

Best vid I have seen on this, thanks!

[@AlgosWithMichael]

thank you

[@majetyprashanth1590]

Never understood this problem's solution this clearly ! You've explained every single small step in detail .. I'm really glad to have found your channel ! Keep going !!! ^_^ At the end, I was like this problem is so easy and I could not believe that the solution was so easy using recursion. All thanks to you brother :)

[@AlgosWithMichael]

Awesome to hear! Thanks for watching

[@dimejifaluyi1759]

Really great explanation. By 4:31 I knew where you were going and had that 'Ah ha' moment and was able to implement it from there on. Thanks!

[@AlgosWithMichael]

nice, thanks for watching

[@Dragondavid]

Man you finally made me to understand recursion!!!!!!!! my hero!!

[@AlgosWithMichael]

that is exactly what i wanted :)

[@lylez00]

I've been interviewing lately, and I'm not encountering any of these "common questions" I'm seeing on KZbin. They're all different, and they're all hard. My question today - just the question and the examples of solutions was 63 lines, and I had about 20 minutes to solve it. I am so sick of the IT industry!

[@2412Anand]

Hey Michael, Thank you for this amazing playlist. As I see the maximum questions in the playlist is consist of DFS. Can you make some set of questions where we need to apply BFS and show us how to apply?

[@Ryan-fe2du]

Best explanation I have seen. Thanks!

[@AlgosWithMichael]

Thank you, I appreciate the kind words!

[@90krishika]

Best explanation on this topic! Loved it (y)

[@AlgosWithMichael]

glad to hear!

[@anpascally]

Great video, great explanation. Thank you so much.

[@AlgosWithMichael]

of course, thank you for watching

[@soumilmishracomp]

The video is really helpful. Keep up the good work and I request you to please draft some more similar videos for other leetcode problems.

[@AlgosWithMichael]

Most definitely! Thank you for watching!

[@shihaojin5338]

very clear and helpful. Thanks

[@AlgosWithMichael]

No problem, thanks for watching! Check out some of my newer graph related videos if you like this one, I've tried to improve the quality of the videos!

[@tetianao376]

such a great explanation!

[@AlgosWithMichael]

awesome!

[@RedionXhepa]

Really nice content !

[@AlgosWithMichael]

Thanks!

[@johnkim7783]

This is a really good explanation! Great job doing in !

[@AlgosWithMichael]

anytime :)

[@snigdhapurohit4216]

Thank you so much for explaining this problem so well. :)

[@AlgosWithMichael]

anytime

[@DanielVazquez]

Good explanation, just a tiny detail: you just missed to change the firsts "ones" occurrences to zeros in the graphic explanation.

[@kinjalthehero]

Thank you for the clear explanation.

[@AlgosWithMichael]

No problem!

[@pavanomanwar1389]

Very easy and clear explanation!!

[@AlgosWithMichael]

awesome to hear

[@KazuhiroOinuma]

So easy to understand!

[@AlgosWithMichael]

Glad to hear :)

[@dustinv9193]

Great video. Thanks for your clear explanation.

[@AlgosWithMichael]

of course!

[@ravikumarnarayanan5876]

Awesome, just made me understand this in one shot.

[@AlgosWithMichael]

glad to hear

[@jeffge8009]

very clear explanation! thanks

[@AlgosWithMichael]

awesome, thanks for watching

[@ShashwataSaha]

For the same algo it's saying maxing recursion depth excided, In pythn

[@KnowledgeAmplifier1]

Very nice explanation ... Clear idea:-)

[@AlgosWithMichael]

Nice, thanks for watching!

[@jingjing6813]

very clear explanation!!!! Thanks for sharing!

[@AlgosWithMichael]

no problem

[@lylez00]

This solution modifies the input data. To avoid this, you could create a set of points and check for the presence of a point (make sure your point class overrides both hashcode and equals) in that set, or copy the input two-dimensional array.

[@mohammadn0man]

great explanation

[@AlgosWithMichael]

Thank you!

[@subhadeepbhattacharyya2867]

I am not sure if your up and down notations are correct.

[@anpascally]

Yeap. Up should be 'i-1' and Down should be 'i+1'

[@AlgosWithMichael]

Yea, I messed them up lol

[@woodylucas]

Every time you ever go over a problem I say to myself "Why did I ever struggle?"

[@AlgosWithMichael]

haha I'm glad the vids are helping!

[@khangt1k25]

Best video, it's really useful. Thanks!

[@AlgosWithMichael]

i appreciate that

[@SumitKumar-ww7he]

Excellent.

[@AlgosWithMichael]

thank you

[@vincenr8822]

Nice! You should create more videos like this but with other problems. 👍🏻

[@AlgosWithMichael]

Only 2 years late, but I have been uploading every week now :p

[@shameedify]

Up and Left recursive calls are not needed the way you are iterating in the caller.

[@karthikmoh]

Great explanation

[@AlgosWithMichael]

Thank you!

[@ramireddy8223]

Really great explanation ...

[@AlgosWithMichael]

i appreciate that

[@SameerSrinivas]

Great explanation! Could you please tell what is the run time complexity? Both space and time?

[@AlgosWithMichael]

Both the time and space will be O(M*N). Sorry for the very late reply lol

[@MrThepratik]

Awsme video Thanks a ton

[@AlgosWithMichael]

anytime

[@qaipak1]

some home slices be doing this with dem trees dough

[@AlgosWithMichael]

fuck yea

[@udaychatterjee4424]

Do we need to call the recursive function for up and left? I think calling it for down and right shoulder care of it

[@ForCodingInterview]

Yes.. Consider the below input [["1","1","1"],["0","1","0"],["1","1","1"]] If top & left are not called, it will give 2 as output. But expected output is 1

[@udaychatterjee4424]

@@ForCodingInterview ahhh. Make sense. Thanks for explaining.

[@danielzuzevich4161]

Thank you.

[@AlgosWithMichael]

No worries!

[@ArghyaBhattacharyaNITA]

what if there is 1 in the top row 3rd place from the left.. as per this algorithm it will count that as an island, but that would be wrong right..

[@DanielVazquez]

When we convert land (1) into water (0) in the recursive method, we make sure to visit every horizontal and vertical neighbor from every land cell. So, if we start at the top left position (0,0) which contains a "1" we convert it to water "0" and we immediately visit the right (0,1) and bottom (1,0) cells recursively. First, we we visit (0,1) which is the top row 2nd place and we do the same: we mark it as water "0" and we visit the horizontal and vertical cells containing land, thus this reaches the right cell (0,2) which is the top 3rd place from the left, so it will be counted as part of the first island. I hope this helps.

[@DanielVazquez]

Is there any advantage of solving this problem using DFS vs BFS?

[@MrMayurB]

Need help with Most Stones Removed with Same Row or Column - [Leetcode], it is similar problem but could not understand.

[@AlgosWithMichael]

im going to do a video on that problem

[@nagesh007]

Super

[@saulgoodman6710]

This solution shouldnt work since you're not considering diagonal cells which are also part of the island right?

[@Srikanthking1]

Can you explain open the lock problem of leetcode? Also can this be done using bfs instead of dfs? I tried bfs and got timeout exception in leetcode

[@AlgosWithMichael]

ill have to look at this problem, i havent seen it before. thanks for watching!

[@marceldegas]

When I try this implementation in Ruby, I get "stack too deep" error

[@AlgosWithMichael]

2 years late lol, but I would say it is because your exit condition is not correct

[@india1727]

If the case is to find the number of connected islands we will be using the diagonals along with the top and downs, am i right?

[@AlgosWithMichael]

for this problem, an island does not include diagonals

[@milaness2730]

Very good

[@AlgosWithMichael]

thank you

[@saswatibhattacharjee7387]

Great explanation. But when I submit this code in Leetcode it throw a error message Java.lang.stackoverflow error. Can you help me?

[@rico5146]

This solution is dfs in matrix so i think that you maybe didn't check the duplicates. if dfs is proceeding and next node not checked as "visited" then it will result in stack overflow error exception. You can handle it simply by making 2d array for visited check. once your dfs function visited next node or cell(in this matter)you should do "visited check for that node" to prevent the next dfs from making duplicate visits. Make a cheke array such as visited[r][c] and when visited a node location at x and y, then assign integer 1 in visited[x][y]. Hope this help.

[@AlgosWithMichael]

a year late lol... but stackoverflow error is usually a problem with your base conditions in your dfs function

[@pranupranup8285]

in your example you have 5*5 , but in the leet code problem, its 4*4 , but how did you get the count as 3??

[@AlgosWithMichael]

regardless of the size of the array, the number of islands was the same

[@MrPrakash219]

Good one.

[@AlgosWithMichael]

thank you

[@yafeiwang730]

Is this BFS method? Thank you!

[@AlgosWithMichael]

No, this is the DFS method.

[@sifou7974]

thanks

[@AlgosWithMichael]

Of course!

[@monikajha3500]

Is column length always grid[0].length ?? I couldnt understand line 7. or should it be grid[i].length? Please help

[@niksgupta36]

grid[0].length is gonna be always same as grid[i].length, so it does not matter. Put anything!

[@AlgosWithMichael]

since they are the same length of row and column, it wont matter

[@AlgosWithMichael]

yep, thanks for explaining

[@rajathanand93]

Can you solve K closest points to the Origin? Leetcode - 973

[@AlgosWithMichael]

Yep, that problem is top on the list.

[@nitin_agrawal]

what if we can take diagonal also?code change?

[@AlgosWithMichael]

Yea, the dfs function would be different

[@doctor3397]

Will the algorithm still work if the matrix is like this? 11100 11100 00100 00011 00011 => should return 2 After you count 1 for [0][0] and make the surrounding 1s to 0s. You would have a matrix like this. 00100 00100 00100 00011 00011. You would count again when you come to [0][2]. Your algorithm would return 4.

[@dattu06]

After you count 1 for [0][0] and make the surrounding 1s to 0s (recursively). You would have a matrix like this. Once you make the surrounding 1 to 0, you continue to do to its neighbors again 00000 00000 00000 00011 00011. You will count again for [3][3]

[@doctor3397]

@@dattu06 I get it now. Thank you!

[@AlgosWithMichael]

after turning the 1's to 0's, it would return 2. Sorry for the mega late reply lol

[@AlgosWithMichael]

thanks for explaining it haha

[@jorgeacetozi7263]

What's the time complexity for this solution?

[@AlgosWithMichael]

O(M*N). a year late, but thats what it is haha

[@XxBruce5002xX]

@@AlgosWithMichael Hey, thanks so much for this video - could you tell me, are M and N the arrays which make up the 2D array? (The array of arrays). And could you tell me the space complexity?

[@AbinayaThiyagarajan777]

In this you are changing the current element as well to 0, thus making entire array to zero.Aren't you?

[@vasshe]

Yep. That's to avoid infinite recursion. If A is 1 and B (right of A) is 1, when calling the changeLandToWater for B, it will call changeLandTowater(A). If you don't make A as 0, it will again call changeLandToWater(B) and get into infinite recursion.

[@AlgosWithMichael]

a year late... lol but yea, it will turn the array to 0 to avoid infinite loops

[@AlgosWithMichael]

well explained, thank you

[@def__init]

Give me more

[@AlgosWithMichael]

a year late, but i have been posting alot more

[@shripalm]

Great explanation

[@AlgosWithMichael]

thank you

[@OFIRROZANES]

what is the time complexity of this solution?

[@adeleketinuade3931]

Great explanation

[@AlgosWithMichael]

Glad it was helpful!