NUMBER OF ISLANDS - Leetcode 200 - Python
Vložit
- čas přidán 23. 07. 2024
- 🚀 neetcode.io/ - A better way to prepare for Coding Interviews
🐦 Twitter: / neetcode1
🥷 Discord: / discord
🐮 Support the channel: / neetcode
Coding Solutions: • Coding Interview Solut...
Solve it yourself: neetcode.io/problems/count-nu...
0:00 - Conceptual Solution
5:00 - Coding
#Coding #Programming #CodingInterview
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission. - Věda a technologie
🚀 neetcode.io/ - I created a FREE site to make interview prep a lot easier, hope it helps! ❤
Is it O(n) time because we're not visiting the same element twice?
Sir you are a hope! Your content is super awesome! Liked it subscribed it. I think I should start paying for bit of amount ..it' free but invaluable!
Thank you for everything that you have done. You are awesome!
Very nice channel that helps me a lot. But one thing that I notice is the lack of discussion of time and space complexity every so often. I'd really appreciate it if you could discuss it in every single one of your videos. Thank you so much.
The time complexity is in the order of O(n) because of DP using the visited array. And because of this array, the space complexity also is in the order of O(n).
Algorithm uses BFS, and time complexity and space complexity can be verified from BFS
It's amazing how clear your explanations are. Thank you for the videos!
Nice vid! I find that the naming convention for r,c and rows, cols could be better because they are used multiple times in different "levels" and is quite confusing which rows/cols/r/c we are talking about.
It doesn't help that he refactors (r + dr) to (row + dr)...
using that range might be expensive instead explicitly use 0
I think so!
Very informative channel. I am not just learning intuition for building algorithms, but also coding in Python. Thank you very much
Beautiful clean solution and well explained. Thank you!
It is a standard algorithm from computer graphics called Flood Fill which builds upon DFS
building an app right now with drawing functionality, and I'm finding myself coming back to graph algorithms for a very practical purpose!
by far the best explanation I've seen for this problem. Thank you!!
Happy it was helpful! 🙂
Hats off to the best explanation out there.
cant thank you enough..I just saw it once and and it was done..very nice explanation 💯
Such a beautiful explanation! Thank you!
Thanks for the great explaination. if I understand this right here is what should be done for this problem - iterate all elements in the array, for each element if it is 1 and not visited then run dfs/bfs to mark all adjacent 1 as visited and increase the island number by 1.
ye, that's a good summary!
Really nice explanation. Can you also please explain the logic for treasure islands problems?
Well done nicely explained :-)
Is using bfs faster for this problem? If that's the case, how do we determine when to use bfs instead of dfs?
Thanks for the excellent video! Does anyone know the complexity of this?
Your videos are very helpful. Thaks a lot.
In this code, when you say [1,0], you are actually moving one row vertically down by doing row+dr. So, we are not moving right along x-axis. Instead, we are moving down.
Similary, for the direction [-1,0] -> It is upward
[0,1] -> Right (Moving right by col + dr)
[0,-1] -> Left
Please correct me if I am wrong.
I caught that as well.
I guess it doesn't really matter since you check all four directions anyways, the order doesn't matter.
Good observation regardless.
Thanks for this comment! I was super confused about the directions. This helped :)
Yep saw this as well, just wanted to confirm. Thanks for commenting! :)
Thanks alot for such an easy explanation, coding made easy. This helped me to understand question and solution both
To be honest he didn't explain this question completely like if you look at his latest videos he completely discusses each and every step but in this question, he didn't explain a lot of stuff.
My DFS solution is very similar to word search but somehow, it is easier. As we just keep eliminating the 1 until there is no 1 left and count that as an island. Then continue the algorithm to search next 1, until all the grids have been searched.
class Solution(object):
def numIslands(self, grid):
"""
:type grid: List[List[str]]
:rtype: int
"""
count = 0
if not grid: return 0
def dfs(i,j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]):
return
if grid[i][j] != "1":
return
if grid[i][j] == "1":
grid[i][j] = "#"
dfs(i-1,j)
dfs(i+1,j)
dfs(i,j-1)
dfs(i,j+1)
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
count += 1
dfs(i,j)
return count
much easier solution, thanks!!
holy shit the "if r in range(rows)" is clean. never seen that before.
I love your solutions and explanations Neetcode. You make easy what others make hard. In this particular case I'm a little worried in terms of complexity since it seems is O(n)3? Can it be done with less time complexity?Thanks.
I don't think so. Although he's looping for m x n, he's only doing something meaningful (BFS) for nodes that haven't been visited. So basically we are just visiting each node once, i.e. O(m x n). But technically, yeah, this is O((m x n)^2)
Brilliant Explanation!
Neetcode is the reason leetcoding feels like therapy
@NeetCode Nice solution! I was thinking about it from a DFS point of view, and recursion instead of interation. Got a question though, what's the time and space complexity of this? Thanks!
I think that the time complexity is O( n x m ) as you iterate through all elements in the grid and visit them only once, and space complexity you used a queue and a set which will at most have (n x m) elements, this is an image explaining space complexity of queue in 2d grid
What will be the time and space complexity? Thanks
This video helped me a lot. Thanks for that!
Glad it helped!
Thanks!
Hey Shravan, thank you so much! I really appreciate it 😀
Great solution. Please go thourgh Time and Space complexity as well
For this particular question, I find DFS more straightforward (and also much more concise).
Really nice explanation. Thanks man
absolutely love this channel
Very nice video. In the BFS, should we use q.pop() instead of q.popleft()? Because q.popleft() makes the q as a stack, which is DFS, right?
In this case, popleft will pop the cells in the order that they are added which is BFS. My understanding is that pop(), pops from the right of the queue which is similar to a stack.
You could use set.intersection() method instead of using double nested loops for the last part where you append the cell coordinates to the result list. It would basically be:
result = [ ]
for cell in atlSet.intersection(pacSet):
result.append(cell)
return result
Yup, you could. But what if the interviewer tells you not to use library functions?
@@itachid Question him why it is useful to write own implementation of something that already exists. Why should a candidate not be allowed to use online resources and built-in library functions?
This is one is pretty easy to do once you've done the pacific waterflow
Hey Neet, how are you able to navigate to different parts of code so fast like at 10:31 when you were replacing the duplicate code. Thanks!!
With his mouse. Play FPS games to get pinpoint mouse accuracy
thank you, because of you i realised that i should use bfs instead of recursive dfs.
ty, i've improved al;ot after watching these video, ty so much
Great video! Small nit: In order to turn your BFS code into *true* DFS code, you must not just transform popleft() into pop() but call visit.add(...) immediately after q.pop()
Great caveat! I just learned that for DFS we set the node as visited only after it's popped out of the stack, whereas in BFS we set it as visited right when we pushed it into the queue
*but ALSO call visit.add(…)
This is a very interesting discovery that has sparked a lot of thoughts for me. Essentially, it all comes down to how you interpret "nodes being visited." If you consider adding to `visit` as visiting the nodes, then you are correct. However, if you shift the perspective and consider performing certain operations (like outputting) as visiting the nodes, then the statement in the video is not problematic. For example:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
will_visit = set() # call it `will_visit` instead
result = 0
for row in range(rows):
for col in range(cols):
stack = []
if grid[row][col] == '1' and (row, col) not in will_visit:
result += 1
stack.append((row, col))
will_visit.add((row, col))
while stack:
r0, c0 = stack.pop()
print(r0, c0) # actual visits happen here
for dr, dc in [(1, 0), (-1, 0), (0, 1), (0, -1)]:
r, c = r0 + dr, c0 + dc
if r in range(rows) and c in range(cols) and grid[r][c] == '1' and (r, c) not in will_visit:
stack.append((r, c))
will_visit.add((r, c))
return result
This truly does DFS.
@@LuminousElysium Hmm, honestly I'm not sure if this is actually DFS? My understanding of the stack is that it represents the DFS sequence of how we process or traverse the graph. (BFS sequence is different such that we use a queue to represent it)
However, for this statement "(row, col) not in will_visit", you will check whether such node is already pushed on the stack in your case since your code push the node on the stack and set it as visited at the same time.
I think this might lead to a problem such that the sequence your stack represents isn't actually a DFS sequence because if one node is connected to a node we've already "seen" (pushed on the stack) before, we won't push it onto the stack again. However, the DFS sequence essentially tells us that we would traverse the path "to the very possible end", so we could potentially add duplicate node onto the stack as such path might involve a node we already "seen" before.
Not sure if I'm making my idea clear but this is just my thought so far on this, please correct me if you find something wrong
@LuminousElysium In iterative DFS, it is best to mark a node as visited only after popping said node from the stack. Otherwise, no node can visit their uncle because their grandparent already visited the uncle.
by the way, you can do the same without visited set just change the value of the from '1' -> '2' in the gird. this will make the memory complexity O(1) since we don't care about the graph anyway so it's ok to modify it
No wait, how would that work?
i got it btw, this is my c++ code
class Solution {
public:
void dfs(vector& grid, int i, int j){
if(i >= grid.size() or j >= grid[0].size() or j < 0 or i < 0 or grid[i][j]=='0')
return;
grid[i][j] = '0'; // Marking as visited.
dfs(grid, i+1, j);
dfs(grid, i, j+1);
dfs(grid, i-1, j);
dfs(grid, i, j-1);
}
int numIslands(vector& grid) {
int num = 0;
for(int i = 0; i < grid.size(); i++){
for(int j = 0; j < grid[0].size(); j++){
if(grid[i][j] == '1'){
dfs(grid, i, j);
num++;
}
}
}
return num;
}
};
But still the space complexity remains O(m*n) because of depth first search or breadth first search is involved in algorithm.
It is generally a good coding practice to not change the input data.
@@aniketbhanderi5927 worst case time complexity of a set can be O(n) in case of collision. It's generally not the case tho.
Very neet! Thanks for adding! I request you to kindly solve some dp problems as well!
I definitely wanna do some DP soon, but I also wanna cover some of the basics first. Any specific DP problems you are looking for?
@@NeetCode Thanks for replying :) I am a self learnt programmer, and in these weekly leetcode contests, usually I am able to solve 3/4 questions. The 4th question is always a dp problem. I am in no hurry, but please consider my request to solve the weekly contest problems! It would be helpful.
Nice explanation on the thought path! Thank you1
6:05 how did you move out of brackets here by typing on the keyboard? I just started learning vim but I don't think this is possible without exiting insert mode, but he seems to do so without changing modes.
i see that you are a vim expert now
@@matthewgand LOL WTF MATT WASSUP MY GUY
great work thanks so much
what is the benefit to solving this with bfs instead of dfs? dfs seems easier to understand imo, maybe I just need to practice bfs more
thanks so much for this!
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?
1, 1, 1
0, 1, 0
1, 1, 1
imagine a really large island with many peninsulas, where there's one part of the land attached to the island on one side only. going in all four directions will cover all the cases
I like to set visited to 2 to remove the visit set, but that solution gives me a too many recursive calls error in recursive dfs, though it works in bfs
Thanks for the very helpful videos 🙏
We can improve the space complexity by setting the cells we visit on the grid to 0, instead of using a separate visit set.
That is true! However, if this was supposed to emulate a real problem, then whoever is calling the function might not want you to change their 2d matrix. Then they would have to create a copy anyway.
Good explanation.
For C++ implementation, is it fine to use a 2d vector of bools to keep track of visited cells. Are is there a more efficient/better way?
Thanks for all the great videos!
There actually is! You can replace each 1 with a 0 as you go over it, and that way you don't have to use any extra space
I think I might try marking the cells as visited by changing the "1" to another char such as "v". maybe that's why LeetCode did it as a string instead of number. then you don't need more memory with the set pairs.
Thanks for the awsome video. Could you please solve this one :694. Number of Distinct Islands
Nicely but actually in BFS function, when you meet the value '1' , you can adjust it to '2', this help you no need to use visit_set
by doing so, can I assume the space complexity will be reduced to O(1)?
@@khagharhimerov3462 but we're still using a queue, so the space complexity will remain the same.
@@SATISH17869 , Thanks!
Isn't it a bad practice to alter the passed in value cos I was thinking of changing visited 1's to 0's?
@@begenchorazgeldiyev5298 yes it is, but since this is not production code might as well do it but let the interviewer know that you're aware
Great video!
This problem is basically the same as Number of Connected Components in an Undirected Graph - Union Find - Leetcode 323 (also his video), and I think Union Find is easier to implement once you know the basic. But this implementation introduces you to BFS if you don't know already.
yes, yes how many times you solved this in your work) correct 0 times)
@@ordinaryggwhy are you so mad? lol
Is the time complexity O(2 N^2)?
8:34 it doesn't really make a difference but the ith position is above and below and jth position is left and right. A good little distinction to understand when you're trying to render a 2D or 3D array in your brain and you brain GPU is maxing out.
Wonderfully explained! Truly "neet" code. A quick question: what is the O(n) complexity?
O(n * m)
Under the description of this problem, the constrains said 1
Yeah. While the constraint does mean that number of rows and columns will always be greater than 0, it never says there need be atleast one island in the matrix and so all elements could be water i.e 0. The above said statement takes care of a case where all elements of the matrix are 0 because python treats it as an empty matrix hence evaluated as False.
what is the time complexity?
Get outta here! This is such a smooth explanation of a question that truly intimidated me before!
I think the flood fill algorithm is faster than BFS or DFS approach in this problem and It also requires less memory :)
bro Neet, could u tell the time complexity of this solution, pls?
Thank you!
Time Complexity: O(m.n)
for looping through each node looking for 1st piece of land we are costing a max of m.n for mxn grid.
This is simple so far, the complex part is that for each node in the grid, we can call bfs(or dfs) which can take more complexity. But if you look at the sum of nodes that bfs(or dfs) touches is bounded by m.n.
For example, if we touched k nodes in mxn grid in the first bfs(or dfs) call, then in the next call we can only touch a max of m.n-k nodes as we already marked the previous k nodes as visited and will skip them.
So, we can touch m.n nodes in the loop, and a max of m.n nodes in bfs(or dfs) call
making it a O(2.m.n) -> O(m.n) excluding constants
Just a small optimization, you could just modify the given grid's "1" to "0" to avoid keeping a visited set.
What is the order of this algorithm? is it o(rowxcolum)?
the explanation is fire
You're helping so many people with these solutions. Dumb question, but why doesn't visit needed to be passed as an argument to bfs() function along with r and c?
Late reply, but the bfs() function is declared within the given function, and the visit set is declared outside of the bfs function and in the given function, so the bfs function already has access to the visit set
For the directions part 8:33 do u mean [1,0[] direction below, [-1,0] direction above, [0,1] direction to the right etc. I feel its the opposite logic to what u said, but please clarify? Thank You
Yeah that confused the heck out of me. It should be this way, I thought I was going crazy
I was asked in the Meta mock interview today. I coded a similar solution with a main with 2 for loops and helper bfs function using a queue. The feedback the interviewer gave at the end was that dfs would be better for this. For problems like shortest path - bfs is good. However, for this problem, it will be faster to go in-depth order.
When I had initially mentioned bfs, he also asked me to explain how I would do it, and the time complexity.
Of course, the worst-case time complexities are the same for both bfs and dfs and its O(m*n).
It is hard for me to understand why dfs would be better though?
Look at nick white video on this. He uses dfs. Dfs is better for this, since it's easier to write - it uses less logic
SIR please do a video on printing all substrings of a string in O(n)..or less than that .. please sir ..
shouldn't the conditions on ine 19-22 be separated? if r or c are out of the range, indexing grid[r][c] would give an error, which is what I encountered
simply change the order of condition . check for 'grid[r][c]=='1'' at the last position after checking " r in range(rows) and c in range(cols)".
Great video!
Btw we can optimize space by using grid itself to mark visited cells.
Also I like a recursion solution, it looks intuitive and clean. Check this out:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def isIsland(i, j):
if not (0
cool yeah this was my hunch as well. the fact this problem was categorized as "graph" kind of tripped me up since I've done flood fill stuff like this before
@@MichaelButlerCa grid is a special type of graph. this is why
In fact you can just set grid[i]j] to "0" rather than "v", and save an additional check :)
Modifying the input variables is generally not advised.
thank you, using recursion is much better.
I did a similar approach:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
islands = 0
def dfs(i, j):
if (i < 0 or i >= len(grid) or
j < 0 or j >= len(grid[i]) or
grid[i][j] == '0'):
return
grid[i][j] = '0'
# do the dfs
dfs(i - 1, j) # down
dfs(i, j - 1) # left
dfs(i, j + 1) # right
dfs(i + 1, j) # up
return 1
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == '1':
islands += dfs(i, j)
return islands
Brilliant!
Is it possible to use recursive DFS for this problem? I find that simpler to understand but I'm sure there's some tradeoffs that make BFS better.
I implemented it using recursive DFS and it's infinitely more readable and easier to implement. It said that Time beats: 88% and Space beats: 97%
I guess that's enough. Though LeetCode let's you modify "grid". If it didn't I'd just have an additional set to remember which positions I've already checked.
A question I have here is using DFS approach. In the courses, during graph DFS, its usually paired with using a hashset to keep track of visited coordinates/nodes, and during backtrack portion we would remove it from the hashset. However, for this problem there is no need to remove it from the hashset. Why is that the case? Is it because we are expanding the search like BFS? If for a different problem, for example - 'number of ways to reach a point', the coordinates would need to be backed out from the hashset to avoid double counting?
I guess that is the case for DFS for the visited node cannot be visited again during the "same path"; however, it can be visited during the another path. Here, there is no backtracking and the problem only requires not to visit the cell if it is already part of "any" island, not just the "current" island. I hope this helps.
Actually we can modify the items in grid "1" -> "0" to avoid using extra space.
Good point. No need to use additional space
This was so hard X_X Neet you must be a genius if this is your favorite my brain hurts
What is the time complexity of the algorithm?
would it be worse to do this problem using DFS to mark an island instead?
I think for this problem both DFS and BFS are about the same. It probably depends more on which one you are more comfortable with coding.
if you wanna use dfs instead:
if not grid:
return 0
rows = len(grid)
cols = len(grid[0])
count = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
self.dfs(grid, r, c)
count += 1
return count
def dfs(self, grid, r, c):
if r < 0 or c < 0 or r >= len(grid) or c >= len(grid[0]) or grid[r][c] != "1":
return
grid[r][c] = "#"
self.dfs(grid, r+1, c)
self.dfs(grid, r-1, c)
self.dfs(grid, r, c+1)
self.dfs(grid, r, c-1)
The explanation on the video helps, but this solution is so simple to understand. Thanks for sharing.
the solution in your video is different from the solution you've included in leetcode discussion. You might want to add the annotation to CZcams.
Genius !!
you don't need the visited set if you alter the data of the list. you can mark "1" -> "2" to mean "visited".
can someone explain me why are checking r and c whether they are in range or not in dfs function
When we are adding/subtracting 1 to get the adjacent indices, we need to check if the indices are in bounds. If we dont check for the valid range, we will get a runtime error - IndexOutOfBounds/
How do I know when the problem is iterative or recursive?
Can you upload some questions about heap?
Why is it in the graphs section though?
I think this solution is a little complicated. This video is 3 years old so I guess Neetcode improved on the coding skills a lot as I used one of his later videos
Here's the solution:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
res = 0
ROWS, COLS = len(grid), len(grid[0])
def backtrack(r, c):
if (r < 0 or c < 0
or r == ROWS or c == COLS
or grid[r][c] == '0'):
return
# mark this position as visited/0
grid[r][c] = '0'
backtrack(r + 1, c)
backtrack(r - 1, c)
backtrack(r, c + 1)
backtrack(r, c - 1)
# visit valid land positions and its neighbors
for r in range(ROWS):
for c in range(COLS):
if grid[r][c] == '1':
backtrack(r, c)
res += 1
return res
Why can't we make the adjacent 1's as "0" in bfs instead of using the set?
Amazing video
Nice, can you show me code how to solve the number of island problem by UCS
Basically the fill algorithm
I think neetcode mentions the directions wrong. [0, 1] -> right , [0, -1] -> left, [1, 0] -> below and [-1, 0]-> above
right
can anyone please tell why have we used bfs here instead of dfs? from what i know(i might be wrong) is that, we want to find "shortest path/ anything minimum" then we use bfs, else dfs. is it true?
You can use any as long as you traverse the whole graph
Thanks
I failed to answer this question at my Google interview yesterday 😅
The best and clear explanation