Solving Questions with Brainpower - Leetcode 2140 - Python

Key Takeaways

I told you I was going to stop making these leak code videos, but I just couldn't help myself today. I'm not sure why they gave us a dynamic programming problem for the beginning of the month. But I do want to show you that this problem is very, very easy once you understand this pattern. It's literally a textbook problem and I was able to solve it in like 5 minutes with both solutions, the top down and bottom up solution. I'm not even kidding. And I want to kind of tell you how you can get just as good as me by knowing like the patterns and learning based on the patterns. You don't have to use my courses if you don't want to, but I want to show you that this is literally the a 01 knapsack pattern and um logging in so I can see all of this. But yeah, it's literally a textbook problem. The template the exact same that I'm going to be following in today's problem. It's got uh some variations. There's many different variations of this problem. Coin change is considered one of them, but I think coin change is actually the unbounded knapsack. But anyways, let's get into it. Idea here is pretty simple. We're given a bunch of questions. Each question is going to be a pair of values. I'm going to go kind of fast, so please try to keep up. Um, the pair is going to be first the number of points that we can earn from that question, and second is going to be the the amount of brain power it requires for us to solve that question. So you could think of it as this is like our reward function and this is like our cost function. I mean not literally this is not machine learning but you could kind of think of it as the reward and the cost. We want as much of the reward and we want to minimize the cost. So you might think well maybe is this greedy? Whoops my camera was in the way. Sorry about that. You might think okay is this greedy? And it's not. And the reason I know that immediately is again just knowing that this is the 01 knapsack pattern. Now they tell us um the way that this u cost is going to work is we are allowed to start solving questions from left to right. And so if we decide for a question to solve it it's going to cost us and for each question we're going to have two choices. We can either solve it or we can skip it. So again that is a hint that this is dynamic programming or at the very least you should realize that this problem can be solved recursively with backtracking. And when I say that you should be able to recognize this, I mean like if you're familiar with this or if you're preparing for interviews and you want to know if you're good enough to solve these types of problems. If you're just starting out or if you're preparing, yeah, of course, you're not going to know how to do all these little things. But anyway, so that's the general idea. So we're going to kind of have two choices, right? So in this case, we could choose that we get 3 2 or we could skip it in which case we end up at the next uh choice. So 43 and in that case again we could either choose it 43 or we could skip it. So I'll just put a little line for skipping. Now the interesting thing is that when we do choose something so if we chose this one we got a reward of three but we it costed us two. That cost means that we have to skip the next two questions. So at that point the choice that we would have is either to uh solve the question or to skip it. And the question this time would not be either of these. It would be this one. 25. And then the five is going to cost us. So we have to skip the next five questions. But the five questions do not exist. There aren't any more questions left. So this is sort of a base case. So along this path, we total up all of the points that we got and that was five. Among all of these paths, we want to maximize the possible result. So that will be easy to do after each recursive step. We just take the max of both sides and then return the max. So we do that even from the perspective of the subpros. So for example here this would have returned nothing because that at that point we were out of bounds. So that's the general idea behind this problem. I won't even kind of mention memorization or caching because I think that's honestly something you can just kind of figure out by looking at the code that this code is going to be easy to cache and that once we do add caching there's going to be n subp problems starting from the beginning of each of these and so the overall time complexity is going to be big O of N as well as the space complexity is also going to be big O of N. And you're probably wondering well how am I going to do the bottom up solution? I'm actually not going to do a drawing explanation for that because it's actually very very easy to translate this code into a bottomup solution. You don't even need to turn your brain on. I usually just turn mine off when I'm doing that part. Okay, so let's code this up. And by the way, I just realized that I also solved this problem a couple years ago. I think I go a bit more in depth in that explanation. So if you prefer that one, you might be able to just search for it on YouTube. But this one, the solution is going to be mostly the same. So I'm going to have my index, right? And so we know that the base case mainly is when the index goes out of bounds. So if I is let's say equal to the length of the input array. So that means it's exactly out of bounds. At that point we have nothing to solve. So we can just return zero. And then after that we have two main choices. We can call backtrack like we have the skip case and then we have the choose case where we actually choose to solve that problem. Skipping is pretty easy because then we just go to the next index. Uh but choosing is a bit harder. We're actually going to need something for that. We're going to need to unpack the question at index i. So I'm going to say questions index i. I'm going to get the points first and then the brain power. And because when we choose, we not only take the result of the sub problem, which is going to be at index i plus the brain power. And we actually also need a plus one here because we're skipping this many questions. We're not going to advance this many places. is we're going to advance one plus that so that we skip that many questions and we will get this much points. So we take points and add it to the result of this sub problem because this is the question we chose to solve. This is the sub problem. Now if we skipped it we wouldn't have gotten any points but we would have then had the sub problem over here. So among these two that's what we're trying to maximize. So I could do this. I could say well max of these two and then just move them inside. And don't forget the comma over here. And then this is what I could return. So this is the most brute force solution. I'm actually going to run it just to make sure that it works and I didn't miss anything. But we're going to call backtrack from index zero on the outside. Actually remember when we naively said this index is exactly out of bounds. Well remember that we're not only advancing the index by one. We could advance it by more than one. So we might actually end up even further out of bounds than this. It's easy to remedy that. You just do greater than or equal and then return zero. So I think this should be good now. And as expected, we do get a time limit exceeded cuz this is an exponential solution. But you notice that inside of the function, we're just doing constant work. If you don't include like the recursive step, we're not really having any loops or anything like that in here. So we could cache the result of this function call because we know that the number of times it's going to be called is n different times for indexes 0 to n minus one where that's the length of the array. So we could have a little cache over here. We could use a hashmap or we could use an array. I'm going to use an array. So 0 time length of the input because we know that for any of the sub problems the result should never be zero. That's why I'm setting it to zero. We could have also done negative 1, but we know that every question is going to have a positive number of points. So for none of the sub problems, we should ever have a max where it's going to be zero. So then down here we can add another case where if the value at index i is non zero. That means we already solved the sub problem, we can return the result of the sub problem which will be stored in that array. Otherwise, we will compute it and before we return, we're going to set the uh result in that array and then we're going to return it uh just like that. So, this is uh the entire uh caching code. So, let's just give this a run. You can see it didn't really require many changes to optimize it. And there you go. Now, you can see it works. It's pretty efficient. If you want to do the bottom up solution, I'll leave this code here and I'll show you how easy it is for this problem. Notice how when we go top down, we are solving the smallest sub problem first and then we return the result of that and then we can solve bigger problems. We can use that same idea iteratively. We can iterate over the array in reverse order and try to solve each sub problem. So I'm going to do this and then I'm just going to wrap that in a reversed call which should allow us to solve these in reverse order just like this. So if you're confused on what to do if you do it in reverse order the step should be pretty similar to what we did down here. So I'm going to unpack uh those values and then I'm trying to determine what to put here at cache and index i. I want to take the maximum of something. So I'm actually going to store those in variables. I'm going to have my choose and I'm going to have my skip. So for choosing, it's going to be similar to what we had down here. So points plus the sub problem. I'm just going to copy and paste it because I can show you how I'm going to change this around. So we have the points, but instead of making a recursive call, we expect that the sub problem has already been computed. That's why we're going through these in reverse order. So instead of making a recursive call, we're going to do cache at index i + one plus brain power. Now the catch here is that what if this is out of bounds in the recursive solution? We handle that with the base case. It's a little bit harder to handle that here, but it's still possible. I'm going to use a turnary operator. You could do it a bit differently if you want to be more explicit, but I think a turnary is fine. We want to do this if the index is inbounds. Otherwise, we want zero. So, we can say if this is less than the length of questions and actually I'm going to put that in a variable as well. So, I'm going to call that my next index. Maybe I could call it J. Um, but I think this is fine. So, just to kind of have this line be a bit shorter. We'll do that. And then I'll do this over here. And I think for the length of questions, I'm going to change that to n to make this a bit more readable. So, I'm just kind of working fast. I hope you're able to still understand what I'm doing. Um, and lastly over here, while that's inbounds, otherwise we want this to be a zero. So, I'm going to wrap that in parenthesis. So, now we've guarded this to prevent an index out of bounds error down here. Similar, we don't add points. Um, but we will do cache at index i + 1. But again, we want to make sure that that's inbound. So I'm going to actually just copy and paste this and then change next index to be i + one. So it's pretty similar. And then we take the max of choose and skip. And I think we're pretty much done there. And then what we return at the end is going to be cache of zero. Just like uh in the recursive solution we returned backtracking of zero. So I believe this code is good. Let's give it a quick run. And yes, you can see it works. And this one is a bit more efficient in terms of the big O runtime and complexity. It's the same, but usually iterative solutions are faster than recursive solutions because we don't have the recursive function call overhead and all that. So, if you found this helpful, check out neatcode.io for a lot more. Thanks for watching and I'll see you soon.