Unique Paths II - Leetcode 63 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem unique paths too we have solved the first variation of this problem this one is pretty similar we're given an M by n grid so this is our grid down here we are going to start at the top left position where this robot is I don't really pay too much attention to the entire story we can either move down or to the right and anytime we get to a different position it's the same we can either go down or to the right but we can only Move Along positions that are marked with a zero so any of these free positions are going to be marked with zeros but this here is an obstacle and that's going to be marked with the value 1 and that means we are not allowed to place our robot here we can't go through this position so it's like blocked off now our goal is to get to the bottom right position that's our Target position and what we're looking to do is just count the the total number of ways that we can reach that position so just taking a look at this grid how many ways are there well we can go to the right and then down that's one path and we can go this way so there's really only two paths in this grid but if we had a larger grid we could have more unique paths that lead to the Target well depending on how many obstacles we have as well if there wasn't an obstacle in this position we would have a lot more we would be able to reach the target position this way or reach the target position this way or this way or this way or even this way and this way as well so the easiest way to solve this problem is brute force and using this logic we can come up with the more optimal solution which is going to involve dynamic programming but it's not too crazy taking a look at the Brute Force solution it's best to handle this recursively so we would do it with a depth first search the main thing we'd want to pass in is is our row and column because we're here we have two choices no matter where we are we can either go down which is to take our row and increment it by one or to move to the right which is to take our column and increment it by one and then recursively what we want to ask ourselves is to count the number of unique paths starting from here what we can do is just count the number of unique paths from here and the number of unique paths from here and then take those and then add them up and then we will have the total number of unique paths from here but then the catch is how do we compute the ones from here well recursively we'd pretty much do the same thing go down count the paths from here or go to the right and count the paths from here and basically that's how our recursion would work we could imagine like a decision tree but the base case is going to be when we either suppose from here we go out of bounds too far down or maybe from here we go too far to the right that's a base case and that would return 0 there's 0 if we go out of bounds the other base case is if we actually reach the target position then we'd say one so from here how many ways can we reach the target position one what about from here how many ways can we reach the target position one so a good way to like initialize this would be to like place a one here or at least imagine that there is a one here and then our math kind of works out for all the rest of the positions and the good thing about this is that while recursively this would be an exponential solution but when we Implement caching to this caching as in any time we compute the value that goes in any of these positions we never want to recompute it because for maybe this it's pretty simple we just look down and then we can get the value here but for somewhere like this there might be multiple paths and we don't have to re-treverse those paths recursively so we do caching to eliminate repeated work so we'll have like a two-dimensional DP grid that's the same size as this I usually use a hash map but it's up to you this will though lower our time complexity instead of being exponential we'll just be the size of the grid which is n times M that's also the amount of memory we're going to need for this DP solution so let me quickly show you the recursive solution but there's actually a way to optimize the memory to get this to actually be Big O of n or you could get it down to a big O of M but basically like one of these rows is the memory that we need and that's like the true dynamic programming solution so I'll show you that afterwards so this is the recursive solution I'll go through it pretty quickly the first thing I like to do is just get the dimensions of the grid so m is the number of rows n is the number of columns and then I'm using a hash map to use as our cache so what I did is exactly what I said in the drawing explanation I'm basically initializing the bottom right position to be one because we know that's kind of our base case but this wouldn't necessarily be required and you could have instead used like a two-dimensional grid that's M by n but I just like to use the hash map for recursive problems we're passing in the row and column into our recursive function because this function is defined in the outer function we already have a reference to our DP cache and to these variables as well so I'm not passing them in and there's a few base cases here one is if we go out of bounds so if our row becomes equal to M or our column becomes equal to n then we want to return 0 immediately the third case is that the grid position is blocked we know if this value is a one then it's blocked we can't Traverse through there so we would return 0 in that case that's the number of unique paths the other case is that we've already computed the value at this position so this is already in our cache this key is in our DP hash map so we would return the value that was already stored there now if that's not the case that's where we actually do our recursion here so counting the paths at row plus one counting the paths at column plus one adding them together storing them in the hash map and then returning that value and then finally to get our result we just call DFS starting at the top left so now to actually understand the true dynamic programming solution which can be really helpful for more difficult problems I would say this is one of the more easy two-dimensional dynamic programming problems so it's a good example to practice on so let's talk about the real dynamic programming solution and let's consider this same example over here even though it's a pretty simplified one it will still get us all the information we need even our caching solution is basically Computing all the values that go inside of this grid to eventually get us the value at the top left of the grid so the idea behind dynamic programming is that we can compute these values bottom up instead of doing them recursively instead of trying to compute this one first and then that leads to the sub problems we can immediately start with the sub problems and then compute them in such an order that we can eventually arrive at the ultimate solution so that's exactly what we do we start at the bottom right and then fill these values in in reverse order to get us the top left value but some people do it the opposite way some people don't like to Traverse arrays in reverse order and then the rows in reverse order as well the interesting thing about this problem is that it's symmetrical in that if you count the number of paths starting from here to the bottom right that's the exact same as counting the paths from the bottom right up to the top left so you can do it the same way that you want to you can do from top right to left or you can do like bottom up like I'm doing it's up to you I prefer to do it bottom up because that kind of preserves like the context of the problem because in the context of the problem we're allowed to go down and to the right so if we kind of do it the opposite way we'd have to consider us going either to the left or above but that's a pretty small point now to actually start filling in the values we know that the bottom right is always going to be a value one so we can just initialize it like that and let's just mark this spot just to indicate that we have an Ops here but we still need to fill the value in going in reverse order so what value would we put here well we want to add the value to the bottom and the value to the right and when we go out of balance here we can just assume that the value is zero as like the default value so then the value we'd put here is one what about over here same thing go to the bottom and to the right so we put a 1 here what about over here same thing we go bottom that's a one when we go out of bounds to the right we also assume there's a zero here so we just put a 1 over here and then here when we get to the obstacle we just want to skip it so we just either leave a zero here or put a zero if there's not already one and we just keep going like that so from here we'd get a one and here we'd have a one and then finally at the top left position we'd look down look to the right add those together we'd get a two that's the result that we're looking for so it's really that simple but the way we coded this up we have the entire Grid in memory but it's actually not required we don't need to have this n by m Grid in memory because if you notice something every time we look for a value suppose this one what we would do is look to the bottom and look to the right anytime we're Computing a position we only need the previous Row in memory by the time we get up here and we're trying to fill these values in we don't really need this Row in memory anymore we just need the previous row then you think well we only need at most two rows in memory but actually we need even less than that we only need one row in memory let me show you what I would do we have these values here I'm going to show you how to fill these values in if we were doing it in place so how would we get the value here well we'd look bottom the value that's already stored here and look to the right so it's one plus zero so then we'd put a one here but what I'm going to do is actually place it over here because my argument is that once we compute the value here we actually don't need this value to even be in memory so let's just assume that this value actually is taking up this spot but I'm just illustrating to you that this doesn't matter anymore we're never going to use it again we only need these three values basically the size of the row and now to get the value here well it's an obstacle so it doesn't matter anyway so we'd put a zero here once we put that 0 here we would never need this value anyway and then finally when we get to this position we want to look to the bottom because we want to know how many paths we can get going down and we want to look to the right because we want to know how many paths we can get going from the right but in reality these values are still going to be stored in this position we're not going to allocate extra memory for them so 1 plus 0 is going to give us a one here so as you can see it's possible to fill a row in in place without allocating extra memory so we just need a single Row in memory and that's the idea I'm going to use to solve this problem and I'm going to do it in reverse order but you you don't necessarily have to so what I'm going to do is just initialize the dimensions again this time I'm going to have a DP row which is going to be filled with zeros it's going to be the size of any of these rows and the last value is going to be set to 1 kind of like I did in the drawing and that will get us to the most optimal solution so what I'm going to do is then go through the list of rows in reverse order so we have M rows and I'm going to go through them in reversed order so R is going to be the index of the row and I'm going to go through every column in reversed order so we can do that just like this and there's going to be a couple cases we know the really simple case is if the value in the grid is a one then we know it is blocked off so we can't go anywhere we can't do anything so what we are going to do at that point is just say DP at this position at this column is going to be equal to zero and then we have a couple cases and then otherwise what we would do is say DP at this column is going to be equal to the value below it what's the value below it it's just going to be at DP of column because we're doing this in place remember to get the value in the previous row what we would do is just get the same value in this DP row at the same index so this is the bottom value and to get the value to the right we say add DP at column plus one so that's how we would get the value remember the couple edge cases where we go out of bounds if we go out of bounds going to the bottom well in this case that's never going to happen because we are initializing our DP array with a bunch of zeros this would never go out of bounds if we're going to the bottom but going to the right we might go out of bounds if C plus one is equal to n for the last value in our row we're going to to go out of bounds so what we can do here is First add an else if because if this doesn't execute that's when we would want to do this but also say if C plus one is equal to n that means we went out of bounds or we could say C is equal to n minus one either way that means we went out of bounds so what we're going to say is C plus one is less than n if that's the case then we're allowed to do this but if this is not true either then what we would say is the value to the right is out of bounds so we're not going to add it so the only thing we're going to do is add the value below to this well not to this but we'd say the value to the bottom plus zero is what we're going to put here but notice how that DP at of C is equal to DP the bottom Value Plus the value to the right which is zero notice how this isn't doing anything this is just like an assignment it's not doing anything so we don't need it but I wanted to explain why we don't need this but I think it's kind of obvious just looking at it so we don't actually need this else case it's not doing anything and then we just have this code which is pretty much all we need by the time this is done the value at the top left position DP of 0 will have the result so we can go ahead and return it now let's run the code to make sure that it works and as you can see yes it does and it's pretty efficient if this was helpful please like And subscribe if you're preparing for coding interviews check out neat code.io it has a ton of free resources to help you prepare thanks for watching and hopefully I'll see you pretty soon