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!
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( )
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 :)
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?
I've been interviewing lately, and I'm not encountering any of these "common questions" I'm seeing on TH-cam. 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!
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!
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.
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
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.
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]
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 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?
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.
![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)
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
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.
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!
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!
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
Best vid I have seen on this, thanks!
thank you
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 :)
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!
This is a really good explanation! Great job doing in !
anytime :)
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?
Best explanation on this topic! Loved it (y)
glad to hear!
Best explanation I have seen. Thanks!
Thank you, I appreciate the kind words!
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
such a great explanation!
awesome!
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!
Very easy and clear explanation!!
awesome to hear
Really nice content !
Thanks!
Good explanation, just a tiny detail: you just missed to change the firsts "ones" occurrences to zeros in the graphic explanation.
Thank you so much for explaining this problem so well. :)
anytime
Great video, great explanation. Thank you so much.
of course, thank you for watching
Great video. Thanks for your clear explanation.
of course!
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
I've been interviewing lately, and I'm not encountering any of these "common questions" I'm seeing on TH-cam. 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!
very clear explanation!!!! Thanks for sharing!
no problem
Awesome, just made me understand this in one shot.
glad to hear
very clear explanation! thanks
awesome, thanks for watching
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!
Thank you for the clear explanation.
No problem!
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.
Very nice explanation ... Clear idea:-)
Nice, thanks for watching!
So easy to understand!
Glad to hear :)
Great explanation
Thank you!
For the same algo it's saying maxing recursion depth excided, In pythn
great explanation
Thank you!
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
Best video, it's really useful. Thanks!
i appreciate that
Really great explanation ...
i appreciate that
Up and Left recursive calls are not needed the way you are iterating in the caller.
Excellent.
thank you
Is there any advantage of solving this problem using DFS vs BFS?
Awsme video
Thanks a ton
anytime
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.
some home slices be doing this with dem trees dough
fuck yea
Thank you.
No worries!
Is this BFS method? Thank you!
No, this is the DFS method.
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.
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!
This solution shouldnt work since you're not considering diagonal cells which are also part of the island right?
Good one.
thank you
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
Very good
thank you
Super
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
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
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
what if we can take diagonal also?code change?
Yea, the dfs function would be different
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
Can you solve K closest points to the Origin? Leetcode - 973
Yep, that problem is top on the list.
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
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?
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
Give me more
a year late, but i have been posting alot more
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
Great explanation
thank you
what is the time complexity of this solution?
Great explanation
Glad it was helpful!