Shortest Path in a Binary Matrix - Leetcode 1091 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem shortest path in a binary Matrix given an N by n Matrix so note that this is a square Matrix that's not like a major point but we will come back to that later it's a binary Matrix so every value will be either a 0 or a one we want to return the length of the shortest clear path in The Matrix if there's no clear path then return negative one so this is a classic situation where there's a phrase that has some explicit meaning to it and they Define the meaning down here a clear path is a binary Matrix from the top left to the bottom right in this case it's small grid so not much going on but it could be a much larger grid something like this and we'd care about the top left which is zero zero and the bottom right is our destination so we're starting here and we want to end up down there down there is defined as being n minus 1 n minus 1 because because it's a square Matrix now about this path itself what's so special about it well first of all we can only visit zero values let's consider the ones as obstacles so we're not allowed to visit those one values the interesting thing here is that we can actually move in eight directions so not just up down left and right but we can actually move diagonally as well that's pretty unusual for graph problems but it won't make things super complicated not much more complicated than if we could just do it in four directions so we want the length of a clear path and a small but important point is that the length of the clear path is the number of visited cells so if we went like diagonally like this or if we just went from here down to here that counts as a path of one which I think makes sense so we're not like going by the Manhattan distance where you know this would be a path of two we're just saying that this is one now what we want to return is of course course the length of the shortest clear path so this is pretty much a shortest path problem the good thing here is that our graph is a grid but it doesn't have any weights to the edges the edges even though we have eight of them so for every position here we can go in eight directions we don't care about the weight of the edge so it doesn't cost us anything to move diagonally or vertically or horizontally it doesn't matter so we just want the shortest path now the easiest way to do a regular shortest path this isn't like dixtra's algorithm is just to do a basic breadth first search where we maintain the distance think of these as being obstacles and stuff we want the shortest path to get to the result let's make it interesting like that so we start here and actually before I even get into this let's consider a very very simple example where we're given a one by one grid where we basically start at the destination What would we say is the length of the Shore's clear path in this case while we're going by the number of nodes or positions that we're visiting so actually the return value for this would be one we say the shortest path length is one knowing that we're basically saying to start here it takes us a path of one now where can we go if we move one position we can't go up can't go there can't go anywhere over here we can only go bottom right if it took us one to get here let's say it takes us two to get here now from here how many other places can we go to we can actually go in three directions we can go here or we can go here or we can go here now these are kind of dead ends we can't really go anywhere from there but from this guy we can go in one other direction to four here and then from here we can only go in one other direction so it took us five moves to get to this spot and then finally we end up at the destination it is a shortest path of six so six is what we would return you can think of this as being like layer by layer this is our first layer this is our second layer this is our third layer this is our fourth layer fifth layer and then sixth layer so we return six if it's impossible to reach the goal which would be the case if we were like blocked off like this or something then we would just return a default value of negative one now what is the time complexity well BFS is a pretty standard algorithm the time complexity is basically going to be the size of the grid which in this case we know is N squared so that is the time complexity and we're doing breadth first search so we are going to need a q data structure which the size of that the max size will probably be of N squared because we might have the entire graph loaded into that okay so now let's code it up so the first thing I like to do is get the dimensions of the Grid in this case it's pretty simple because we have a square grid so I'm just going to say the length of it is n and I'm also going to initialize a few data structures that we usually need for BFS one is a Q and the other is a hash set for keeping track of which positions we've already visited so we don't get stuck in an infinite Loop and generally how we're going to code this up is while the queue is non-empty we're going to pop left from the queue and we're going to keep doing that and then keep continuing the BFS until we have reached the destination now like I said we don't want to get stuck in an infinite Loop that's an important point so we're going to take advantage of our visit hash set now there's two ways to do this first notice how our queue is initially empty we should probably add the origin the top left position to the queue we can initialize the cue like this basically I'm going to initialize it with a tuple a single Tuple of zero zero so this is the row column another thing I'm going to add actually is the length for that position just to make it a little bit easier we're going to add that directly to the queue we could have a separate variable for this but that would actually complicate our while loop a bit you can try doing it that way and then compare your code to mine when you're done the third parameter here is the length so I'm going to add that and initialize that as one so we know that to get to the origin we call that a path length of one so when we pop from the cube we'll be popping three values we'll be popping the row the column and the length it took us to get to this position now another point is how do we initialize our visit hash set when we add a position to the queue do we consider it visited at the time that we add it to the queue or at the time that we pop it from the queue I prefer to do it as we add to the queue so I'll say that 0 0 has been visited you could do it the other way I think it's just slightly less efficient not in terms of Big O time complexity I think it's the same because we can only go in eight directions but what I'm getting at is that there are variations of how you could end up implementing this and all of them are pretty much fine now a very important thing about this position is we want to make sure that it's valid we haven't gone out of Bounds at this row column position how do we know that well if our row is less than zero or our column is less than zero we know we've gone out of bounds an easy way to check this is to actually just take the minimum of the row and the column and check is that less than zero if one of them is less than zero that's all that we really care about or if we've gone out of bounds the other direction is the row greater than or equal to n or rather is it just equal to n or is the column equal to n and since this is a square grid we can actually take the max of the row column if one of these has gone out of bounds that's all we really care about so if this is greater than or equal to n or you could just say is it equal to n both of them would work then we know we've gone out of bounds and if we go out of bounds then we don't want to do anything with this position now another possibility is that or this has already been visited which means our row column is in visit and the third possibility is that this position is blocked how do we know that well we take the Grid at this position at this row column position and is it equal to one or we can just you know check if this evaluates to true in Python I'm going to wrap this in parentheses if any of these is true we basically want to skip this position so I'm just going to say continue to the next iteration of the loop now if it is valid it could be that we've reached the result how do we know that well if rho is equal to n minus 1 and column is equal to n minus 1 that means we have reached the result so what are we going to return well we want to return the length and thankfully we have the length that it took us to get to this position so that's what we return the third and final thing is and this is important we want to go through all of the neighbors of this position how do we do that we know that there's eight directions you could write out like eight statements here I think an easier way to do this is to define a helper variable I'm going to call it direct short for directions and I'm going to Define all eight directions one of the directions is 0 1 I believe that would be moving to the right and then another direction is going to be one zero I believe that would be moving down but at this point you don't even need to you know turn your brain on you can just kind of turn your brain off and just start copy pasting and then just do all variations of these but we're going to do negative one here we're going to do negative one here and this is a little bit more tricky than just doing four directions because we actually have a few other cases to worry about like one one where I think moving a down right and we also have negative one negative one and we also have positive one negative one and we have negative one positive one so those are all eight directions now we're going to go through them the direction of the row the direction of the column in our directions what we want to do with this is append it to the Q 2 so we'd append the row plus Dr C plus DC and the length it took us to get to this the length it took us to get to row column was this so to move one more spot it's going to be length plus one also we would want to mark this spot as visited we can do that like this R plus the r c plus DC the only problem with this is that we're appending every single neighbor it's okay if we append some neighbors that are out of bounds because we have a check for them here it's okay if we append a position that has an obstacle because we're checking for that here but what's not okay is that first of all we're marking this spot as visited because then this is always going to execute so we don't actually want to do this but at the same time we don't want to visit nodes that we've already visited before so to fix that actually we're going to guard this statement by checking that row plus Dr and then C plus DC is not in visited this spot has not been visited then we only add it and I want to continue discussing this because I think this is how a lot of people can get tripped up there is a bug here notice how when we started things we said that anytime we add something to the queue we mark it as visited we have to be consistent we do have to add this position as visited so I'm going to go ahead and do that so we do have to do this so then what about up here well we can't put this here it's okay if a node has been visited we still need to process it and we make sure that we don't process a node multiple times because before we add a node we make sure that it hasn't been visited every node will be pushed to the queue once and then popped from the queue once we'll never visit a node multiple times this way and that's kind of the logic and reasoning behind everything since we're not guaranteed to find a solution if we end up visiting every node and and we don't end up executing this return statement then by default we return a negative one value now let's run this to make sure that it works of course I had multiple or statements I had one down here and one up there as I was erasing the other statement so let's just go ahead and get rid of that and then rerun things and as you can see it works and it's really efficient if this was helpful please like And subscribe if you'd like to see the code and languages other than python check out neatcode.io it's got a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon