Number of Islands
Vložit
- čas přidán 6. 09. 2024
- For business inquiries email partnerships@k2.codes One of Google's most commonly asked interview questions according to LeetCode.
Google Coding Interviews Number of Islands (LeetCode) and explanation.
This interview question is from LeetCode and commonly asked by the following companies: Google, Facebook, Amazon, Lyft, Uber, LinkedIn, Apple, Bloomberg, Microsoft, Alibaba, and more.
Problem description: Given a 2d grid map of '1's (land) and '0's (water), count the number of islands. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.
Example 1:
Input:
11110
11010
11000
00000
Output: 1
Example 2:
Input:
11000
11000
00100
00011
Output: 3
Support me on Patreon: / kevinnaughtonjr
Follow me on GitHub: github.com/kdn251
Follow me on Instagram: / programeme
My Desk Setup
Desk - bit.ly/3jfY195
Chair - amzn.to/2O9TM3r
Monitor - amzn.to/3rcSHGa
Webcam - amzn.to/2NUmwgi
Desktop - amzn.to/3tiySPL
Laptops - amzn.to/3aRoN3Z
iPad - amzn.to/2LlJzzJ
Keyboard - amzn.to/3jfbxdd
Mouse - amzn.to/36ElWtT
Wrist Rest - amzn.to/3trrHF4 (pls don't buy this)
Mouse Pad - amzn.to/2Myz2lt
Microphone - amzn.to/3atNyTA
Lamp - amzn.to/3jjfZYp
Headphones - amzn.to/3tvr0KU (new model)
Headphone Hook - amzn.to/3tr8uTC
Blue Light Glasses - amzn.to/3cDVUdK
Wireless Charger - amzn.to/39LY1uu
Keyboard cable - amzn.to/2O5p2R5
Mic arm - amzn.to/3cECZj8
Audio interface - amzn.to/36HdWIi
Cloudlifter - amzn.to/36VO6kf
Laptop dock - amzn.to/2O2DsBw
Motherboard - amzn.to/3rkiWuA
Solid state - amzn.to/3rk5vuo
CPU cooler - amzn.to/3tnwwPA
CableMod - amzn.to/3tqbtM8
CPU - amzn.to/3auG1ns
Power supply - amzn.to/3trsAxo
RAM - amzn.to/39JZcuf
Designing Data-Intensive Applications - amzn.to/2YK4ek1
Clean Code - amzn.to/3txqfB5
Meditations - amzn.to/3cDa4fi Discord: bit.ly/K2-discord
If you found this video helpful be sure to check out the interviewing service I made! thedailybyte.dev/?ref=kevin
Thank you for covering this problem, it's pretty important.
By the way, it is absolutely not necessary to return an integer from the dfs, actually an interviewer can ask you why are you doing that.
dfs can be void and just increment after calling it in the main function, because you already know that you have one island (grid[i][j] == '1') and you can't have more than one in that recursive calls, because if it find more one they belong to the same island.
Another follow-up question that can be done in an interview is "What if you cannot modify the matrix?" In that case, an option would be creating a boolean[][] of seen/visited, which takes space but also solve the problem.
Thanks for all your work Kevin, I really appreciate it.
a stupid question here i hope to get help with
was the grid passed to the dfs method by value?? if that is the case if we did not update the original grid dfs will be called on every appearance of 1?
@@ahmadalbaz6059 by default arrays are passed as reference in parameters.
@@nmnjn
ahh thank you!
Actually not by reference, but you can think it as reference. It passes a copy of the memory address, because it is an object. Google how objects are passed as parameters in Java :)
@@darod6098
Thanks man
I'm not that familiar with java that's why I'm asking
Bro you are a legend .. you are a natural in making ppl understand stuff .. great work keep going
Harshal Patil thanks Harshal I really appreciate that thanks so much for your support!
Right? He deserves wayyyy more subscribers
I love your videos seriously. If possible, I hope to see more DFS, BFS, or shortest path related questions as well.
Keep up the great work, buddy!
Thank you so much I really appreciate it! Thanks for the suggestions, I'll see what I can do!
I like how you're able to explain the solution in just 10 minutes, yet it doesn't feel fast-paced.
I wouldn’t have done it that way, but it’s actually so much more elegant than my solution. It’s like a wave spreading out to flip the 1s to 0s if they are connected to the initial 1. That just reduces all connected squares to 1 island.
Also when he typed the semicolon I was confused initially, but it seems that even good programmers can make syntax errors. Good to see I can catch errors while reading code.
I have literally no idea about graphs, but the way you explained it. just nailed it.
best explanation. thanks for explaining every loop instead of just writing it and assuming we know everything
This is nice bro. There is only one advice is that we actually don't need a return value when we are dealing with the base case. Just return and numIslands++ every time we "sank" an whole island.
Good stuff, I like the length of your videos and readable code. I’m prepping for an interview in the midst of finals and it’s nice to not have to be mentally exhausted after going through LC questions. Keep up the good work!!😁
haha thanks Christian I really appreciate that. Lmk if there's anything I can do to try and help you!
@@KevinNaughtonJr Hey kevin i just love your way of make us understanding of solution, can you make some videos of interview bit questions aswell?
This is pretty genius, and very clearly explained. Essentially, even though the neighbours of your island grid point are 1, your dfs method returns 1 for each neighbour but these arent stored anywhere. Only the original dfs call is returned as an increment of the island. Simultaneously, you avoid the double count (as you said) through this approach.
I was thinking of an iterative approach of checking the row above you and to your right, each time, but it quickly span out of control. I think your solution is the best thus far!
same here. got out of control
thanks!!!
The time complexity of the code is O(m * n), where m is the number of rows and n is the number of columns in the input grid. This is because the DFS function is called for each cell in the grid, and each cell is visited at most once.
The space complexity of the code is O(m * n), as the maximum depth of the recursion is the number of cells in the grid, and in the worst case, all cells could be part of the same island. This means that the call stack could have up to m * n frames. Additionally, the DFS function modifies the input grid in-place, which requires O(1) extra space.
You are amazing man. Explaining such complex problems with such ease is sheer brilliance.
It's a great great service you are providing to us who seek for these explanations. God bless you.
Thanks so much! If you need help with these questions and like my explanations sign up for the interviewing service I created: thedailybyte.dev/?ref=kevin I recommend joining the annual tier if you can! :)
Man, the way you speak, it tells a great deal about your level of understanding with the questions and dsa as a whole. Great job dude.
I was asked this question in an interview.I explained in the same way you are explaining and interviewer was very much impressed.Thanks to you ..! I got the job..!
that's amazing congrats!
@@KevinNaughtonJr Thanks ..!
Understood this problem for the first time. Thanks
Hey Kevin.. thanks for the videos. I got the same question in Amazon on call interview. They asked the distinct count. I followed same approach per your video but saved the path which we visited in a list. Thanks again.. you are doing great job!
@Krishna, Can you please ellaborate more on what do you mean by distinct count?
@@shraddhakharche1107 - AMZ asked to provide count on distinct count of islands. i.e. islands coordinates are unique.
Deep dive on the recursion part would be great! I understand generally what is going on, but little things like the returning of int 1 screw me up as far as how that return statement gets carried over into all of the other calls.
All connected 1s will return 1 (after altering itself from 1 to 0) , so the top level 1 which called all these recursions will receive only one 1; which is then added to numIslands.
Solid medium question, was asked this by Amazon for my internship onsite, managed to solve it in 30 minutes and got the offer
Dude you explain everything so clear. please don't stop making vids.
Thanks and I won''t don't worry :)
I love your work man, how you break down complicated problems into very simple terms, keep up the great work!
Amazing solution man!. Keep going. It really helps people like me without a background in CS to learn more about writing optimal codes in a simple way. Thanks
Idk how I never responded to this, my bad!!! Thanks so so much for the kind words they mean a lot to me. So happy to hear my videos are helping :)
Love your vids man, I've been prepping for my interviews and your explanations are super clear!
Thanks Jay, anytime! If you need any help please be sure to let me know!
Could you please explain 733. Flood Fill, you are the best CZcamsr for me who can explain everything so clear. Thank you!
was scratching my head for an hour, you explained it very good and made it simple to understand. Thank you.
anytime and thanks!
Thanks Kevin! I was able to solve max area of island after understanding this video of yours.
Concise, yet comprehensive.
Bloody amazing!
thanks!
I was so scared of this problem you made it look so easy
A video about recursion and discussion on that subject more deeply would be really useful. Overall really good explanation !
How does grid gets updated when it gets back to the for? Are you passing it by reference?
beautiful and better than any paid services out there :)
I really like the solution and the way you went through the thinking of it. Keep posting it and Big Thank you Bro.
You make it sound easy. Have you come across this problem before? Because I could've never solved it in my first ever attempt
Hey Thanks Kevin. I had been preparing for online assessment of Amazon. Kudos to your explanation, I was able to solve both the questions. Thanks :)
Jeet Patitundi amazing and anytime!
just solved the amazon tagged questions ?
Yes. Even I bagged the job. Thank you Kevin. You are a life saver.
@@jeetpatitundi6128 were you able to solve all questions in the final interview ?
Jeet Patitundi anytime and congrats Jeet super happy for you!!!
Interesting video ! The technique is correct, but you are going to get an heap overflow (atleast in C++). You better check before your next recursive call to dfs if the grid[x][y] you are going to use is valid and a '1' to avoid unnecessary calls.
Do we need to go up and to the left? It seems like we would have encountered '1's from these directions because we're scanning up-to-down and left-to-right.
The return 1 ; inside the DFS call is really not required as the DFS call of any index with 1 always returns 1.
We can straight away update islandCount if we see a 1 inside main function.
Code is super clean btw!!!
Thanks! I believe that the return 1 is necessary otherwise we wouldn't be able to actually count each island. As an alternative though we could move the +1 inside the nested for loop!
Once u recursively Call DFS again on the horizontally and vertically adjacent nodes and keep calling them do you use the returned 1 anywhere except for the time you are calling from the main function.
No right?
So do we really need to return anything?
In each DFS call we just want to erase the corresponding 1's.
Right I see what you're saying. So we can just make it the inner loop look like numberOfIslands += 1 and then call the DFS function?
@@KevinNaughtonJr
Yes!!
😀
I agree with Soumya here, the whole time I was like " why is there a return". You can code things up multiple ways, but Soumya explained it well. I feel its more intuitive.
you find a 1
Increase count by 1 and then perform a void dfs that just flips the 1's to 0's and then continue until you find another 1. (insert DJ Khalid voice)
Great content and very clear explanation. Thank you very much for your video! It really helped me understand this question. Please continue making more videos like this!
You make the questions look so easy ! Gem of a person you are!
Kevin, you are AWESOME at explaining stuff man! I have seen many great coders but they suck at explaining!
But you are really awesome! I totally understood the solution! Thanks a lot and please keep making such elaborative videos!
Hi Kevin .thank you very much ...your videos are real saviour ...can you please make a video on how to
1> think the recursive solution
2> decide the base case
3> your general approach to break down any problem into a recursive solution
like... almost everything about recursion
thanks
I've been following you on LinkedIn for a while -- you, amongst others, are inspiring me to work harder than ever (and be happy doing so) to achieve something I never considered to be in the realm of my possibility. My google interview may be sometime in September (pending interview slowdown status). Thank you for your insight and perspective!
Completing the video with the time and space complexity analysis will be way helpful!
Thanks brother. Could please elaborate the line 24 : grid[i][j] == '0' and the time complexity. Thanks again
The complexity is O( n x m ). grid[i][j] == '0' means to press each stone of the island under water, and as a reward, obtain one "dfs"（island)
instead of having a visited 2d matrix , u are making the original visited cells as 0 itself ??to prevent traversing them again?
I Understood such a hard question which i usually skip & you made it look so simple. Great Work & Please keep it up,
thanks!
Great and simple explanation. Thanks Kevin. As you mentioned at the tail end of this video, if you could do a deep dive into the DFS recursion of this problem, it would be awesome. In my experience, this tracing of calls need to be revisited all the time because, I don't think one does this in their daily job, but only during interviews this concept becomes very important, and revisiting this again and again helps clears the confusion that may arise at times. If this deep dive video exists, please post it - Thanks again.
Lucky to find your videos. Set my first aim in new year, to watch all the videos you made as soon as possible. Two at least one day. Hopefully help me with my near feature interview with Google。
near future...
Haha thanks that sounds like a great resolution to me! Thank you so much for all the support and let me know if there's anything I can do to help you prepare for your interview!
@@KevinNaughtonJr Thank you for your help in advance.I think I need to overcome the poor expression...Explained them in English something hard for me and often go blank. I will persist in watching your video to learn from it !!!
Kevin thanks for the videos! Your explanation is very easy to understand, now it has become for me like i am sure i will understand when i watch your video more than i trust my own understanding 😊 well, would you mind just discussing the time complexity also? For some some complex problems that involve recursion, like this one in this case. Thanks again!
Your channel is super helpful!
Thank you for what you do!
Thanks Eugene and anytime! I'm super happy to hear my channel has been helpful for you :')
Even Odd
Problem Description
Given a range [low, high] (both inclusive), select K numbers from the range (a number can be chosen multiple times) such that sum of those K numbers is even.
Calculate the number of all such permutations.
As this number can be large, print it modulo (1e9 +7).
Constraints
0
Thanks for posting this. I have one question - It feels like your dfs() is dangerously close to just producing side effects when you could increment numIslands and then run some kind of "sink()" recursive helper function. Where do you draw the line if you were considering OOP?
Thanks Kevin, This was really helpful. I always struggle with graphs but your solution made it easy :)
For some reason just hearing you say the problem made me realise the solution by 1:20 :) Thanks for the push
I’m wonder if there is a way to optimize it by somehow moving the selected cell to the end of an island before the start of the other. Doesn’t seem like it would work optimally though cuz it has too many checks.
Also, is there a specific reason for making the helper method return 1s or 0s? Is that more efficient than checking it within the loop and having the helper be a void? Even if it doesn’t change the runtime or memory usage, having it return the value is more elegant.
Recently encountered a slight modification of this problem in one of the tests in which we have to find the islands completely surrounded by water i.e no other Island should be touching the island under consideration.
I do have a question, why do we have to search for four directions, why can't we search for only right and down directions?
this video was so clear and easy to understand, thank you so much always!!!!
wouldn't it make more sense to make dfs not return anything and just increment num_islands after the call to dfs?
Immutability should be preferred, this might be considered really bad by some interviewers as changing grid content is something not good.
then you can have memory tradeoff. Dont modify original.. make a copy. you have to have some way to keep track of where you have been.
Good video, but it would be nice if you could also say about the time and space complexity of your solutions.
the simplest solution ever, great job man!!
I am going to follow your playlist as you are the only youtube here who is so fluent and clear with his coding skills. I wish I could solve problems like you one day.What is the secret ingredient ??
SANKALP TYAGI thanks and just practice!
@@KevinNaughtonJr Seriously I am not able to think as you do. I recently got kicked off the Facebook interview. Some problems are so damn hard that I feel like quitting now. Sometimes I think its not even my cup of tea as I flunk at it always :(
Love the simplicity man!!!
Thank you for this video!! You did a great job of really helping me understand why your solution works and made is really easy to catch on with your way of approaching the problem
Blew my mind. Thanks for making these walkthroughs!
Thanks for the video. It's obvious that you know this problem very well. I think this would be even better if you really outlined your mental model and problem solving approach a bit more, as if you were seeing the problem for the first time.
if you start in 0,0 do you really need to call i-1 and j-1? if you go always to the right and down, you dont need to go back as its already visited, at least thats what seems to me for a quick inspection.
Clever!
Awesome solve but you your recursion can simply return a void and you can just keep a count of how many islands you have had to sink in your main loop.
Kevin helpp! Which was the question you solved which added a string index : count or something into a hashset
For Memoization
nice video.. dfs doesn't need to return a number and could just be used to clear up the island.
Why do we use the dfs() to return 1 and do numIslands += dfs().
I would think it would be more clear to change dfs() name to sinkIsland(), then do
sinkIsland();
numIslands++;
Wait, why didn't you make the grid global? How can the dfs() method access the grid and mark it 0 if grid is only local to the numIslands() method?
Brilliant explanation, easy to follow and understand.
what a video.. amamzing.. awesome, best, and crispy!
Thank you! Your explanation is really clear, have a bit trouble understanding this kind of graph problem, but you made it easy! Thanks
You are just the best and easygoing educator ever when it comes to coding.
I had a question, about returning 1
Why did we return 1?
Why no counting while performing recursive calls?
It doesn't matter what we are returning from the dfs function to get to the answer. We just need to return from the function when the base cases are satisfied. Instead of returning an int, 'void' and 'return' could be used as well!
I have my Google interview and my small term goal is to solve at least a 100 Google related problems. Thanks Kevin! This helped me a lot! :-) Also would appreciate if you could add more Google related problems.
Could you do coding questions of relatively more complex graph algorithms especially for weighted graphs?
What is the run time and space complexity of this solution? Nice explanation btw.
Space is O(1). Runtime is O(nm).
Similar idea, I create a dfs that will change adjencent 1 to 0. in the loop, call dfs, and count left 1, which is isolated island.
So is the time complexity O(n^2) ..? Plus what would be the space complexity?
Hi Kevin,
thank you very much for sharing.
if you ever have the time, id love to see you take on the higher difficulty questions (medium/hard)
Thanks for the input, I'll try and start doing some harder problems!
Nice solution, thank you! Just a nit, I believe the check grid[i][j] == ‘0’ is not necessary since you check it’s equal to ‘1’ before calling dfs.
i think you actually need that check to bottom out your recursion in some instances
@@KevinNaughtonJr Yep I quickly found that out :P
Why should we initiate grid[i][j]=‘0’ in dfs method
The approach and explanation are on point! Thanks a lot!
ok, this might be a really stupid question, but how does the calling (numIslands) "grid" get modified ? All the work that's happening is in the helper method's grid, and we dont return those changes back to the numIslands... :////
So how? :/
Interesting takeaway in this problem that I didn't realize before: In python, doing a index-wise value update will modify the originally passed in grid variable
Can you comment on why you'd use DFS instead of BFS on this particular problem? I've seen other solutions recommending to use BFS instead, and I'm having a hard time explaining to myself why you'd go one way or the other, for this particular problem. Thanks!
You don't have to return anything from the DFS. If you call it from a '1' location you are guaranteed an island.
Undoubtedly recursive approach is explained nicely .I was wondering if you also make iterative approaches for Tree problem ?
IT took me minutes understand your logic , Thanks Man.
Perfect explanation. Thanks a lot!!
Kevin will make you feel these questions are simple while actually they are not :)
Thanks so much. Your video is so clear to the point.
Thank you for such a simple explanation! It was really helpful!
Oh man! you made me feel it as an easy problem, which I originally felt very very hard. Thanks a buddy!
Harinath Reddy Amasa anytime!
Great explanation kevin thanks a lot
Congratulations!! Once again you won my heart 💕