SHORTEST DISTANCE FROM ALL BUILDING | LEETCODE 317 | PYTHON BFS SOLUTION
Vložit
- čas přidán 26. 07. 2024
- In this video we are solving a very tricky Google interview question dealing with traversing a 2D matrix: Shortest Distance From All Buildings (Leetcode 317).
This question follows a familiar BFS solution pattern but implementing it is very tricky and we have to be very careful to get the details right because otherwise our solution won't work.
TIMESTAMPS:
00:00 Intro
00:21 Question Prompt
01:10 Example & Solution Intuition
09:36 Coding
20:00 Time/Space Complexity
22:00 Outro - Věda a technologie
"I don't know who will kinda like to ask this bullsh*t" 🤣😂😂you made my day. Thank you! The best explanation for this problem!
I was actually asked this question when I interviewed for x the moonshot factory an Alphabet company. I wasn’t able to solve it that time and was rejected. Thanks for making this video.
Many people comment that this explanation is excellent but think the solution to this question is poorly explained.
The key to solving the problem is the empty land.
While exploring the grid, if there are buildings we cannot reach, we won't be able to mark the empty lands adjacent to unreachable buildings.
So when exploring unreachable buildings, we won't find any empty land. For example, if EMPTY == -1, We won't be able to mark the unreachable buildings as -1, so their empty land ID will remain 0.
That is why if there are unreachable buildings in the grid, we won't be able to find any empty land, as there will be no empty land with that id at the end. That is why the minimum distance will remain float('inf').
English is not my first language, but i hope this answers the question about the local distance and minimum distance.
that's true, I did not understand why we need to flip the cell to -1, -2, etc until I hit an edge case in which there's no house that can reach all buildings.
thank you for this video!! the concept of the solution isn't hard to grasp but it's so hard to code up in practice lol i kept writing bugs. finally was able to understand and code it up by following your solution.
The coding part makes the problem so much clearer, thank you for your effort! From the description it's so confusing on how to approach it
No problem! Admittedly not one of my best videos because it's really one of the harder ones you can get and it's quite tricky to wrap your head around...even if you have the solution in front of you
I just went through the matrix again to get the minimum and used the negative value to judge whether it has been visited by all the buildings or not:->
for(int i=0;i
One advantage of defining local_dist like this is that if we start from a building and we cannot reach the land then ans will stay float("inf") and we can return -1. For example grid = [[1, 1], [0, 1]], the top right building cannot reach the land and the answer should be -1.
won't the other buildings overwrite the min_distance? coz their local_dis would be reachable.
Found the answer for this - essentially from your example, when we kick off a bfs from top-right building, it updates the LAND variable to -2 (assuming the top-left already updated LAND=-1) without updatin grid[0][1] to -2. So any subsequent building doesn't reach that cell (even though it was a land) ever again signifying that grid[0][1] is unreachable. That is why local_dist and min_distance both remain float('inf').
In other words, the LAND variable and the "lands" in our grid should go hand in hand to indicate reachability. Hope this makes sense.
Thank you for this explanation, I have the same question after watching the video and glad to discover you have put a solution here@@chiragkamat4887
@@chiragkamat4887 Thank you for your explanation. The min_distance is overwrite when we start a new building.So grid[0][1] will change the min_distance to infinite number.
new youtube UI, yikes... new video on the channel, poggers!!!
Would you mind attaching the link to the LC problem? There is nothing extra hard about taking ID and searching it on LC, but would be faster to dig into the problem when you see a new video (yeah, it's me, I am basically taking the problem from the video and trying to crack it myself before I watched the whole video :D )
Sure I can start doing that going forward. I’ll put it in the description of the video
Thanks
nice explanation 🙂
Thanks, glad you found it helpful. This one is quite tricky to explain
Hi, a little question about local_dist, should the final ans,min_dist be update only when we get all of houses that we update the answer, right? So if each time queue is empty, we update min_dist=local_dist, won’t there be any problem?
Tried using manhattan distance than went to BFS but i think my distance checks were a bit off I was loading all homes onto the q at once and doing layers from there lol. This one is a beast thanks for sharing I will be ready for when google asks this one
Intuitively this one makes sense it’s just coding it is tricky and explaining it is even worse
Great explanation thank you
Thanks glad you enjoyed it. Hope the explanation made sense. This is one of the questions where it makes sense in my head but explaining it always trips me up
@@crackfaang Naah you killed it!!
Great explanation! Also, what is the point of using min_dist if you are not doing anything with it? It's just being assigned to local_dist, you could just return local_dist
Thank you for your effort. There is just one point that stucks me. What about one empty room is not available from one friend's house? Should we still return the answer or -1
@edwinrosemond989 Thank you. You have solved it already
I may be thinking about this wrong but what if a house is isolated and can't reach any other houses. In this case min_dist is going to update to some small value, if it sees any 0, right/ How does min_dist track that that cell can reach every house?
nevermind, the empty_land won't decrement the 0 and so proceeding 1's won't be able to see it. really cheeky!
@@edwinrosemond989 yes! this part also tricked me. i tried to use a visited set but it didn't work
code link?
not hard
Very hard