Count Sub Islands - DFS - Leetcode 1905 - Python

[@NeetCode]

💡 GRAPH PLAYLIST: kzbin.info/www/bejne/e5isZqGLbsqnpLc

[@neeravjain805]

Man the amount of confidence I have after solving all your graphs question is insane, thanks a lot for the videos

[@saiachyuth3460]

One improvement - instead of using a visited array to keep track of the visited indices , we can just make grid2[i][j] = 0 whenever we visit the cell so that we will not visit it again.

[@duduimpact5321]

What if you were told that you were not allowed to modify the grid?

[@ale-hl8pg]

@@duduimpact5321 I don't think the input is completely immutable in most problems, you could set it to 2 instead then just reset all 2's to 1's afterwards, thus you'd restore the input Definitely still an issue if you're dealing with multithreading though

[@danielsun716]

class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: rows, cols = len(grid1), len(grid1[0]) visit = set() def dfs(r, c): if r < 0 or c < 0 or r >= rows or c >= cols or (r, c) in visit or grid2[r][c] == 0: return True if grid1[r][c] == 0: return False visit.add((r, c)) return dfs(r + 1, c) & dfs(r - 1, c) & dfs(r, c + 1) & dfs(r, c - 1) count = 0 for r in range(rows): for c in range(cols): if grid2[r][c] == 1 and (r, c) not in visit and dfs(r, c): count += 1 return count In python, x and y means if x if False, return x. otherwise, return y. So only if x is True then y can be executed. x or y: if x if True, return x. otherwise return y. That means if x is True, y will not be executed. So in the dfs(). we can only use &. Cause it is the bit counting. if we use and, what will happen? In this problem, grid2 = 0: True grid2 = 1: 1) if grid1 = 0: False 2) if grid1 = 1, put in visit So if we use "and", if the first dfs(r + 1, c) meet grid1[r + 1][c] is 0 ( sea portion), then it will return False. Then the last 3 dfs() will not be executed. But actually we can still go the others' directions. In conclusion, if you want to use "AND", then you had better save the result of each dfs() in a variable, or you can use"&"

[@vxprz-5295]

oh my god, ive been so frustrated trying to figure out what was wrong with my code, and why have the dfs before the "And" got the correct solution. Thanks so much

[@MattLevine-bq2vb]

Can someone please explain why in this example you need to move the addition to the visit set below the check for the 0 in grid1 instead of above?

[@BharCode09]

You break down the problem very well and solutions though optimised, you explain it in pretty simpler way. But one small add on. Why should we use DFS than BFS? Not bcz DFS is simpler. In many cases DFS performs better if we are not exploring all the options(branches/Neighbours ) extensively. Here, since they say, there is only one Island, DFS is a good option. But in other problems, which kind of tries to seek a shortest path or best of all routes/solution, we better chose BFS. And which traversal we chose and its trade offs, itself is a pretty serious question or discussion point in the coding interviews.

[@fatropolis6909]

Hey man, what do you mean by “since they say there is only one island”. How do we know to choose DFS because of that?

[@adithyagowda4642]

It doesn't work if you swap the places of the recursion call and 'res'. For example writing "res = res and dfs(r+1, c)" instead of "res = dfs(r+1, c) and res" (and doing the same for other 3 calls too) doesn't work. I am scratching my head to find the reason. What if I code the answer correctly in an interview but couldn't come across this trivial error which I cannot think of? That would be a horrible situation.

[@NeetCode]

I'm glad you asked because I had the same issue at first. There's an interesting fact about how conditional statements work in python. Ex: "If X and Y()", if X is true in this case, Python wont even execute the second conditional, meaning that the function Y won't even be called. This is the reason in my code I called the function first, to make sure it gets called.

[@adithyagowda4642]

@@NeetCode Damn that's true yeah. Almost forgot it haha. Thank you very much for replying. Your videos are super helpful and so are your comments.

[@justinejose5111]

@@adithyagowda4642 you and @neetcode saved my life. I have been scratching my head for quite some time now.

[@adithyagowda4642]

@@justinejose5111 No problem mate. I'm glad you got what you were looking for.

[@justinejose5111]

@@adithyagowda4642 another question though, when I tried to do this locally, it called Y() even if X was True. Have you checked this one?

[@nikethdonthula2123]

Great Explanation 🔥

[@shivamrawat7523]

why res stored in the variable and not returned there itself? if its false what's the point of calculating further?

[@wenqianghu1352]

@NeetCode Just found out that, it makes a huge difference if you write the recursive steps as the following. You wouldn't get the correct answer in this way. I don't know why. Would someone be able to answer it for me? res = res and dfs(r, c + 1) res = res and dfs(r, c - 1) res = res and dfs(r - 1, c) res = res and dfs(r + 1, c)

[@manehdarbinyan]

The issue arises from the lazy evaluation of the `and` operator. In the expression `A and B`, if A is false, B is not evaluated because the result is already known to be false. Similarly, in `res = res and dfs(...)`, if res is false the dfs function will not be called, preventing the algorithm from exploring all necessary paths and potentially leading to incorrect results.

[@c_hlee]

I just struggled so much with this too. I was trying to do "return dfs and dfs and dfs and dfs and res" ... which also did not work

[@Bullimicporkupine]

python gets 1 False and will not run the remaining of the expression. also had to find this out the hard way

[@aniketjain3101]

Wow excellent explanation! Keep the good work Up!

[@CS_n00b]

Why are we returning true if we go out of bounds?

[@charleskorey6515]

The meaning of false is we didn’t find equivalent island in first grid. If we use false for out of bounds, it changes that meaning and res will stay false even though you have a sub island in second grid.

[@CS_n00b]

Thanks Charles

[@hemesh5663]

@NeetCode could you please explain to me why we are not returning as soon as we are getting grid1[r][c], if we hit the condition then we can say that we cant form a sub island so why are we doing the way you do. Please could you explain it?

[@ChanChan-pg4wu]

You want to transverse that whole island and add them to the visit set. Otherwise, we could visit part of that island again in the main loop.

[@chih-weiyang5988]

​@@ChanChan-pg4wu It's the answer I am looking for. Thank you

[@dheepthaaanand3214]

And if we visit the remaining part of the island from the main loop and match every cell to the parent, we'll return true, because the remaining portion was visited already so it'll count as a boundary true condition. When in reality it should be false for the whole island

[@kirillzlobin7135]

Amazing video

[@bhawnapatnaik7903]

Why is the third land in the second grid not a sub-island?

[@NagashiChidorii]

same question i have. He did not explain it. My problem is shit like this that messes me up on the code because it doesnt make any sense and will stop me from solving ALL cases

[@thecuriousengineer]

All the cells of an island in grid2 need to be subset of an island in grid1

[@algorithmo134]

@NeetCode Can we return straightaway after we encountered a False case instead of going into more dfs since True and False or False and False will result in a False at the end?

[@dheepthaaanand1133]

My understanding is - We would anyway have to do dfs of those coordinates as the dfs is not just for returning a value but also for exploring a coordinate, so we are doing it recursively; had it not been done there, it would have anyway been covered in the for loop below

[@vedantravialimchandani3424]

Why can we not use BFS traversal instead of DFS? I tried but it's giving TLE. Does anyone know the difference?

[@algorithmo134]

Hi NeetCode can you do 629. K Inverse Pairs Array?

[@nikhilgoyal007]

Hi! Can someone pls explain why are we returning True when going outside of the range in grid2 (line 7). I understand it should not be a False and loop should continue but return True seems to suggest a successful subisland has been found which might not be the case after all ?

[@infiniteloop5449]

One readability optimisation: instead of ANDing res and reassigning it, you could just use the All function in Python on all 4 directions at once, if any of them return false the whole thing is false.

[@moosegoose1282]

if i was given this i am walking out to prevent embarassing myself

[@minciNashu]

Most variations of the island question come down to flood fill For example this question seems like the original count islands question, with the minor tweak of double checking nodes in both grids instead of just one grid. With that being said, back in 2018, when I didn't even know what leetcode was, I failed the count islands question.

[@c_hlee]

I'm having a really hard time wrapping my head around Python's lazy evaluation happening in this problem. I haven't faced issues with lazy evaluation doing any other leetcode problems until now.. ##### Works res = dfs(r-1, c) and res res = dfs(r+1, c) and res res = dfs(r, c-1) and res res = dfs(r, c+1) and res return res ##### Does not work res = res and dfs(r-1, c) res = res and dfs(r+1, c) res = res and dfs(r, c-1) res = res and dfs(r, c+1) return res ##### Does not work return dfs(r-1, c) and dfs(r+1, c) and dfs(r, c-1) and dfs(r, c+1) and res ##### Does not work return res and dfs(r-1, c) and dfs(r+1, c) and dfs(r, c-1) and dfs(r, c+1)

A bit late but... to correctly traverse the entire grid (and islands), you must call dfs on all neighbors. With lazy evaluation, if res == False, then dfs won't be called and that part of the grid won't be traversed.

[@chelsylan8554]

easy to choose to return False when it's not the sub-island... thanks for explaination

[@remixowlz]

Hi, what is time complexity of this algorithm?

[@charleskorey6515]

O(m*n) where m=number of rows and n=number of columns

[@poptart007-b2r]

omg "res = dfs(i+1,j) and res" and "res = res and dfs(i+1,j)" are not equivalent :() I pulled my hair for like half an hour trying to find what was wrong with my code xD

[@shaharyar.khalid]

I pulled all my hair out as well !

[@ChanChan-pg4wu]

If the 1st part (res) is False, the 2nd part of the code will not execute. Really tricky. I have no hair to pull already.

[@arijaa.9315]

Why this does not work then class Solution: def countSubIslands(self, grid1: List[List[int]], grid2: List[List[int]]) -> int: ROWS, COLS = len(grid1), len(grid1[0]) visit = set() def dfs(r, c): if r not in range(ROWS) or c not in range(COLS) or (r, c) in visit or grid2[r][c]==0: return True visit.add((r, c)) res = True if grid1[r][c] == 0: return False directions = [(-1,0), (1, 0), (0, -1), (0, 1)] for rd, cd in directions: res = dfs(r+rd, c+cd) and res return res count = 0 for r in range(ROWS): for c in range(COLS): if grid2[r][c] and (r, c) not in visit and dfs(r,c): count += 1 return count

[@arijaa.9315]

@neetcode please help

[@abhinavgupta7048]

Please someone check my code shows memory limit exceeded when solved using bfs approach and it gets solved using DFS approach can anyone please why is this happening? class Solution { public: void bfs(vector grid2,vector& grid1,int& temp,vector& isVisited,int i,int j,int m,int n){ queue q; q.push({i,j}); isVisited[i][j]=1; while(!q.empty()){ int row=q.front().first; int col=q.front().second; if(grid1[row][col]==0) temp=1; q.pop(); vector dis={{1,0},{-1,0},{0,1},{0,-1}}; for(auto i:dis){ int newRow=row+i[0]; int newCol=col+i[1]; if(newRow>=0 && newRow=0 && newCol

[@code_school6946]

This is not working