Just fyi for others, be careful when visiting neighbors if your dfs return boolean instead of count like here. E.g: boolean dfs(grid, r, c) { …code here.. return dfs(grid, r+1, c) && dfs(grid, r-1, c) && ..the rest here..; } Doing this way will make you stop early and only half the island is visited. When the main for loop reach the unvisited part of the island again, the result will be wrong.
We can also run the loop from 1 to row_len - 1 and 1 to col_len - 1. Because the land cells in the boundary are never going to be a part of the enclosed islands since minimum one side is boundary.
You can alternatively use the bitwise AND operator (&) to combine the dfs statements, assuming it returns False when OOB and True otherwise. Reason: if using "and", once you encounter the first dfs statement and it's false, the remaining dfs statements won't be executed (short-circuit), which will misrepresent the visited grids in future iterations of grid.
I like this person, because he is not a human being 😅😅😅HE REALLY FROM ALIENS 👽👽👽 WORLD 😅😅😅😊😊😊😊(REASON: IF I WATCH SAME PROBLEM IN OTHERS UA-cam CHANNES LIKE 10000 TIMES I CANT ABLE TO UNDERSTAND,SO ALIENS ONLY CREATE WONDERS).SIR PLEASE SUGGEST ME HOW TO BECOME LIKE YOU??? DEFINITELY HARDWORK MATTERS,OTHER THAN THESE??
I just don't get why the time complexity is only O(n*m) once you have two nested for loops and additional recursive calls inside of them, wouldn't you have to consider the time complexity of the recursive calls either?
what about the case when there's water inside the land? we're exiting in that case and will run remaining set of land points, resulting in 2 counts for same island?
I just found the reason for this. It's because in the case where you're ANDing all of these traversals, python will stop if it reaches a false condition, whereas you want to go forward with the entire traversal no matter what. The way to do it is to have each statement execute (perhaps set it equal to four variables and then to return the and of those four variables).
@@atishayjain3011And why do we want to visit each cell. If we don’t visit some branch in this iteration, it should remain unvisited and we should cover it when we reach this cell from outer for loop. We would still iterate each cell once only. So, why is this an issue
Thank you so much for this video, very helpful! :) Just out of curiosity: is there a reason why ROWS and COLS are written in capitals? Is it a convention or just a personal choice?
Because we're coming back to a piece of land on a grid we've already visited, that means we haven't encountered land on the edge of the grid along that path.
love the daily leetcode problem vids
Just fyi for others, be careful when visiting neighbors if your dfs return boolean instead of count like here.
E.g: boolean dfs(grid, r, c) {
…code here..
return dfs(grid, r+1, c) &&
dfs(grid, r-1, c) &&
..the rest here..;
}
Doing this way will make you stop early and only half the island is visited. When the main for loop reach the unvisited part of the island again, the result will be wrong.
such a subtle bug, thx dude!
Thank you for pointing this out!
If I'm able to make it to MAANG or any big tech, it would be only because of you Navi. Thankyou so much, I learn a lot from your channel.
0:46 Amogus
We can also run the loop from 1 to row_len - 1 and 1 to col_len - 1. Because the land cells in the boundary are never going to be a part of the enclosed islands since minimum one side is boundary.
You could have an island starting at row idx 1 but stretches all the way to boundary.
You can alternatively use the bitwise AND operator (&) to combine the dfs statements, assuming it returns False when OOB and True otherwise.
Reason: if using "and", once you encounter the first dfs statement and it's false, the remaining dfs statements won't be executed (short-circuit), which will misrepresent the visited grids in future iterations of grid.
I like this person, because he is not a human being 😅😅😅HE REALLY FROM ALIENS 👽👽👽 WORLD 😅😅😅😊😊😊😊(REASON: IF I WATCH SAME PROBLEM IN OTHERS UA-cam CHANNES LIKE 10000 TIMES I CANT ABLE TO UNDERSTAND,SO ALIENS ONLY CREATE WONDERS).SIR PLEASE SUGGEST ME HOW TO BECOME LIKE YOU???
DEFINITELY HARDWORK MATTERS,OTHER THAN THESE??
This solution was so perfectly explained. Thank you.
Awesome explaination as always NEET yor are GOAT of LeetCode
I just don't get why the time complexity is only O(n*m) once you have two nested for loops and additional recursive calls inside of them, wouldn't you have to consider the time complexity of the recursive calls either?
i just watched 5 mins and coded by myself .. and I did it :)
what about the case when there's water inside the land? we're exiting in that case and will run remaining set of land points, resulting in 2 counts for same island?
Great explanation
Great work on the videos and explanation!!
Hi NeetCode!
I tried the same thing but I used true and false instead of 0s and 1s. I have no idea why this turns out to not work for a few testcases.
I just found the reason for this. It's because in the case where you're ANDing all of these traversals, python will stop if it reaches a false condition, whereas you want to go forward with the entire traversal no matter what. The way to do it is to have each statement execute (perhaps set it equal to four variables and then to return the and of those four variables).
@@atishayjain3011 Thanks for the explanation and saving my time !!
Had the same issue. Thanks for mentioning@@atishayjain3011
samer here, I think if you execute False & argment_1, argument_1 won't get executed
@@atishayjain3011And why do we want to visit each cell. If we don’t visit some branch in this iteration, it should remain unvisited and we should cover it when we reach this cell from outer for loop. We would still iterate each cell once only. So, why is this an issue
For the Dfs could you also use booleans and just return Dfs in all directions using and?
Yes, that can be done too
Are cpp codes also available? If it s, can you share the same.
importance of (r,c) in visited in base case!!?
Why are we returning true for 1 which is not on the boundary?
this means, if we have reached water on all 4 direction, that was a closed island, so we are counting it by 1
can someone pls explain why do we return true if we have already visited (r,c) in the base case?
same question
can someone explain what are we doing here: res += dfs(r,c)
6 months late reply, He explains it very well at 08:29
We do that to calculate the number of loops. If dfs return 0 then no closed loops whereas if it returns 1 then we add to the result.
Thank you so much for this video, very helpful! :)
Just out of curiosity: is there a reason why ROWS and COLS are written in capitals? Is it a convention or just a personal choice?
It's sort of a convention to write constants in all caps. Makes it easier to identify them. Our company codebase follows this practice at least.
Why can we return true if we have seen it before can anyone explain
Because we're coming back to a piece of land on a grid we've already visited, that means we haven't encountered land on the edge of the grid along that path.
❤
Hey bro great content i love your channel however i used this solution and it failed so i am curious why it failed as logic is correct @neetcode
maestro
Great explanation