Technical Interview Question: Number of Islands [LeetCode]
Вставка
- Опубліковано 29 вер 2024
- In this video, I explain the popular coding interview question Number of Islands.
🎧 Join the community Discord: / discord
💰 Support me on Patreon: / michaelmuinos
🔗Follow me on LinkedIn: / michael-muinos
📂Follow me on Github: github.com/Mic...
This problem is asked at Google, Amazon, Facebook, and many other companies.
The idea behind the algorithm is to use a DFS traversal to change all land to water. Each time we encounter land, we will tally up how many islands their are. This problem can be solved using a BFS or Union Find algorithm, but I find the Depth First Search solution the easiest to understand.
![Technical Interview Question - Max Area of Island [LeetCode]](http://i.ytimg.com/vi/JP39wU1UhRs/mqdefault.jpg)
![Technical Interview Question - Max Area of Island [LeetCode]](/img/tr.png)
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!
Thank you so much, more videos to come!
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!
nice, thanks for watching
Man you finally made me to understand recursion!!!!!!!! my hero!!
that is exactly what i wanted :)
Really nice content !
Thanks!
Great video, great explanation. Thank you so much.
of course, thank you for watching
Thank you so much for explaining this problem so well. :)
anytime
Thank you for the clear explanation.
No problem!
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!
Thank you so much, I really appreciate that!
I second this.
By far the best mentor
Great explanation
Thank you!
Is there any advantage of solving this problem using DFS vs BFS?
Very good
thank you
Is this BFS method? Thank you!
No, this is the DFS method.
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
ill have to look at this problem, i havent seen it before. thanks for watching!
Give me more
a year late, but i have been posting alot more
I am not sure if your up and down notations are correct.
Yeap. Up should be 'i-1' and Down should be 'i+1'
Yea, I messed them up lol
Great explanation
thank you
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.
For the same algo it's saying maxing recursion depth excided, In pythn
Up and Left recursive calls are not needed the way you are iterating in the caller.
This solution shouldnt work since you're not considering diagonal cells which are also part of the island right?
Best vid I have seen on this, thanks!
thank you
what is the time complexity of this solution?
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.
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..
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.
Super
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?
Good explanation, just a tiny detail: you just missed to change the firsts "ones" occurrences to zeros in the graphic explanation.
Do we need to call the recursive function for up and left? I think calling it for down and right shoulder care of it
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
@@ForCodingInterview ahhh. Make sense. Thanks for explaining.
Very nice explanation ... Clear idea:-)
Nice, thanks for watching!
Every time you ever go over a problem I say to myself "Why did I ever struggle?"
haha I'm glad the vids are helping!
Best explanation on this topic! Loved it (y)
glad to hear!
Thank you.
No worries!
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 :)
Awesome to hear! Thanks for watching
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( )
Thank you very much!
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.
Most definitely! Thank you for watching!
Need help with Most Stones Removed with Same Row or Column - [Leetcode], it is similar problem but could not understand.
im going to do a video on that problem
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??
regardless of the size of the array, the number of islands was the same
great explanation
Thank you!
Can you solve K closest points to the Origin? Leetcode - 973
Yep, that problem is top on the list.
such a great explanation!
awesome!
Excellent.
thank you
thanks
Of course!
Great explanation. But when I submit this code in Leetcode it throw a error message Java.lang.stackoverflow error. Can you help me?
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.
a year late lol... but stackoverflow error is usually a problem with your base conditions in your dfs function
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?
for this problem, an island does not include diagonals
Great explanation! Could you please tell what is the run time complexity? Both space and time?
Both the time and space will be O(M*N). Sorry for the very late reply lol
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.
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]
@@dattu06 I get it now. Thank you!
after turning the 1's to 0's, it would return 2. Sorry for the mega late reply lol
thanks for explaining it haha
Best video, it's really useful. Thanks!
i appreciate that
Is column length always grid[0].length ?? I couldnt understand line 7. or should it be grid[i].length? Please help
grid[0].length is gonna be always same as grid[i].length, so it does not matter. Put anything!
since they are the same length of row and column, it wont matter
yep, thanks for explaining
Great video. Thanks for your clear explanation.
of course!
very clear and helpful. Thanks
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!
In this you are changing the current element as well to 0, thus making entire array to zero.Aren't you?
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.
a year late... lol but yea, it will turn the array to 0 to avoid infinite loops
well explained, thank you
Best explanation I have seen. Thanks!
Thank you, I appreciate the kind words!
When I try this implementation in Ruby, I get "stack too deep" error
2 years late lol, but I would say it is because your exit condition is not correct
very clear explanation!!!! Thanks for sharing!
no problem
Nice! You should create more videos like this but with other problems. 👍🏻
Only 2 years late, but I have been uploading every week now :p
what if we can take diagonal also?code change?
Yea, the dfs function would be different
This is a really good explanation! Great job doing in !
anytime :)
very clear explanation! thanks
awesome, thanks for watching
So easy to understand!
Glad to hear :)
some home slices be doing this with dem trees dough
fuck yea
What's the time complexity for this solution?
O(M*N). a year late, but thats what it is haha
@@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?
Awesome, just made me understand this in one shot.
glad to hear
Great explanation
Glad it was helpful!
Very easy and clear explanation!!
awesome to hear
Awsme video
Thanks a ton
anytime
Really great explanation ...
i appreciate that
Good one.
thank you