I was having a hard time understanding this at first, too. Basically, because in the second half our q at first only holds the coordinates of where we have 0s, so we find the #s that are next to the 0s, and thus one space away. Once we do this, all the spaces that are 1 space away from a zero now contain 1 and are added to our q. The for loop continues through and looks at the coordinates that now contain 1s and looks for any #s that may be next to them, and so on. Because we are starting at the 0s and working our way up within the q we will always find the shortest distance as the further ones will not be seen when we look up,down,left,right. I'm sure there's a better way to say it, but hopefully this can help someone a little.
Hey man great video but you should focus more on the solution as opposed to explaining what parts of the code do syntatically. Anyone who is attempting leetcode mediums should already understand things like accessing an element in a 2D array.
Thank you for the explanation. While this is algorithmically correct, it may fail in large test case. Specifically, if the distance of a cell is previously computed as 35 (exactly the ascii value of ‘#’), your code will mistakenly flag it as not being computed and therefore incrementing it again (and potentially more than once due to the same reason). I suggest you change ‘#’ to either some negative number or maximum of int so this corner case will be fine. Otherwise, love the short and concise explanation!
Just a quick question - If you assign the value of mat[ i ] [ j ] to " # " , how are you able to add 1 to it in the bottom if statement. Wouldn't it be 1 + "#"
Not only do you explained it quite well, but your voice is also quite soothing, which makes the lesson enjoyable.
Great tutorial. Thanks for putting in time to help others.
Great Tutorial Man!
Thank you so much Ahmad!
Thanks for the tutorial! This helped me understand.
how does this code guarantee the shortest distance?
I was having a hard time understanding this at first, too. Basically, because in the second half our q at first only holds the coordinates of where we have 0s, so we find the #s that are next to the 0s, and thus one space away. Once we do this, all the spaces that are 1 space away from a zero now contain 1 and are added to our q. The for loop continues through and looks at the coordinates that now contain 1s and looks for any #s that may be next to them, and so on.
Because we are starting at the 0s and working our way up within the q we will always find the shortest distance as the further ones will not be seen when we look up,down,left,right. I'm sure there's a better way to say it, but hopefully this can help someone a little.
Hey man great video but you should focus more on the solution as opposed to explaining what parts of the code do syntatically. Anyone who is attempting leetcode mediums should already understand things like accessing an element in a 2D array.
Thank you for the explanation. While this is algorithmically correct, it may fail in large test case. Specifically, if the distance of a cell is previously computed as 35 (exactly the ascii value of ‘#’), your code will mistakenly flag it as not being computed and therefore incrementing it again (and potentially more than once due to the same reason). I suggest you change ‘#’ to either some negative number or maximum of int so this corner case will be fine. Otherwise, love the short and concise explanation!
"#" != 35 in Python
very clear explanation, thanks
Just a quick question - If you assign the value of mat[ i ] [ j ] to " # " , how are you able to add 1 to it in the bottom if statement. Wouldn't it be 1 + "#"
no it wont. You can see that it will only update coordinates if previously traversed coord was visited and its value was updated (from 0)
mat[ i ][ j ] always equals an int. mat[ i+dx ][ j+dy ] always equals "#" in the conditional
Nice explanation. Would it be better to solve it recursively or not?
recursion better for dfs
easy understanding)