Number of Islands
Вставка
- Опубліковано 29 вер 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
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 work man, how you break down complicated problems into very simple terms, keep up the great work!
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!
Dude you explain everything so clear. please don't stop making vids.
Thanks and I won''t don't worry :)
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 the questions look so easy ! Gem of a person you are!
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
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.
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 :(
You don't have to return anything from the DFS. If you call it from a '1' location you are guaranteed an island.
nice video.. dfs doesn't need to return a number and could just be used to clear up the island.
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.
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
Excellent explanation, a video on recursion would be wonderful.
Kevin helpp! Which was the question you solved which added a string index : count or something into a hashset
For Memoization
very easily u explained thank you
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?
Where can I start?
Could you please give serial number to video, eg. Problem no 200?
So that I can start from beginning.
Seriously man, I want to get hands on competitive coding and you seems to be helpful, where can I start to watch?
I don't think he does them in order. He just does problems commonly asked by big N companies.
God dammit. This is one of those problems that are very simple once you see the solution.
Hi Kevin, Sorry for posting out of topic question. In BFS why do we have to define the 2d Dirs like below:
int[][] dirs = {{-1,0},{1,0},{0,1},{0,-1}};
When getting the new cell coordinates. Any idea please?
generic code below:
while(!queue.isEmpty()) {
int size = queue.size();
for(int i = 0; i < size; i++) {
int[] cur = queue.poll();
for(int[] dir : dirs) {
int nx = dir[0] + cur[0];
int ny = dir[1] + cur[1];
if(inValidArea(nx, ny) && res[nx][ny] > length){
res[nx][ny] = length;
queue.offer(new int[] {nx, ny});
}
}
}
length++;
}
Nilanjan Chowdhury doing so makes sure you traverse the 4 adjacent cells to the cell you’re currently on (so {0, 1} simulates moving right one cell, {1, 0} simulates moving down one cell, etc)
@@KevinNaughtonJr Thank you.That makes sense. Is it same as I mentioned earlier?
int[] xDirs = new int[] {0,0,1, -1};
int[] yDirs = new int[] {1,-1, 0, 0};
Time complexity = space complexity = O(M*N)
Nice solution!!!Is it not necessary to catch the returning value from the function,like when we call dfs(grid,i+1,j) something will be returned, right?
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!
you are a legend bro
CAN I GET UR FULL CODE ,FOE SOME WEIRD REASON SAME CODE I WROTE BUT ISNT WORKING
What's the runtime complexity for the solution?
// TIme complexity O(N*M) - N number of rows, M - number of columns
// Why? In the worst case we would have grid with ones. We would go through each cell using recursion on the
// first step of the loop. Then we will do constant operation for other steps of the loop, so O(N*M + N*M)
// Space O(N*M) - deepness of recursion
From Github: github.com/chopdev/leetcode_tasks/blob/0df3657e8f02f53f81f7c6e48d7eb17e27857271/union_find/200_union_find/Solution.java
what if they want to add diagonal 1 also, i.e in 2nd eg o/p will be 1 like that
standard flood fill algo!
Does anyone have good suggestions for similar questions on Leetcode?
Why is it returning 4 instead of 3?
public static int numIslands(char[][] grid) {
if(grid==null || grid.length==0) {
return 0;
}
int numIslands =0;
for(int i =0; i
sweet
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!
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
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?
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.
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.
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 :)
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!
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.
How does grid gets updated when it gets back to the for? Are you passing it by reference?
I am such an idiot, DFS and BFS get confusing for me.
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?
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!
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.
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)
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! :)
instead of having a visited 2d matrix , u are making the original visited cells as 0 itself ??to prevent traversing them again?
A video about recursion and discussion on that subject more deeply would be really useful. Overall really good explanation !
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 :')
Javascript version:
const islands = (grid) => {
if (grid === null || grid.length === 0) {
return 0;
}
let numIslands = 0;
for (let i = 0; i < grid.length; i++) {
for (let j = 0; j < grid[i].length; j++) {
if (grid[i][j] === 1) {
numIslands += depthFirstSearch(grid, i, j);
}
}
}
return numIslands;
};
function depthFirstSearch(grid, i, j) {
if(i= grid.length || j=grid.length || grid[i][j] === 0){
return 0;
}
grid[i][j] = 0;
depthFirstSearch(grid, i + 1, j);
depthFirstSearch(grid, i - 1, j);
depthFirstSearch(grid, i, j + 1);
depthFirstSearch(grid, i, j - 1);
return 1;
}
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.
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.
What is the run time and space complexity of this solution? Nice explanation btw.
Space is O(1). Runtime is O(nm).
I was so scared of this problem you made it look so easy
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!!!
// TIme complexity O(N*M) - N number of rows, M - number of columns
// Why? In the worst case we would have grid with ones. We would go through each cell using recursion on the
// first step of the loop. Then we will do constant operation for other steps of the loop, so O(N*M + N*M)
// Space O(N*M) - deepness of recursion
From Github: github.com/chopdev/leetcode_tasks/blob/0df3657e8f02f53f81f7c6e48d7eb17e27857271/union_find/200_union_find/Solution.java
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.
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? :/
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++;
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.
Good video, but it would be nice if you could also say about the time and space complexity of your solutions.
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!
each element in 2d metrix represent the color, how many minium number of rectangles we can form for same color? can we achieve solving this with this approach? if it is already solved can you pl share the link? if not, can you pl help in solving this?
Could you please explain 733. Flood Fill, you are the best UA-camr for me who can explain everything so clear. Thank you!
I am a new graduate and I have hard time doing these questions. I haven’t done any internships to finish my degree faster but it’s been really hard to get a job in software if you don’t have experience. Can you please give me some advice
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.
this is not a complete solution it will fail if there is 1's in diagonal. I think you have to check diagonal cases also
dfs(a,i+1,j);
dfs(a,i-1,j);
dfs(a,i,j+1);
dfs(a,i,j-1);
dfs(a,i-1,j-1);
dfs(a,i+1,j+1);
dfs(a,i-1,j+1);
dfs(a,i+1,j-1);
Congratulations!! Once again you won my heart 💕
You make it sound easy. Have you come across this problem before? Because I could've never solved it in my first ever attempt
Could you do coding questions of relatively more complex graph algorithms especially for weighted graphs?
best explanation. thanks for explaining every loop instead of just writing it and assuming we know everything
So is the time complexity O(n^2) ..? Plus what would be the space complexity?
What is time complexity ?
Thanks Kevin! I was able to solve max area of island after understanding this video of yours.
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)
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?
wouldn't it make more sense to make dfs not return anything and just increment num_islands after the call to dfs?
Great explanation! Please consider making videos on Systems Design :)
Thanks! I've been thinking about doing that...maybe I'll start doing that soon
Understood this problem for the first time. Thanks
this video was so clear and easy to understand, thank you so much always!!!!
nice video. Why don't you make a video on "m-coloring graph"
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!
Thanks so much. Your video is so clear to the point.
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!!!
Does anyone know why leetcode lists "union find" as a related topic?
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
what a video.. amamzing.. awesome, best, and crispy!
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!
Thank you for explaining this one!
Anytime I hope it was helpful!
@@KevinNaughtonJr Totally! It was asked to me 2 years back in fb and i was not able to solve. Only addition they added is, find the longest island as well.
It's a tough one! Interesting modification, thanks for sharing :)
@@mastbawa wild guess: maintain another variable localLongestIsland. Increment it by 1 inside dfs(). Maintain another variable globalLongestIsland. Update globalLongestIsland whenever its smaler than localLongestIsland.
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!
Thanks for making it so simple :)
Hi Kevin,
thank you very much for sharing.
Using BFS would be much easier to understand
What would be the runtime complexity of this? I wish I could answer this right now. On a different (from Leetcode) site I am seeing that a DFS solution times out vs. BFS works. On Leetcode though, this DFS solution clearly wins in terms of runtime. Unable to reconcile those two observations. Anyways, keep up the great job! Your videos are very helpful!
What is the difference between i++, and i+1? I failed task, trying to use i++, and i-- in last few lines of code.
i++ increase the value of i but i+1 dosen't
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 !!!
beautiful and better than any paid services out there :)
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.
Although I liked the way solution is derived in limited time , it would have been better, if visual explanation of the sample test case is considered while you code!