Stone Game II - Leetcode 1140 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Stone game 2 this is a pretty weird problem and that's kind of why I like it and I have solved the previous one if you want to check that video out the story is the same we have two people Alice and Bob that are taking turns grabbing stones from a pile of stones in this case it's an array so let's take this for example and we have remember two players I'm just going to call them A and B for short player a is going to go first they're going to start at the two now in terms of the choices that they can make we're given another variable and this is going to be fixed so you can see it's not a parameter in this problem it's just a fixed variable initially M = to 1 so that does not mean that Alice can choose from only the first pile it actually means she can choose from two times this value so she can choose from the first two piles and when I say choose from I mean like either she can take just this stone or she can take both Stones all stones are going to be a positive value and what we're trying to do in this problem is maximize the score of Alice so of course you might think that we should just be greedy we should always just take both stones but this first example actually illustrates why we shouldn't do that because suppose Alice does take both stones and I'm going to make a player B red just to make it more obvious we can actually update our M value and it was actually one originally sorry for making it two now we update our M value by Always setting it to the max of either itself which is you know one in this case or the x value and X is basically the number of stones that were chosen in the previous turn and in the previous turn you can see Alice chose two stones so in this case the max is going to be two so therefore m is now going to be equal to two and so now when player B goes that doesn't mean they can choose from the first two that means they can choose from two times this value so Bob can actually choose four piles but we only have three left so that's an edge case you definitely don't want to go out of bounds keep that in mind for the first three of course Bob is trying to maximize his own score because what they tell us is we're running a simulation assuming that both players play optimally now of course neither of the players can predict the future they can't see what all of the stones are so in a sense we will have to brute for it we will have to try multiple possibilities so in this simulation that we ran Alice had a score of nine but Bob had a score of 18 + 4 which is 22 there's only one other simulation in this case and that's if Alice were to have only chosen the first stone so Alice chooses just two and the reason that's good is because M started as one and now to update M we take the max of itself one or the x value which in this case was one because Alice just chose a single Stone so now m is going to stay one even though Alice only got a single Stone the good thing is that now Bob can either choose just a single stone or choose two stones so I guess technically we do have more than two choices you can imagine the way I'm going through this could be simulated with a decision tree where we're keeping track of one whether we have Alice or Bob going we can use like a Boolean flag probably for that or you can use an integer one or two or one or zero but there's only going to be two possibilities for that parameter the other is going to be the index that we are at now so like we could be at this index we could be here we could be here and you know the index tells us what the sub problem now is and the first sub problem or really starting at the beginning is the entire problem itself and the third parameter is going to be M even though it always starts as one as we go through the array we could be at this position and we could have a completely different M value depending on how we got here like in this decision tree depending on the branch that we took M here might end up being one M here might end up being two and you can imagine what the M value is definitely does affect the result of this problem we have three variables the index the M value and whether we have Alice or Bob this one probably isn't going to affect the time complexity too much because there's only two possible choices here this one probably is I can be up to n values where let's say n is the length of this input array and M technically this one yes it starts as one so you might think it's fixed but how big could this possibly grow because in the worst case it could pretty much double on every level of the tree in the worst case M might get to the point where it's literally as big as the input array n so the number of possible States for this recursive function this Brute Force function is going to be n^ S where by States I mean like this is the number of combinations we could pass into that recursive function technically it would be 2 * n ^2 because we do have the Alice or Bob Flag but this is kind of a hint that this problem can be solved with recursive dynamic programming or you know AKA memorization I won't go super deep into the time complexity right now that'll be easier to analyze when we code it up I never finished this example so let's look at this point let's say Bob just chose the seven then over here if Alice wants to play optimally she has a choice of either just choosing the nine in which case Bob's probably going to take the last two or Alice can choose both of these in which case Bob is going to take this one so assuming this is the case where of course Alice wants to play optimally she's going to take both of these she gets a score of I think 20 and Bob gets 14 but just because Alice played optimally doesn't necessarily mean that Bob played optimally why would Bob just choose a single value over here Bob is trying to maximize his own score as well and I said 14 but I think it was 11 my math is off today is it possible for Bob to have a higher score than 11 like if he had chosen here something differently probably because if he takes both of these values he's definitely at least getting a 16 so that's probably the optimal move for Bob and when now Alice goes she's just going to take both of these giving her a score of 2 + 13 which is going to be 15 so that's probably the optimal path this is probably the solution because not only is Alice playing optimally but Bob is also playing optimally but how do we algorithmically keep track like how do we know if Alice is playing optimally and Bob is playing optimally because if we were just focusing on Alice it'd be pretty easy like we'd have our choice we either choose the two or we choose the two and seven so like just keeping track of Alice's score it could either be a two or a nine and then recursively maybe from here and here we want to choose this or this and among these two we want to get the maximum so that we can add it to the result but we know that after every turn it's alternating here it's not going to be Alice going it's going to be Bob so if from here we return the score that Bob gets from Alice's perspective we wouldn't want to maximize that we would want to minimize that so in a way what we could do is from Alice's perspective we could use the return value and actually take the minimum and not add it to the result but the problem with that is while it would kind of guarantee that Alice plays optimally what we're ultimately trying to do is calculate the score of Alice if she played optimally so what this function should ultimately do this recursive function it should return Alice's score even though I drew this in red we know we're talking about Alice here what my whole point with this is that now from Alice's perspective it will be like the return values from here and I shouldn't even put the two and N here because the return value here will be the score and will take the maximum of these two I should be putting like the pointer that we're at here we're at I = 1 and here we would be at I equal two originally let's say we started at you know the zeroth index here it's going to be Bob's turn and when Bob makes a turn we still know that the return value for him is also going to end up returning Alice's score to him but he's not trying to maximize Alice's score he's trying to minimize Alice's score so what we say is alternating on each level of the tree from here we know it's Alice's turn so we would take the maximum of these two return values from here we know it's Bob's turn so we would take the minimum of these two return values you might think then how are we going to calculate Bob's score well do we need to calculate Bob's score I mean to me it doesn't really look like we need to as long as we calculate Alice's score and we guarantee that Bob and Alice are both playing optimally we don't need to calculate Bob score Bob score won't be stored anywhere nor will this function return Bob score at all on any level of this we will not be returning Bob's score we're only calculating Alice's score that's the main idea behind this problem but it probably won't make sense until I actually show you the code so now getting into the code like I said we can solve this recursively and we're going to have three variables the first is going to be the flag telling us whose turn it is second is going to be the index and third is going to be the M value and remember this function is only returning the number of stones Alice gets it's always going to be the return value and the edge case is of course when we go out of bounds if I is equal to the length of piles then we return zero because if we run out of piles Alice's score is going to be zero regardless of if it's her turn or not otherwise we want to calculate the result so first I'm going to initialize it to zero but I'm going to leave a comment we will change this once we have a bit more information but we know for Alice we're trying to maximize her score so setting the result to a value of zero isn't bad and we know this is going to be the same result that we end up returning but now remember what's our choice at this point well that's what our M value is for and here I'm not going to use the pointer I cuz one we already used it up here and in the context of this problem that was the x value that we were talking about so I'm just going to say for X in range from 1 up until 2 * m now I am adding A+ one here because this is non-inclusive in Python but we know that the possible range of values is going to be from 2 up until 2 * m remember we're not just taking the pile at the index and how would we even find the index Well we'd say I + x but this is not quite right because our X in this case is starting at one so this would basically mean we always skip the I value that's not what we want to do if we're currently at the I index that's our first choice so to offset that we do put a minus one here but again we don't just choose this pile we're choosing a prefix starting at I we're either going to choose the first pile or the first two piles or the first three piles etc etc so you would think maybe we'll have a nested Loop in here but I'll tell you we don't need to do that we can just store that prefix sum aka the total sum of the stones and store that in a variable and on each iteration of the loop just add to that variable so here I'm just going to say total add to that this okay cool that tells us the total that Alice could choose on this iteration of the loop or on this branch of the tree there is one slight bug here though what if this ends up going out of bounds what if I + x - one is out of bounds it's not like we're checking that anywhere we could add like a minimum here like to make sure that X doesn't exceed the length of piles but I'm actually just going to put that in an if statement because I think it's a little bit more simple to do it that way like this line will get pretty fat if I try to add like a minimum in there so I'm just going to say if I + x is greater than the length of piles then I'm going to not return I'm going to break out of this Loop because we went out of bounds now you might be thinking well what if it's equal to piles isn't that the appropriate case no because notice how we do have the minus1 over here so if you really want to make it equal you should say xus one is equal to this I don't know what's more simple this one or the previous one but I'll just leave it like this for now you can do whatever makes more sense for you now we have our recursive case and right off the bat I'm just going to tell you remember we're going to do it slightly differently depending on whose turn it is if it's Alice's turn we're going to do it slightly differently when it's Bob's turn we're going to do it slightly differently for Alice we know we're trying to maximize her score it's her turn right now and we want to maximize her score so we want our result to be the maximum of either itself or the DFS recursive call after we choose this many stones so how would we update our recursive call well if it's Alice's turn we want to pass in false here probably or to make it a little bit more simple you could just pass in not Alice cuz we're always just going to take the negation of this no matter which recursive call we make for where our pointer now is going to be at if we started at X and we took this many stones we're just going to take I + x and say that's our new starting point and what about our M value how do we update that well that is something that they pretty much just told us we take the max of either itself or the x value that we ended up choosing not bad right this is the simple case where for Alice we want to maximize her score now here where we take Bob's turn remember the return value of this recursive call is not going to be Bob score we don't care about Bob score we're not calculating Bob's score here we're calculating Alice's score believe it or not it just happens to be Bob's turn and with Alice's score when it's Bob's turn we don't want to maximize that we want to minimize that so we take the minimum of the result and the DFS call which I'll fill in in just a second if we're trying to minimize something and we already set it to zero in the first place that's probably not going to work so we're coming back to this comment we're going to initialize that to zero if it's Alice's turn but other otherwise let's set it to like a really big number that we can then try to minimize and we know for sure that the result will never actually return float of Infinity for Alice's score here because we know our base case is going to be zero so just wanted to clear that up now to fill in the DFS for Bob's turn it's going to be pretty similar we just pass in not Alice and I probably shouldn't capitalize Alice here or over here and for the x value we do the exact same thing we set it to I + x and for updating m again we do the same thing M and X looking at it these are pretty much the exactly the same recursive call so maybe you could even break it out somewhere but I think for readability it's not like a huge deal or anything when we do minimize this value we're going to assign it to the result here and then we're returning the result and ultimately we want to call this DFS starting with Alice's turn so we pass in true for the first variable we start at index zero and we know our M value is always going to start at one so that's pretty much the whole code but this is a very very brute for approach this is exponential not only will we be branching two times at each step we could be branching multiple times so now let's add a little bit of caching to this you could call it a DP or you could call it cache and in my case I like to use a hashmap but a three-dimensional array I believe would work as well and it's just as easy as checking if this combination of parameters was already passed in meaning it's already stored in our DP cache then we're going to return the value that we ended up storing in that DP cache if it's not already stored then that's what we're calculating of course so before we end up returning the result over here let's make sure to throw it into the DP cache lsim and storing the result before we return it it's literally as easy as that to add caching to this once you can get to like the Brute Force solution so now let me run it to prove that it works and unfortunately I had a very silly bug I wonder if you can spot it the way we're taking the maximum of the result in the DFS call will the result ever be anything larger than zero cuz we're never adding anything to the recursive call and we know the base case is always going to be zero and we have our total variable over here for a reason when it's Alice's choice and we're calculating her score we should take the total number of stones that we chose and add it to the recursive call which also Returns the number of stones Alice can get but when it is Bob's turn yes Bob is taking this number of stones this is the total number of stones Bob is taking but remember we're not storing Bob's score nor are we getting the return value from Bob's score so to take like the total and add it to this would be a contradiction because these are the stones that Bob chose but the return value from this is Alice's Stones so we don't even need to add the total in this case we're trying to minimize Alice's score why would we give her some free stones from Bob there's no need to do that now let me quickly run it to prove to you that works and as you can see yes it does and it's pretty efficient and honestly if you want to improve the runtime you could probably just use an actual three-dimensional array rather than a hashmap a hash map has a bit more overhead but what about the time and space complexity well space complexity for this should be straightforward cuz the maximum size of this DP cache would be two cuz that's the number of possible States Alice could have and N cuz that's the possible number of states that I could have and we talked about why m in the worst case could be as large as n as as well so time n^2 is going to be the space complexity the memory complexity is going to be similar we know that's the number of times this DFS is going to be called and fully executed but on each full execution it's not like it's a constant time operation we are in the worst case looping and in the worst case looping up to M times so we would take the time complexity or the space complexity and multiply that by n one more time and this gives us the time time complexity so pretty much n cubed is the time complexity n s is the space complexity thanks for watching if you found this helpful please like And subscribe and I'll see you soon