Find the Safest Path in a Grid - Leetcode 2812 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem find the safest path in a grid and before we start I just want to say we all know that leak code difficulties are pretty nonsensical and this is the perfect example of that so I don't know who like the Leo is at leak code that is making these difficulties ass signing them but they literally don't make sense and in this video I am going to literally mathematically prove to you that this is Elite code hard but let's just first read all this mumbo jumbo which as usual is over complicated so first of all we're given a two-dimensional grid it looks like this zeros are empty ones are thieves and as usual we're going to mainly ignore like the context of this problem like who cares if they're thieves or whatever doesn't really matter to us what we want to do is we start top left we want to go to the bottom right explanation they give here is pretty long and complicated you can read it and read it if you want to but let me kind of simplify it we just want to make paths that are far away from ones we want to be as far away from one as we possibly can and it's not that simple because look down here at this third example there's two of them there's two thieves so we want to stay far away from this guy and we want to stay far away from this guy so that's the problem like if anything here is confusing to you this is what we're trying to do and I want to address a couple things here so one one thing they say here is that for any particular path for example let's look at this top one it's pretty simple this is the solution now why is it the solution because the safeness factor of this path which is basically the minimum distance from any Thief so like in this path let's get the distance for every single cell from every single thief or rather the closest Thief this example is obviously pretty simple but again we could have multiple thieves I'm trying to keep it simple with this one for now but basically we're saying that for this cell the distance between a thief is two the distance from this thief for this cell is three and by the way how did I calculate that well it's 1 2 3 so down here when they tell us that we're calculating the distance using Manhattan distance that again is kind of complicated in my opinion because we're really just looking for like the shortest path from here to there and the length of that path is essentially the Manhattan distance isn't it again let's just pretend like this isn't even there here we have four that's the distance here is three and the distance from here to the thief is two so on this path the safeness factor of this particular path is going to be the minimum among all of these values so in this case obviously the minimum is two and let's alternatively consider a different path maybe we take this path instead well I'll quickly show you that the minimum distance for that path would be Z Z because this is one this is two this is two but obviously we land on a thief so the distance you know the closest Thief is zero away obviously we could also take a different path like this one and then I think the minimum distance would just be one so what we're saying is among all possible paths every single path which one has the maximum safeness factor I think these types of problems are confusing when you have minimum and maximum in the same problem description it can get confusing so I want to really clarify what they're asking for basically like I said earlier we want to just stay as far away from thieves as possible and we want to find the path that allows us to do that and then return the safeness factor of that path in this case it happens to be two okay now we finally know what the problem is asking of us so now comes to actually solving this problem I want to mention a couple things like first I want to say that of course there is the Brute Force like at this point we kind of know this is a graph problem and if you're not like familiar with graphs I would say that don't even bother with this problem it's probably too difficult for you but if you know about graphs you know that there's two common algorithms with graphs DFS BFS okay so with DFS obviously the Brute Force approach would be just go through every single path like I showed right now and among all of them get the safeness factor and then try to maximize the safeness factor that's an approach and kind of similar to yesterday's problem it's going to be exponential it's not going to be very efficient maybe this is the best that we can do but if there is a better approach almost certainly it's going to have some greedy element to it so let's try to see can we take some kind of a shortcut do we really have to go through every path let's try to explore this and I'll just kind of spoil it for you there is a greedy approach the funny thing about this problem is it's literally two leak code problems I'll show those problems to you because actually those problems make this problem trivial but one of those leak code problems is a medium and one of them is a hard if you take two leak code problems combine them together one's a medium and one's a hard the result is not a medium right that doesn't really make sense mathematically it does not make sense why is this a medium problem either this is not a medium problem or this one is not a hard problem and I would argue that this is definitely a hard problem so please don't feel bad if you're not able to solve it so the first thing I want to do is talk about the medium problem and how it is going to apply to this problem cuz look at what we did a second ago wouldn't it be nice for every single cell if we knew the minimum distance between a thief kind of like what I showed here we we're not given this information it would be nice if we were but we're not given that information so we have to kind of get it ourselves how can we do that well this itself like I said is a leak code problem like Computing this grid here like I've kind of done I guess I'll fill in the other values this is a one I think this is a two and this is a one filling in this grid is not trivial because the Brute Force for filling in this grid would not be very efficient it would be a breath for search because breath for search is pretty good at Computing distances so I prefer to use that and it would basically be for every single cell like here do a breath for search until you reach a one and we'd go layer by layer like these are the nodes we can reach in a distance of one these are the nodes we can reach in a distance of two from this node and we landed on a thief therefore the minimum distance from this guy to the nearest Thief is going to be two okay so we do that for one cell and doing it for one cell is going to be the size of the grid like that's the time complexity of doing that it's going to be n squ if we do it for every single cell it's going to be n the^ of 4 that's not very efficient and I don't think you'll pass this problem if you try to implement it like that let me tell you there is a better way I'll show it to you right now the idea is that we don't start at every cell we only start at the thieves and from the thieves we run a breath for search so from this guy I say okay there this is one distance away this is one distance away okay this is two distance away this is two this is two okay this is three this is three Next Step this is four now we're done but this was pretty trivial there's only a single Thief what if there's more thieves well let's look at the bottom problem this problem by the way like what I'm showing you right now the algorithm I'm showing you right now is Elite code medium it's called walls and Gates and the solution for it is called a multi-source breath first search and the idea is this instead of just running breath first search from this because if we were to run breath for search from this thief we'd have to go over the entire grid we might have to do that for a second thief or a third thief or a fourth thief and at that point again we're at end to the power of four time complexity the better approach is to run bread for search from all thieves at the exact same time so this would look something like this so the minimum distance obviously for these guys is zero the neighbors is going to be one one here as well next we do two here two here two here two here here and here next we do three here three here three here and three here so this is for every single cell now we have the minimum distance from the nearest thief and we did it in N squar time and I really just want to drive home that this is another leak codee problem like this problem which is a leak code premium problem unfortunately you won't be able to solve it I think on leak code but don't worry I got you if you click this little link here you can still solve the same problem and you will realize it is literally what I just showed you right now so sorry if I spoiled it for you I mentioned that this problem that we're solving right now is two different leak code problems this is the first one this is the medium one and the other one is this swim in Rising water if I literally open up this problem to you right now you'll see it's literally the same problem we're about to solve right now and the funny thing is both of those problems that I just talked about are in the neat code 150 list so if you're wondering how was I able to know all of this that I'm talking about right now did it just magically come to me no it's literally because I solved these two problems this one over here walls and Gates and this one down here swim in Rising water back to this problem now that we have this grid remember what we're trying to do and let me kind of clean this up cuz we're going to specifically focus on this example so now that we have this grid we've transformed this problem we are now solving a different problem nobody cares about Manhattan distance anymore this is a different problem this problem is now asking us start here end over here and whatever path you end up taking try to avoid small values and try to only take big values whatever path you take try to maximize the minimum value in that path in other words that kind of sounds greedy to me basically the answer to this problem is a BFS it's a modified BFS that takes a lot of inspiration from Dix's algorithm to the point that I would just say that this is actually not a BFS this is a modified dixis algorithm which is going to solve this problem for us and let me explain that algorithm to you but like I said it's literally the same as the other Elite code problem that I talked about except I think in that problem instead of of trying to maximize it we're trying to minimize the distance the idea at this point is we're starting here we have two choices we can either go down or we can go to the right it doesn't really matter which one we take we want to pick the maximum but they're both the same in this case so we'll go here now we have three choices we can look down we can go here or we can go here remember we're trying to always maximize the value that we take so which one do you think we're going to take probably this one now we have a few more choices we can go down here and we can go to the right over here and again at this point it doesn't really matter whether we pick this one or this one for the fun of it let's pick this one at the top we pick it and now we're probably not going to choose this one so this is kind of a dead end for us now we're going to pick this one now we have a few more choices down here and to the right which one do you think we're going to take probably uh this one but at this point you kind of realize right it's not that we just have one choice or two choices we literally have 1 2 3 4 five choices and it's going to keep growing potentially so why not put all of these choices into a better data structure so that we don't have to literally iterate over all of them like if it's stored in a list for example isn't there a better data structure perhaps called a heap or priority q and in our case we're going to use a Max he because obviously we are trying to maximize the values that we pick from so just imagine all of these are in a Max Heap and then from that Heap we're going to pop the maximum in this case it happens to be three and now we're here and now I'll just kind of continue with it you probably get the idea we'll go down here and then we're going to go to the right here so we found a path now this is different than the solution path that they showed like the solution path they showed is I think this ours is slightly different ours is going like this I think but this is still a valid path because if you look at the path the minimum among all values on this path is going to be a two so that is the result so we found the result but there's just one thing I didn't explain as we were doing this you tell me how are we keeping track of the minimum distance that we have seen so far and it's kind of confusing because when you look at what I've done here this is not just one path this is the path like for example this is the solution path but there was also a cell visited over here so what do we do about that that one did not lead us to the path well this is why it's a modified Dix approach we know that Dix is a shortest path algorithm in a sense Dix accumulates values like it accumulates distances in this problem we are not accumulating anything we're not adding up the total of this path at that point it would literally be the same as Dix's algorithm but this is modified this is different we're actually paying attention to what was the minimum value that we saw so what we're actually going to do when we solve this problem problem with our modified Dias and with our priority CU our Max Heap this is what we're actually going to do let me rewind this this is our Max Heap we start at the top left we have a guy with distance three and its coordinates are 0 0 and then we pop this from the Heap and then we look at its neighbors and add the neighbors to the Heap both of them have a distance of two simple so far I think the coordinates are 0 1 and 1 0 so now these guys are also in the Heap now this is the part where it gets interesting this three over here when we add it to the Heap we're not going to add 31 one to the Heap this is not what we're going to do because when we have a path for example like this one and then we arrive at this cell what we want to know is okay we took this path to get here what is the minimum distance for this path itself we don't care about the value at this cell I mean we kind of do it is relevant but what's more relevant is the minimum of the entire path itself so what we would say is take the minimum of three and two and so what we would actually add to the Heap here is two one one and we wouldn't just do that for this in the other case for example if the value here was not a three and it was actually a one what we would do is take the minimum of one and two and then here we would add one for the distance the minimum distance to reach this cell think of it as that this value is the minimum distance to reach this cell and so now you can probably see why we're doing it this way because by the time we reach the result we will have the minimum distance it took to reach this cell it'll be two we'll have the minimum distance it took to reach this guy it'll be two same for all of these pretty much I think the only one that wouldn't be two is the original starting point three because both of its neighbors are two so it's never going to get higher than that so that's the main idea let me just spend like 30 seconds to quickly just dry run through this knowing everything that we talked about so we start here three 0 0 I'm not even going to add the coordinates just to kind of save time we started with the three okay then we went to the two neighbors and we add the two neighbors to add this neighbor since we just popped this we're going to take the minimum of three and two which is the neighbor itself obviously that's going to be two so we add two here and then we would do the same thing for this guy we're add two here it's the minimum and now suppose we go down here like we popped this guy came from down here we're going to look at the two neighbors one here and then three over there so for the one obviously we're going to take the minimum of one and two which was one and then for this guy three minimum of two and three which is two we add that and now just to kind of save time let's say we pop this we po the three even though the distance it took to reach that three is a two and then we let's say go down here push the two on here I think you probably get the idea so I'll just skip the rest of it let's quickly talk about the time comp D before we code this up so in the worst case we're never going to visit the same cell multiple times so in the worst case we'll visit each cell a single time so we'll add each coordinate to the Heap and pop it from the Heap a single time so for every coordinate that's going to be Big O of n s that's every coordinate how much does it take to push and pop from the Heap well that's going to be log n you might think well isn't it log N squared cuz we're going to potentially add every single cell technically yes but if you're familar with logarithms you know that the two becomes a constant here and then we don't really care about constants so that's how I'm getting this time complexity space complexity I think is going to be n s because we're going to have this grid that we're going to be Computing so now let's code it up um if you're curious how I was able to solve this problem I think these comments that I left are pretty much my thought process and how I was able to like narrow it down I don't know if this is going to be helpful for you or not but let's get into it I think the first thing we want to do is just get the dimension of this and it's a square grid so it's just going to be this so the first thing I want to do is basically solve that leak code medium I was talking about basically the precomputing that we're going to be doing for every single cell in the grid we want to compute the distance from the nearest Thief so we'll do that just like I talked about earlier basically a multi-source bread for search so I'm going to declare a variable that I'm going to call the Q what we're trying to do here is just get all of the thieves so that we can put them in this q and then we'll run the breath for search I'm going to say for R in range n for C in range n if this is a one that's how we know it's a thief and in that case we're going to say q. append the row the column and I'm actually going to do a third thing I'm going to also put the distance for this thief because obviously we know for this cell it is literally a thief so the distance from it and the nearest Thief is literally zero that's going to be helpful for us in the breath for search while I'm doing that I might as well just store the minimum distance for this cell and so the way I'm going to do that we could obviously use a grid so for every cell we could put the minimum distance for every like position but I'm going to just prefer to use a hashmap just cuz that's my thing that's what I do it's usually easier to declare it at least and so here I'm going to say that the minimum distance for this coordinate is going to be zero great now we run the bread for search now we say while the Q is not empty let's pop from the Q pop left and when we pop we'll get the row the column and the distance now we want to go through the neighbors of this position cuz assuming that these are thieves we don't need to store the distance for them they've already been added to the Q therefore we've already stored the minimum distance for them now let's go through the neighbors to do that let's actually declare the neighbors like the four adjacent neighbors it's going to be R Plus + one column R minus one same column same row but column + one same row but column minus one those are the four adjacent directions now we're going to do for R2 C2 these are the neighbors I know it's not like the best name but you can probably do better than me but this is the neighbor and for this neighbor we want to know if this has not already been computed if this pair is not already in in Min distance it's basically like we're using this to track visited positions so that we don't like end up doing extra work so if this is not already been computed let's go ahead and compute it let's say minimum distance for this guy is going to be and how do we do this this part well that's exactly why I stored the distance in the que because we know it took this much distance to reach this cell so to take one extra step which is all we did we only took one extra step in four different directions so the distance here is just going to be distance + one and of course we want to append this to the Q so just like this R2 C2 and the distance which is just distance plus one so it's definitely important here that you also put distance plus one because we are using that like that is what's going to be popped in the next iteration of the bread for search from this entire function all we want to do now is just return what we computed we want to return that minimum distance hashmap so now down here we can just say minimum distance is just going to be precomputing great I think there's one thing I didn't check which is we are dealing with a grid so it's technically possible that this coordinate could be out of bounds we're not going to get like an out of bounds index error since we are using a hashmap but we don't want to go out of bounds either way I'm going to write a helper function for this because we actually are going to need it again when we implement the modified Dias so I'm going to declare this function in bounds given a row and column determine if it's in bounds basically we just want to make sure that the row and column are greater than or equal to zero so I'm going to say let's just get the minimum of row and column make sure it's greater than or equal to zero and we want to make sure that neither of them are greater than or equal to n so let's just say that the max of both of them is going to be less than n so this is the helper function and now we're just going to use it down here um here so inbounds for row two column 2 and we want this to also be true before we visit that neighbor okay so now we solved the first leak code problem now let's solve the second one it's not going to be too much more code believe it or not there's a couple things we want to do to set up this modifi Dix's approach first of course the max Heap problem with python is there's no minimum Heap so we're going to need a small workaround so first of all what I'm going to add to this Heap is going to be three values um I'll leave a little little comment here to indicate that it's going to be the distance the row and the column starting with the row and column the starting position it's pretty simple it's just going to be Zer Zer the distance itself the minimum distance for that position is obviously just going to be this but the problem with python is there's no Max Heap this is going to be a Min Heap by default so to get around that we put a negative sign over here and that's going to be kind of confusing for the rest of this but that's just what we have to do in Python the last thing is we don't want to have to visit the same cell multiple times so of course we're going to have a hash set we didn't really need that up above cuz we kind of just reused this for it but now we definitely are going to need it and since we started with this position we might as well add that to the visit hash set just like this now is when we start the actual uh Dias so while the max Heap is not empty we're going to pop from that Max Heap so Heap q. Heap pop Max Heap and we're going to get those three values I mentioned up above the distance the row and the column we know that the distance though was negative so we want to make it normal again we want to turn it back into positive so let's do this first things first as soon as we land on the destination we are done like that's the point of Dix's algorithm it's a greedy algorithm so if this row column pair is equal to the destination n minus one uh nus1 then we can return what are we going to return the distance of course the minimum distance so that's what we return here and if we don't return we are going to continue with the breath for search so we're going to need the neighbors of this current position I'm just going to copy and paste it there's probably a way to reuse this but I personally don't care so I'm just going to copy and paste it and I'm also going to copy and paste the next line over here cuz that's exactly what we're going to do we're going to go through the neighbors of the current position for the Neighbors of course we want to make sure it's inbound so I guess I'll copy and paste this part too and not only that we want to again make sure it hasn't been visited just like before but this time we're going to use a different data structure we're going to say row two column 2 is not in visit so if this is the case then we're going to add this coordinate now to the max Heap and we're also going to mark it visited at the same time kind of like what we did up above so we'll say mark this as visited visit. add row to column 2 and push to the Heap Heap q. Heap push to to the max Heap a new pair of course it's going to include row two column 2 and this is probably the tricky part this is probably the part that's going to confuse you even though I think I did explain it in the drawing explanation it's not simple to understand so I don't blame you if you have to go back and Rewind it but remember what we're trying to do along the path we want to know what was the minimum distance it took to reach this cell what was the minimum distance that can include the previous cell row column or it could include the current cell because the previous distance this is the distance it took to reach this so either this is smaller or the current one that we're at is smaller Min distance of row two column 2 again I know this part is kind of confusing that's why I'm putting it into a separate line so I'm putting uh this here I guess I'll call this distance two and distance two is what we're going to push to the Heap actually I guess uh we should probably make it a negative as if there weren't enough things to worry about in this problem I guess it's only 40 lines of code but that's definitely misleading like there's a lot of thought that goes into solving this problem so yeah I'd say it qualifies as a leak code hard but I just ran it and as you can see it does work I think it is relatively efficient but you know I don't really care about the elak code run times in terms of Big O time complexity I think it is optimal if you're preparing for coding interviews definitely check out NE .io the neod 150 list I'm telling you it helps a lot there's a reason I made it because I found these problems to be exceptional and I think the problem we solved today kind of proved that but thanks for watching I'll see you soon