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).
The directions you mention is wrong. Correct way is: [1,0] is row+1 and same col; so down [-1,0] is row-1 and same col; up [0,1] is same row and col+1; down [0,-1] is same row and col-1; up
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.
correct. Having to check whether r+dr is in range is O(n) because it has to check it against every element of the array. Just checking the bounds is O(1)
@@mixtli1975 if r in range(rows): # do something Time Complexity: This operation is 𝑂(1) O(1). This is because range objects in Python are implemented in a way that supports fast membership testing. When you check r in range(rows), Python checks if r falls within the start and stop bounds of the range without iterating through each element.
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
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.
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.
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
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
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
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.
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.
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)
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
Much simpler: Check all 4 sides for land and set the visited node to 0 class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 count = 0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == "1": self.dfs(grid, i, j) count += 1 return count def dfs(self, grid, i, j): if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != "1": return grid[i][j] = "0" self.dfs(grid, i + 1, j) self.dfs(grid, i - 1, j) self.dfs(grid, i, j + 1) self.dfs(grid, i, j - 1)
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.
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
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
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)
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.
Nice! A few things: 1) The checks for r in range(rows) and c in range(cols) are pretty inefficient even if pretty. I'd recommend using normal boundary checks. 2) If you can destructively change the input, you can replace 1s with 0s in the bfs and not worry about another visit occurring, which removes the need for a visit set.
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
@@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.
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.
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.
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
@@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?
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?
Super simple solution: class Solution: def numIslands(self, grid: List[List[str]]) -> int: y_range = len(grid) x_range = len(grid[0]) def fill(x,y): nonlocal grid if x >= x_range or x < 0 or y >= y_range or y < 0 or grid[y][x] == '0': return grid[y][x] = '0' fill(x+1,y) fill(x-1,y) fill(x,y+1) fill(x,y-1) res = 0 for y in range(y_range): for x in range(x_range): if grid[y][x] == '1': res+=1 fill(x,y) return res
It works, But honestly found it to be very complicated the way you wrote the code. I watched Greg Hogg's solution for this problem, that was much easier Marking "Visited" in the grid itself is much easier. But Thanks for the other solutions, you are doing great!
class Solution: def numIslands(self, grid: List[List[str]]) -> int: if not grid: return 0 count=0 for i in range(len(grid)): for j in range(len(grid[0])): if grid[i][j] == '1': self.recursion(grid, i, j) count+=1 return count def recursion(self, grid, i, j): if i len(grid[0])-1 or grid[i][j]!='1': return grid[i][j] = '0' self.recursion(grid, i-1, j) self.recursion(grid, i+1, j) self.recursion(grid, i, j+1) self.recursion(grid, i, j-1)
Thank you very much. This taught me a lot. But at the beginning where you asked "How will a kid solve this problem?", if that's how the kid starts, then that kid is a genius.
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.
i did this for the first time last week i just "destroyed" the island as i visited it setting the visited 1's to zeros before calling destroy(nextSquare) this simplifies the code because the visited check and isIsland check become the same also i didn't use a typical dfs or bfs but i did recursively try and "destroy" islands in all 4 directions
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
@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
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
Using my own solution I get the right answer on 99% of the tests, but one of them I get 44/45. I have no idea how and in the input size is too large to go through step by step xD
I think, i have similar but maybe simpler: def solution(grid: list[list[str]]): visited = set() island = 0 def helper(row, col): if row=len(grid[0]) or grid[row][col] != "1": return grid[row][col] = "#" helper(row, col+1) helper(row+1, col) helper(row-1, col) helper(row, col-1) for row in range(len(grid)): for col in range(len(grid[0])): if grid[row][col] == "1" and (row, col) not in visited: helper(row, col) island += 1 return island
def numIslands(grid: list[list[str]]) -> int: rows, cols = len(grid), len(grid[0]) visited = set() def dfs(r, c): if (r < 0 or c < 0 or (r,c) in visited or r >= rows or c >= cols or grid[r][c] == "0"): return 0 visited.add((r, c)) dfs(r+1, c) dfs(r-1, c) dfs(r, c+1) dfs(r, c-1) # visited.remove((r,c)) return 1 res = 0 for r in range(rows): for c in range(cols): if grid[r][c] == "1": res += dfs(r, c) return res
This code will help with space complexity by 90%... def numberofislands(grid): if not grid: return 0 rows=len(grid) cols=len(grid[0]) islands=0 def bfs(grid,r,c): q=[] q.append((r,c)) while q: dr,dc=q.pop(0) directions=[[1,0],[-1,0],[0,-1],[0,1]] for roww,coll in directions: r=dr+roww c=dc+coll if ( r in range(rows) and c in range(cols) and grid[r][c]==1 ): q.append((r,c)) grid[r][c]=0 for r in range(rows): for c in range(cols): if grid[r][c]==1: bfs(grid,r,c) islands+=1 return islands
class Solution: def map_island(self, i, j): if self.grid[i][j] == "1": self.grid[i][j] = "mapped" if i-1 > -1: # up self.map_island(i-1, j) if j+1 < len(self.grid[i]): # right self.map_island(i, j+1) if i+1 < len(self.grid): # down self.map_island(i+1, j) if j-1 > -1: # left self.map_island(i, j-1)
def numIslands(self, grid: List[List[str]]) -> int: self.grid = grid count = 0 for i in range(len(grid)): for j in range(len(grid[i])): if grid[i][j] == "1": count += 1 self.map_island(i, j) return count
I came here to understand the problem...Seems while explaining the first example...you skipped one 1 which is connected to the same island but is having a 0 as its neighbor...But it should be included in the same island because its vertically connected to another 1...Made me a little confused in the begining!
def bfs(i, g): if g - 1 in range(cols) and grid[i][g - 1] == '1': grid[i][g - 1] = '*' bfs(i, g - 1) if g + 1 in range(cols) and grid[i][g + 1] == '1': grid[i][g + 1] = '*' bfs(i, g + 1) if i - 1 in range(rows) and grid[i - 1][g] == '1': grid[i - 1][g] = '*' bfs(i - 1, g) if i + 1 in range(rows) and grid[i + 1][g] == '1': grid[i + 1][g] = '*' bfs(i + 1, g)
for i in range(rows): for j in range(cols): if grid[i][j] == '1': grid[i][j] = '*' bfs(i, j) islands += 1 return islands
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.
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.
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!
How about we just mark the visited land in the grid itself, and while traversing if we reach a visited land or if it is water then skip computation, in js I would write it this way: (I'm marking visited land with "2") var numIslands = function(grid) { const traverse = (i, j) => { if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === "0" || grid[i][j] === "2") return; grid[i][j] = "2"; traverse(i + 1, j); traverse(i - 1, j); traverse(i, j + 1); traverse(i, j - 1); } let numberOfIslands = 0; for (let i = 0; i < grid.length; i += 1) { for (let j = 0; j < grid[0].length; j += 1) { if (grid[i][j] === "2" || grid[i][j] === "0") continue; traverse(i, j); numberOfIslands += 1; } } return numberOfIslands; };
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.
BFS is nice and all, but no longer works for this particular problem. Try testing this grid: 1 1 1 0 1 0 1 1 1 Should get 1, but instead getting 2 in results. Looks like LeetCode have updated tests, so above solution is no longer valid. Spent a good hour and half trying to figure out why BFS has been invalidated. DFS approach seems to be the way to go.
I tried this problem with bfs and realized I was getting the wrong solution because I was checking if (row/col - 1 > 0) instead of (row/col - 1 >= 0). If you make the mistake I did it completely skips the bottom left cell (2,0) because when the cell (2,1) checks for neighbors, the value of (col - 1) is equal to 0 and because our condition is strictly greater than 0 it doesn't add that cell to the queue.
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
This is simpler, faster and consumers less memory. class Solution: def numIslands(self, grid: List[List[str]]) -> int: def recursive(grid, i, j): grid[i][j] = '0' if i > 0 and grid[i-1][j] == '1': recursive(grid, i-1, j) if i < rows - 1 and grid[i+1][j] == '1': recursive(grid, i+1, j) if (j > 0 and grid[i][j-1] == '1'): recursive(grid, i, j-1) if (j < cols - 1 and grid[i][j+1] == '1'): recursive(grid, i, j+1) rows = len(grid) cols = len(grid[0]) count = 0 for i in range(rows): for j in range(cols): if grid[i][j] == '1': count += 1 recursive(grid, i, j) return count
Using q = deque() or q = collections.deque()? My question is that is there any difference between theses two? When shall we decide to use one instead of the other?
🚀 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
The directions you mention is wrong. Correct way is:
[1,0] is row+1 and same col; so down
[-1,0] is row-1 and same col; up
[0,1] is same row and col+1; down
[0,-1] is same row and col-1; up
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!
correct. Having to check whether r+dr is in range is O(n) because it has to check it against every element of the array. Just checking the bounds is O(1)
@@mixtli1975
if r in range(rows):
# do something
Time Complexity: This operation is 𝑂(1)
O(1). This is because range objects in Python are implemented in a way that supports fast membership testing. When you check r in range(rows), Python checks if r falls within the start and stop bounds of the range without iterating through each element.
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!!
That very cool and easier solution
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!
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!
It's amazing how clear your explanations are. Thank you for the videos!
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! :)
Neetcode is the reason leetcoding feels like therapy
For this particular question, I find DFS more straightforward (and also much more concise).
by far the best explanation I've seen for this problem. Thank you!!
Happy it was helpful! 🙂
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
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.
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.
I like the recursive dfs search better. Thanks!
I think neetcode mentions the directions wrong. [0, 1] -> right , [0, -1] -> left, [1, 0] -> below and [-1, 0]-> above
right
Very informative channel. I am not just learning intuition for building algorithms, but also coding in Python. Thank you very much
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
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.
Is using bfs faster for this problem? If that's the case, how do we determine when to use bfs instead of dfs?
There is a typo in the solution in neetcode, the function is named as dis instead of bfs. It is a small typo, but beginners might be mistaken.
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.
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
Much simpler: Check all 4 sides for land and set the visited node to 0
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
count = 0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == "1":
self.dfs(grid, i, j)
count += 1
return count
def dfs(self, grid, i, j):
if i < 0 or j < 0 or i >= len(grid) or j >= len(grid[0]) or grid[i][j] != "1":
return
grid[i][j] = "0"
self.dfs(grid, i + 1, j)
self.dfs(grid, i - 1, j)
self.dfs(grid, i, j + 1)
self.dfs(grid, i, j - 1)
I ain't readin all that fam
this gives an error, solution class has no attribute dfs
Hats off to the best explanation out there.
Just a small optimization, you could just modify the given grid's "1" to "0" to avoid keeping a visited set.
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.
Thanks!
Hey Shravan, thank you so much! I really appreciate it 😀
Thanks for the excellent video! Does anyone know the complexity of this?
you don't need the visited set if you alter the data of the list. you can mark "1" -> "2" to mean "visited".
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
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)
thank you, because of you i realised that i should use bfs instead of recursive dfs.
holy shit the "if r in range(rows)" is clean. never seen that before.
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.
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
Nice! A few things:
1) The checks for r in range(rows) and c in range(cols) are pretty inefficient even if pretty. I'd recommend using normal boundary checks.
2) If you can destructively change the input, you can replace 1s with 0s in the bfs and not worry about another visit occurring, which removes the need for a visit set.
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
It works better. Neet code solutions do not works anymore.
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.
Actually we can modify the items in grid "1" -> "0" to avoid using extra space.
Good point. No need to use additional space
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.
What will be the time and space complexity? Thanks
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.
This is one is pretty easy to do once you've done the pacific waterflow
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?
Beautiful clean solution and well explained. Thank you!
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
Super simple solution:
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
y_range = len(grid)
x_range = len(grid[0])
def fill(x,y):
nonlocal grid
if x >= x_range or x < 0 or y >= y_range or y < 0 or grid[y][x] == '0':
return
grid[y][x] = '0'
fill(x+1,y)
fill(x-1,y)
fill(x,y+1)
fill(x,y-1)
res = 0
for y in range(y_range):
for x in range(x_range):
if grid[y][x] == '1':
res+=1
fill(x,y)
return res
It works, But honestly found it to be very complicated the way you wrote the code.
I watched Greg Hogg's solution for this problem, that was much easier
Marking "Visited" in the grid itself is much easier.
But Thanks for the other solutions, you are doing great!
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
if not grid:
return 0
count=0
for i in range(len(grid)):
for j in range(len(grid[0])):
if grid[i][j] == '1':
self.recursion(grid, i, j)
count+=1
return count
def recursion(self, grid, i, j):
if i len(grid[0])-1 or grid[i][j]!='1':
return
grid[i][j] = '0'
self.recursion(grid, i-1, j)
self.recursion(grid, i+1, j)
self.recursion(grid, i, j+1)
self.recursion(grid, i, j-1)
Thank you very much. This taught me a lot.
But at the beginning where you asked "How will a kid solve this problem?", if that's how the kid starts, then that kid is a genius.
1,0 is below, -1,0 is above, 0,1 is right and 0,-1 is left
ty, i've improved al;ot after watching these video, ty so much
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.
cant thank you enough..I just saw it once and and it was done..very nice explanation 💯
i did this for the first time last week
i just "destroyed" the island as i visited it
setting the visited 1's to zeros before calling destroy(nextSquare)
this simplifies the code because the visited check and isIsland check become the same
also i didn't use a typical dfs or bfs
but i did recursively try and "destroy" islands in all 4 directions
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
You don’t need a queue, you can make the visited nodes as minus.
@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
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
Great solution. Please go thourgh Time and Space complexity as well
Using my own solution I get the right answer on 99% of the tests, but one of them I get 44/45. I have no idea how and in the input size is too large to go through step by step xD
Instead of creating a set of visited coordinates you could change each 1 to a 0 after verifying it's a valid spot of land. Saves space and time.
the solution in your video is different from the solution you've included in leetcode discussion. You might want to add the annotation to RUclips.
I think, i have similar but maybe simpler:
def solution(grid: list[list[str]]):
visited = set()
island = 0
def helper(row, col):
if row=len(grid[0]) or grid[row][col] != "1":
return
grid[row][col] = "#"
helper(row, col+1)
helper(row+1, col)
helper(row-1, col)
helper(row, col-1)
for row in range(len(grid)):
for col in range(len(grid[0])):
if grid[row][col] == "1" and (row, col) not in visited:
helper(row, col)
island += 1
return island
def numIslands(grid: list[list[str]]) -> int:
rows, cols = len(grid), len(grid[0])
visited = set()
def dfs(r, c):
if (r < 0 or c < 0 or
(r,c) in visited or
r >= rows or c >= cols or
grid[r][c] == "0"):
return 0
visited.add((r, c))
dfs(r+1, c)
dfs(r-1, c)
dfs(r, c+1)
dfs(r, c-1)
# visited.remove((r,c))
return 1
res = 0
for r in range(rows):
for c in range(cols):
if grid[r][c] == "1":
res += dfs(r, c)
return res
Well done nicely explained :-)
This code will help with space complexity by 90%...
def numberofislands(grid):
if not grid:
return 0
rows=len(grid)
cols=len(grid[0])
islands=0
def bfs(grid,r,c):
q=[]
q.append((r,c))
while q:
dr,dc=q.pop(0)
directions=[[1,0],[-1,0],[0,-1],[0,1]]
for roww,coll in directions:
r=dr+roww
c=dc+coll
if ( r in range(rows) and c in range(cols) and grid[r][c]==1 ):
q.append((r,c))
grid[r][c]=0
for r in range(rows):
for c in range(cols):
if grid[r][c]==1:
bfs(grid,r,c)
islands+=1
return islands
"if not grid" will return true because [[]] -> is not False
Nice explanation on the thought path! Thank you1
Really nice explanation. Can you also please explain the logic for treasure islands problems?
class Solution:
def map_island(self, i, j):
if self.grid[i][j] == "1":
self.grid[i][j] = "mapped"
if i-1 > -1: # up
self.map_island(i-1, j)
if j+1 < len(self.grid[i]): # right
self.map_island(i, j+1)
if i+1 < len(self.grid): # down
self.map_island(i+1, j)
if j-1 > -1: # left
self.map_island(i, j-1)
def numIslands(self, grid: List[List[str]]) -> int:
self.grid = grid
count = 0
for i in range(len(grid)):
for j in range(len(grid[i])):
if grid[i][j] == "1":
count += 1
self.map_island(i, j)
return count
I came here to understand the problem...Seems while explaining the first example...you skipped one 1 which is connected to the same island but is having a 0 as its neighbor...But it should be included in the same island because its vertically connected to another 1...Made me a little confused in the begining!
Same me too!
This video helped me a lot. Thanks for that!
Glad it helped!
Only 12 out of 49 test cases are getting passed. :(
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
rows, cols = len(grid), len(grid[0])
islands = 0
def bfs(i, g):
if g - 1 in range(cols) and grid[i][g - 1] == '1':
grid[i][g - 1] = '*'
bfs(i, g - 1)
if g + 1 in range(cols) and grid[i][g + 1] == '1':
grid[i][g + 1] = '*'
bfs(i, g + 1)
if i - 1 in range(rows) and grid[i - 1][g] == '1':
grid[i - 1][g] = '*'
bfs(i - 1, g)
if i + 1 in range(rows) and grid[i + 1][g] == '1':
grid[i + 1][g] = '*'
bfs(i + 1, g)
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
grid[i][j] = '*'
bfs(i, j)
islands += 1
return islands
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
I think the flood fill algorithm is faster than BFS or DFS approach in this problem and It also requires less memory :)
Brilliant Explanation!
Is the time complexity O(2 N^2)?
SIR please do a video on printing all substrings of a string in O(n)..or less than that .. please sir ..
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.
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
bro Neet, could u tell the time complexity of this solution, pls?
Really nice explanation. Thanks man
Get outta here! This is such a smooth explanation of a question that truly intimidated me before!
How about we just mark the visited land in the grid itself, and while traversing if we reach a visited land or if it is water then skip computation, in js I would write it this way:
(I'm marking visited land with "2")
var numIslands = function(grid) {
const traverse = (i, j) => {
if (i < 0 || i >= grid.length || j < 0 || j >= grid[0].length || grid[i][j] === "0" || grid[i][j] === "2") return;
grid[i][j] = "2";
traverse(i + 1, j);
traverse(i - 1, j);
traverse(i, j + 1);
traverse(i, j - 1);
}
let numberOfIslands = 0;
for (let i = 0; i < grid.length; i += 1) {
for (let j = 0; j < grid[0].length; j += 1) {
if (grid[i][j] === "2" || grid[i][j] === "0") continue;
traverse(i, j);
numberOfIslands += 1;
}
}
return numberOfIslands;
};
Thanks for the awsome video. Could you please solve this one :694. Number of Distinct Islands
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
I failed to answer this question at my Google interview yesterday 😅
How do I know when the problem is iterative or recursive?
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.
BFS is nice and all, but no longer works for this particular problem.
Try testing this grid:
1 1 1
0 1 0
1 1 1
Should get 1, but instead getting 2 in results.
Looks like LeetCode have updated tests, so above solution is no longer valid.
Spent a good hour and half trying to figure out why BFS has been invalidated.
DFS approach seems to be the way to go.
yeah even I am wondering why it doesn't work anymore
I tried this problem with bfs and realized I was getting the wrong solution because I was checking if (row/col - 1 > 0) instead of (row/col - 1 >= 0). If you make the mistake I did it completely skips the bottom left cell (2,0) because when the cell (2,1) checks for neighbors, the value of (col - 1) is equal to 0 and because our condition is strictly greater than 0 it doesn't add that cell to the queue.
absolutely love this channel
Such a beautiful explanation! Thank you!
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
This is simpler, faster and consumers less memory.
class Solution:
def numIslands(self, grid: List[List[str]]) -> int:
def recursive(grid, i, j):
grid[i][j] = '0'
if i > 0 and grid[i-1][j] == '1':
recursive(grid, i-1, j)
if i < rows - 1 and grid[i+1][j] == '1':
recursive(grid, i+1, j)
if (j > 0 and grid[i][j-1] == '1'):
recursive(grid, i, j-1)
if (j < cols - 1 and grid[i][j+1] == '1'):
recursive(grid, i, j+1)
rows = len(grid)
cols = len(grid[0])
count = 0
for i in range(rows):
for j in range(cols):
if grid[i][j] == '1':
count += 1
recursive(grid, i, j)
return count
Amazon doesn't like this solution. Because when you do grid[I][j] = '0', you're destroying the data.
@@yass1415 what does that mean?
@@Ahmed-vn6fd grid is provided parameter . So he means you should not change it.
Using q = deque() or q = collections.deque()? My question is that is there any difference between theses two? When shall we decide to use one instead of the other?
I think they're the exact same,
@@NeetCode Many thanks!
what is the time complexity?