Solving Questions With Brainpower - Leetcode 2140 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem solving questions with brain power sounds like kind of what we're doing today but actually we're going to be doing the opposite because yesterday's problem actually I went so in depth into that problem that today's problem is actually pretty trivial in comparison and I'll show you why if you watched yesterday's video you'll probably realize the same thing but here we are given a list of questions where each question is a pair of values one is how many points we gain from that question and the second is the brain power we have to exert to solve that question now the rest of the problem is so damn confusing the way that they worded it to be honest it took me a while to realize what exactly they were asking this is kind of the most important sentence down here basically we are allowed for every single question to either choose that question or skip that question what does that sound like to you it sounds like backtracking or maybe depth first search right a brute for or solution and maybe just maybe we'll be able to optimize this using dynamic programming either recursively or just like the tabulation solution but what exactly are they even asking us let's say this is our list of questions we are starting at the first question if we decide to skip that question which definitely is a valid Choice then we're just going to move on to the next question and continue to make choices either include this guy or skip it but what happens if we decide to actually solve this question as in we include this well basically we gain the first integer the first integer is the number of points so our total number of points is going to be three at that point there is a catch there is a downside here and they say it right here you will be unable to solve each of the next this many questions by this variable I thought they meant like we're not allowed to solve the questions that have like another a brain power value of two but that's not what they mean they mean we are not allowed to solve the next two questions because this number here is two we have to skip the next two questions we skip this guy and we skip this guy and then we go over here so let's say our index I was over here initially at zero and we decided to include this question then we have to skip the next two questions so what do we do with our pointer I do we add 2 to it at that point it would be equal to two that's not correct because at that point it would be over here that's not exactly what we're looking for we're looking to move it one further than that we want to skip two questions so what we would do to our pointer I is say plus one and plus the two value that we get from over here so then our pointer would be equal to three and we would be at this position now if we did not decide to include this question our current total score would still be equal to zero but we would have just taken our eye pointer and shifted it by one to be over here so that is actually pretty pretty much all you need to understand to get to The Brute Force recursive solution very quickly if you want to visualize the decision tree it would look something like this where our eye pointer is initially at zero we decide to include this guy in which case our eye pointer would then be at three if we decide to skip it our I planner would be equal to one and of course we would have to maintain like our current score at each of these uh points but this is kind of how the decision tree is going to go we're going to enumerate all possible ways that we could solve these questions and then what we are ultimately trying to determine what the problem is asking for is what's the maximum number of points that we could possibly achieve given these rules now one thing you're going to find is since we only have to keep track of one variable what we're going to see is that sometimes we do get repeated work like here if we decide over here to skip we might get like a plus three plus one which would put this something out like I equals five but if we decide to skip this then we would get maybe over here to I equals two the point that I'm making is Maybe here we're going to get to I equals 3 and sometimes we're going to notice that the sub problems end up repeating we don't want to have to solve the same sub problem twice so we're going to implement ADP uh technique called caching to eliminate the repeated work so each of these subproblems will only need to be solved a single time and how many sub problems are there well our pointer I might end up being at every single position in the input array which let's say the length of it is n so therefore the time complexity is going to be Big O of N and lastly from the root of our decision tree once we have this sub problem solved and this sub problem solved these are kind of the two main sub problems we're going to take the maximum of the return value of both of these recursive calls and that's going to be our result because that's what we're trying to determine remember the maximum number of points that we could earn so knowing that let's code it up so remember we're going to solve this recursively so I'm going to create create another function defined inside of our outer function because then I don't really have to pass in this list of questions each time we can only worry about like our actual pointer which is changing now what about our base case for the recursive function well the main one is going to be if our pointer I goes out of bounds which might mean it reaches the end of the length of the questions but remember the way we are making decisions we might not only be incrementing I by one we might end up incrementing it by a larger number so it's actually possible for our eye pointer to go way far out of bounds way further than the last index instead of checking this equality we should check if it's greater than or equal to the length of questions and if that does happen if we're out of questions of course we can't really gain any more score so we return zero now what about the recursive call well the simple one is just DFS on I plus one this is skipping the current question what if we want to include food or rather solve the current question well then we would call DFS actually before we even call DFS we would have to add to our current score the current question which is going to be at questions index I and the first value among the pair so at index 0 is going to be the score that we gain from solving that problem so we're going to take that score and add it to the result of our new DFS call which we're not just going to be passing in I plus one it's not that simple remember we have to pass an i plus 1 plus the number of questions that we now have to skip which is going to be questions index I at index one remember the second value is the one that tells us how many questions we have to skip so we have it just like that so these are the two values that we actually care about and what we want to do with both of them is just find the maximum so I'm going to do it just like this there are probably more readable ways to write this but I kind of prefer writing it like this don't forget the comma over here because we're passing these two values into max as parameters and we're going to then store the result in our DP cache which now I should probably start talking about because we've pretty much solved this problem in a Brute Force way but now we have to add caching to it to make it more efficient which we can do by creating a hash map that's what I usually like to do but you could also use a one-dimensional array in this case and we're going to store the result in the hash map using the index I as the key and then after we've computed that we can go ahead and return it it's important though that you make sure to store it in the cache because here as another base case we want to know before we actually start making additional recursive calls if we've already solved this sub problem before which we know if index I is already stored in the DP hash map then we can just return that pre-computed value so this is the entire recursive solution with caching implemented or memoized station and the only thing we have to do now is actually call it we're going to call DFS starting at index 0 because they told us we have to start at the beginning of the list of questions and work our way to the right so let me run this code to make sure that it works and as you can see it does and it's pretty efficient now very quickly I want to show you the tabulation method for this even though the time and space complexity is pretty much the same which for both of the solutions is going to be Big O of n for the time and Big O of n for the space remember we had a hash map and it was pretty much a one-dimensional array like I said and we were Computing the values in each of these positions can you tell me what the value at this position might represent well it's basically the entire problem the value stored here is the score we can gain the max score we can gain from all of these questions like if we can choose from all of these questions but we know that to compute this value we have to solve the sub problem which is asking the same question for this portion of the array and then to solve this problem we have to ask that for this and then this and this is pretty much the base case because remember we start at the left and work our way to the right but we can't predict the future so we have to try every combination so this is the basic sub problem just solving this question will give us two points so let's put two over here now we can kind of solve this sub problem so at this question we have a choice we can solve this problem and gain a score of four and then if we decide to solve this problem we have to skip the next four sub problems so we would say actually the value we're going to store here is going to be 4 plus whatever value would be four plus one positions ahead and this 4 by the way is coming from here clearly that takes us all the way out of bounds that's kind of the reason I'm deciding to use a hash map instead of just a one-dimensional array you could use a one-dimensional array but you'll have to have some if statements to check if you go out of bounds and with a hash map I'll show you how you can avoid that that was just one of our choices for this position if we decided to include this value what if we decided to skip this value then we would just take the value at I plus 1 which is 2 in this case so you tell me which is greater four or two well probably four so we're going to score 4 over here and we're just going to keep working our way backwards solving each sub-problem now we're over here we can choose to include this 4 plus then we have to skip three spaces plus one but that'll take us out of bounds so that's one choice or we could just take the value at I plus 1 which is four so either way we get a value of 4 in this position now finally we get over here so we have a choice include three plus whatever value is going to be at index I plus two plus one so our index here is zero our index here is one two three this brings us all the way to index three the value at index 3 is of course two so this is one possibility the value stored here could be three plus two if we include the three value but we could decide to skip this and just take the value that happens to be stored over here well 5 looks greater to me than four so the value we're going to store here is going to be 5 and you can see that that happens to be the result for this question so this is exactly how we're going to code up this solution basically I'm just going to reuse this hash map that we already have here and I'm going to go through the array in reverse order so we can do that in Python like this the length of questions minus one we're going to be working our way all the way up until the beginning of the array and we're going to be decrementing each time if you're not familiar with python this looks complicated but it's actually simpler than you think we're just iterating our pointer I in reverse order through the range of the length of the questions and now what we're trying to compute here is what value we should store at DP at index I remember and we have two choices we can choose to include the question which would mean we take the score of the current question which is at index I and the value at index 0 plus whatever value is in our DP hash map at index I plus one plus the offset which is questions at index I at index one the problem is that this might give us an index out of bounds error if we're using a one-dimensional array with a hash map it might give us an invalid key error one way to fix that would be to say collections.default dict in Python which will always give us a default value of 0 if I pass an INT as like the default dick type but I think it's better to be a bit more explicit sometimes I feel like using this is like cheating so what I do is just have a hash map and I actually instead of indexing this I say dot get with the same key value which was I plus one plus question questions index I index 1 but if this value doesn't exist or this key doesn't exist in the hash map we can return a default value which we can actually specify so in this case a good default value would probably be zero so that's what I'm going to specify as the default value so this way we don't have to check we don't need an if statement to check if this is not a valid key because if it's not we'll get 0 anyway and remember this is the choice if we include the current question there's also the choice where we skip or rather I should say solve but you know whatever and skipping is a bit more easy remember we can just say DP dot get at index I plus 1 but even if that happens to be out of bounds let's get a default value of zero so these are our two cases and we just want to take the maximum of them remember notice we do not have any recursion here we're just getting the values from the hash map we're not making recursive calls like we did below so I'm just gonna cut this into our Max function function and then move the max function up to the assignment over here and that's pretty much the entire code remember the result is going to be stored at index 0 so let's return DP of 0 and run this to make sure that it works oops I forgot the comma remember how I told you earlier in the video don't forget the comma well somehow I didn't take my own advice so let's run this again and as you can see it works and it's pretty efficient very quickly I want to mention that this is an example of the zero one knapsack problem this is a dynamic programming pattern it's pretty common in the comments I'll try to link a few more problems that follow this pattern I've solved quite a few if you found this 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