Paths in Matrix Whose Sum Is Divisible by K - Leetcode 2435 - Python

Key Takeaways

Hey everyone, welcome back and let's write some more neat code today. So today, let's solve the problem paths in matrix whose sum is divisible by K. A lot of divisible by K problems lately, but this is probably the more interesting one. The idea is that this time we're actually given a two-dimensional grid. We want to sort of enumerate every single path from the top left to the bottom right. And the only constraint is that we can either move down or to the right. So that's actually pretty good cuz it simplifies things for us a lot. And among each of these paths, so like we could do this or something like this. Among all of these paths, we want to track the sum and more specifically the sum modded by K. So it's not like this is going to grow arbitrarily large. Whatever this is, it's going to fit somewhere between zero all the way until K minus one. because when you mod a number that's the only possibility that you can get given that this is the mod but the number of paths themselves could be pretty big. So that's itself is going to be modded by this prime number. One thing I want to mention just like upfront is that mathematically there's no difference between a path that goes from the top left and goes down compared to going starting from the bottom right and then going up and to the left. Like mathematically they're equivalent. The only reason I'm mentioning that is because uh spoiler alert, this problem is going to be dynamic programming. And when you actually get into the bottom up solution, you have a bunch of choices for how you want to actually implement this. All of them end up being confusing. That's kind of the nature of dynamic programming. But I'm going to do it not considering this as the starting point. I'm going to keep it consistent to my top-down solution because I think it's just so easy. And I'll show you why. I I think it's so easy to take a top- down solution and translate it into a bottom up solution. It's not trivial, but I think it's like the easiest way to do it is to take one solution and translate it to the other. It's much more easy than especially in this problem where the DP grid is going to be three dimensions. So, it's very hard to visualize that. But anyways, let's get into the problem. Why is this dynamic programming? Well, it's hard to think of a solution where we're not going to have to, you know, consider every possible path given that we're literally counting them. So, the fact that it's like a counting problem is definitely one sign. Uh, but you don't have to like memorize this like after you've solved enough problems, it'll become a part of your intuition, I think. But anyways, um, that itself doesn't mean that this is DP though because it could also be backtracking. But what you'll find is that backtracking, let's call our function DFS. We're going to have three main variables. One of course is going to be the row, the current row that we're in. The other is going to be the current column. So we might be here. And the other thing is going to be the total sum. And like I said, the total sum is not going to grow arbitrarily large because we are going to mod it. That's what we're going to keep track of. Uh they specifically in the problem mentioned that the sum has to be divisible by K. So we're not going to store the sum. We could, but that would not be efficient. We're going to mod the sum by K. We just want to keep track of the remainder. So that's what I'm going to call it. I'm going to call this third parameter the remainder. You realize that uh at every step you're going to have like two choices. So yes, this could become exponentially large. And depending on like the dimensions of the grid and what K is it like the actual true time complexity might end up being exponential with respect to the dimensions of the grid. But in terms of taking this uh function and applying something called caching to it where we eliminate repeated work, what would that look like in this example? It would look something like this where to say that a function call has been repeated means that we possibly ended up at the same position. So you can imagine like in this grid there are multiple ways to end up at this position. We could have gone like that or we could have gone like that. So there's only two ways in this case. But if there's two different ways to reach here and there's maybe two different ways to reach here and there's two different ways to reach here. Then all of a sudden for this guy, there's six different ways to reach there. And then you can imagine as the grid gets bigger, it's just going to get more and more like that. So the possibilities could be bigger than they seem with just a small grid. And so it's possible that we get to that same position. And not only that, but we also have to keep track of what the remainder is. It's not enough to just say that we're at the same position again. So we're solving the same sub problem again. That's what dynamic programming is about. And since this is a hard problem, I'm kind of glossing over a lot of like the things that I would normally cover in like a medium problem. If you are new to dynamic programming or just new to leak code in general, you can keep watching this video, but I would highly recommend solving some more easy DP problems. You can check a lot of them out on neat code. I have explanations for them. A lot of them are going to be easier than this one. But if we see the exact same sub problem, only then can we apply caching. So not only do we have to visit the same position multiple times but we also have to have the exact same remainder at that position and then once we find the solution to the sub problem. So in this case that would be like um a threedimensional grid. So like for each position we're going to say here like to solve this sub problem means to count the number of paths where from here we can reach the target and the sum is divisible by k. And initially you might think well how is it possible to do that because it's not like we know what comes before but that's the point we don't know what comes before so we uh keep track of the remainder the remainder basically tells us that okay at this point we have this remainder and so based on that given that we have this remainder how many paths are possible to reach the target and so the base case in this example would be like for down here we're going to have the total remainder up until this point and then to that remainder we're going to add this value and then we're going to see when you take that and you mod it by k is it equal to zero if it is then the sum is divisible by k then we can return a positive one that means we found a path if it's not equal to zero we did not find a valid path we would return zero in that case that's mostly the idea I think behind the top down solution unless I'm missing something but the whole reason that we apply caching to this is uh Then we realize that the max number of ways that this function could be called is going to be equal to r. That's the number of possibilities that could pass in for here multiplied by c number of possibilities for this. And like we discussed the number of possibilities of the remainder is proportional to k. So that will bring us to this nice time complexity. And the space complexity is also going to be like that cuz each of those sub problems is going to be stored. So let's code this one up and then I will try to optimize the solution with a bottomup approach. So first I want to just kind of define and fill out the recursive function and I'm going to use the same parameters that I mentioned and the main base case like I said is going to be this where we reach the target position. So that's going to be all the way at the bottom right and I guess I should define these variables now. I always like to do this. I like to think in terms of row and column and then get the dimensions of that as well which we can do like this. In this base case we are either going to return one or zero but it's going to depend on what the remainder is. So we're going to compute the new remainder which is going to be the original plus the grid uh value at the current position. And we want to mod this by k. So here I'm just going to use a turnary operator. Let's return zero if remainder is non zero. Otherwise, let's return one. That means it's zero. Okay, so that's the uh easy base case. The other base case is actually also pretty easy. Since we know we're only going to move down and to the right, the only way we would end up out of bounds of our grid is either if the row became out of bounds, so it would have been exactly this value, or it became this value. So if that's the case, we return zero because we can't really go any further. And then the other case is the caching case. And I'm gonna apply that after. I guess like there is a way to do it like with just a decorator in Python, but I think that's kind of cheating. I think in most languages you can't do that. So it's worth showing it the other way. But the recursive case is pretty simple. We're just going to call DFS by incrementing the row. We're going down one row. Column stays the same. Um, the new remainder will be different though because to this child, we want to pass in the new remainder, which is going to be pretty much what we computed up above. And I see that I forgot the mod here. So, I'll fix that. And I will copy and paste that to be here. Probably could have put it into a variable, but I think this is also fine. So, I'm going to do this. And then I'm going to copy that and put it here. And this time, instead of incrementing the row, we're going to increment the column. And so these are the two choices that we have. And we want to return the sum of these because we're trying to count the paths. And so initially you can just do this, but this solution doesn't have caching. And you would call DFS like this starting from the top left with a remainder of zero. So this is going to give us time limit exceeded. I won't run it, but trust me that it will unless it has some other issues. Uh but to fix this, we're going to use a cache. You could use a hashmap, but I actually got memory limit exceeded by doing that because I guess caches do have more overhead than uh the other alternative in this case, which like I said, since we have three dimensions, we're going to have a three-dimensional grid. So that's what I'm going to do here. I'm going to first have uh the value I'm going to use is actually negative 1 in this case cuz zero means something here. It's possible. I I'll show you how we're going to use the cache first. I guess we're going to do something like this where if the cache value at this row, this column, and this remainder is well, if it's zero, that could mean that either we computed that there's zero paths uh with this sub problem or that could mean that we just haven't seen it yet. So that's why I put negative 1 here. I don't want to use zero as that value cuz it's kind of ambiguous. So we use negative one and then we say if this is not negative one well then you can return the value that's actually in the cache whether it's zero or one. So that's what we're going to use here. And the dimensions I'm going to set up basically like this. So the the innermost array is going to be the one with k dimensions. Then the next one is going to be the one with column dimensions. So this in range columns. And then lastly, we're going to have for underscore in range rows. Actually, I almost forgot that we actually need to do the caching. So before we actually return just this value, we should cache it. Then we can actually use the cache. So just assign this and then just return this. And I am also missing an equal sign over here. So sorry about that. And I almost forgot that we actually also want to do the modding. So in Python, it actually becomes really really trivial. Too trivial I would say. You can just apply the mod at the end because integers can grow as big as pretty much like as much memory as you have in Python. So this could be a massive number and then we mod it right at the end. But in most languages, you're going to want to probably do something like this where you take the return value of this and then I think you apply the mod here and you apply the mod here and just to be safe, you also apply the mod there. This way we can guarantee that the return value from here is always going to be uh valid. So actually we don't even need this outer one anymore. So let's give that a run. And you can see it works and it is pretty efficient. But we can do a bit better by going to the bottom up solution. And it's really hard in my opinion to derive from a picture. If you like pictures, I highly recommend you dry run through the code I'm about to show you and give that a try. But it is really really tedious. I don't want to make like a 20 minute video, like a 20-minut section of this video just drawing that. I'd rather talk about like the highle ideas. So, first I'm gonna leave this stuff the same and I'm just going to start translating this into the bottomup solution. And I'm going to do it to be consistent with our recursive solution, which the recursive solution computes the top left position last, right? It goes all the way to the bottom right and then it starts working its way back up to the top left. That's what this solution is doing. So, to be consistent with that, I'm going to do this. I'm going to say let's go through the rows in reverse order. Let's go through the columns in reverse order. Some people don't like it when I do this, but like I said, the reason I do it is because it makes translating this solution into this one really easy. Otherwise, you have to completely change the way you're thinking about the problem. If you want to traverse this from the top left to the bottom right, you have to think of it uh very differently. So, I'll show you why I'm doing it this way. And then lastly, this is the part that's kind of confusing because now we're also iterating uh the remainder through the range K. And this one time it doesn't really matter whether you go left to right or right to left because there's no like geometry with K. K is just the remainder. So, what we're trying to do here is say, okay, if I was at like the first iteration of this loop is going to say if I was at the bottom right position and this was my remainder, how many paths would I have to get to the bottom right? Like how many valid paths would I have? And there's only one correct solution to that edge case, to that like first case. And for that reason, uh, the general formula that we're going to have here actually isn't going to apply to that. Like that's like our base case. That's like this case. So before I show you the base case, let me just show you the general math here because it's pretty similar to this. So what we're ultimately trying to say is we're trying to fill in this value, the cache at the row column with assuming that this is the remainder. Maybe it's not even possible that this could have been the remainder. It's not like we started at the top left and worked our way down like we did in the recursive solution. We're just assuming we're just going through every single possibility. Whether those possibilities actually exist or not is it doesn't really matter because once we have those possibilities, once we solve those sub problems, then we can solve the ultimate problem which is this. return the value in the cache starting from row 0, column 0, and the remainder initially being zero. Do that. That's what we're trying to do. So, we're trying to solve all of these sub problems that make that possible. And to do this, like I said, it's pretty similar to just this. It's going to be cash row plus one with the column and sum remainder and cash here, row column + one with some remainder. I'm not going to use the same remainder here. Why not? Well, if you don't want to think about it, you can just look at the recursive solution and realize that's exactly what we did in the recursive solution as well. So, I'm just going to copy and paste this and then bring it up here and then say new remainder is this. And then I'm going to put I guess I'll wrap this in a parenthesy and then I'm going to put new remainder down there and down there. Because logically what this is doing is it's saying okay if we went down then we'd obviously be at this position and our new remainder would be this one cuz we took the value from the current position. And then we're asking okay well how many paths from there exist and that's why we're doing this in a bottom up order because we know that when we're doing this assignment that value will already have been computed. So hopefully this much makes sense so far and I guess I should go ahead and do the modding as well while I'm at it. So mod this and then add that to this and then take that whole thing and then mod it like that. I'm pretty sure the order of precedence of this is correct. So hopefully I'm right about that and hopefully this can be translated into other languages. But now for probably the hardest part. Well, I guess before I do that, we initially set this to negative one. Uh but we're actually going to set this to zero this time. That might be a little bit confusing, but the reason we're allowed to set this to zero is because now we're actually computing the subpros in the correct order. We're never going to get to a point where we're looking into the cache and then there's a zero value there and that zero hasn't already been computed yet. Like we're not going to look down and then see a zero there that wasn't originally there. That zero was there intentionally. So that that's why we can do that here. And not only that, we actually need to do this because what you're going to find is there's an edge case where we're starting in the last row and or if we were in the last column, row + one is going to be out of bounds. Column plus one is also going to be out of bounds. So to account for that, the easiest thing to do is just to make the grid one size bigger in both directions. And then when we go out of bounds, the default value in that case will be zero. And then that's a good default value to have when you're out of bounds as we learned with the recursive solution. So uh that's why we're doing that. Now last but not least, what's going to happen on the first iteration of the loop when we're at the bottom right position? We're going to compute some remainder, but it doesn't matter because this is the edge case that the value below is going to be zero and the value to the right is also going to be zero. So we're just going to end up with a zero here for every single possible remainder. But that's not quite correct. So now to make this clear, I'm going to give you a little grid. So we have this grid. What I'm saying is we're going to start here. And in our DP grid, which is going to be all zeros, what we're trying to do is initialize this value because everything's going to depend on that. That's kind of like our base case. So in this example, let's say K is equal to three. So the remainder like what we're looking for has to be divisible by three. So now this question should should be pretty easy to answer. When we're here, when we're at this location, what's the remainder that we need to make this guy divisible by three? Obviously, it's one. So only in that case can we say that okay, from here there's one path and we would need that exact remainder. Now how do you calculate that remainder? It's given that this could actually be like bigger than three. It could have also been a five. And in that case, still the remainder we would have wanted is to be one. This is how I'm going to calculate it. Some people might say this is too complicated, but this is how I figured it out. So, it's going to be what I'm going to call target remainder. I'm going to take K and I'm going to subtract from it the value grid at rows minus one, columns minus one. The value at the bottom right. And this value could be bigger than K. So I'm actually going to mod this by K first. This uh itself maybe this was actually a zero. That's the other edge case. So then we would have gotten K minus K or sorry we would gotten K minus 0 which is going to equal K. And that doesn't really make sense. Like if this was a six for example, then 6 k is going to be zero. That means we needed a remainder of zero, not a remainder of K. So then we're going to take this entire thing and mod it by K. So again, all of this is just to compute the target remainder that we would have needed from here to make a valid path. And so with that, that's pretty much the base case. That's the one where we can say, okay, at the bottom right of our cache, uh with this target remainder, we're going to set this to one. And since we don't want to overwrite that value here, we don't want to reset that to a zero on the iteration of the loop here. We're going to put a continue statement. This is going to be that and this is going to be that. And then we're going to continue. That's the bottomup solution, assuming I don't have any bugs. And while it is not trivial to arrive at, especially this edge case, I think it is still pretty similar to the bottom or the top down solution. And here you can see it works and it is pretty efficient. I think there actually is another optimization we can make to this which is that if you notice uh for each row that we're computing, we're only looking one row below. So rather than having the entire grid in memory, I'm pretty sure you can actually do it row by row by just having at most two rows in memory at a time. And I think that would mainly be to improve the memory complexity if you're interested in doing that. Anyways, that's it for me. I hope you guys have a good day and check out Nico.io for a lot more.