Grumpy Bookstore Owner - Leetcode 1052 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem grumpy bookstore owner suppose we're given two arrays that look like this and the first array represents customers so we want to sort of maximize the values in this array I won't go too much into the context of the problem like minutes and all that stuff cuz it isn't really relevant it's more about there's a onetoone mapping between the first array customers and the second array grumpy the idea is that if grumpy is zero that means that the owner is not grumpy therefore the customers here will get the full satisfaction one here the owner is grumpy so this actually is going to be a zero now it's already a zero but it makes more sense if you look here where the owner is also grumpy even though there's a two here we can't really use that it's pretty much a zero as far as we're concerned so if you think of it that way just given this array we're kind of turning this into a zero this into a zero and and the value over here into a zero now if you take all of these up and compute the sum we're going to get 1 + 1 + 1 + 7 I think that's 10 now we want to maximize this score so what can we actually do about it well that's where the third parameter comes in it's minutes in this example it's three so what that means is we can pick any block of three any continuous block of three elements and basically turn the grumpiness to zero for all of those values now if we do that the only reason would be because then we get the original values from the first array so instead of this being a zero it would actually be a two and this would be a one and if you take our original result 10 plus whatever we gained by you know flipping these we're going to get this as the result now we're trying to find the window that will allow us to maximize the result and for this particular problem it's over here because we're going to get the plus one and we're going to get the plus five so that's going to leave us with a result of 16 that is the output for this problem now the brute force would be an n * m solution where M literally is this parameter and N is the length of the array can you think of that Brute Force solution well I kind of just showed you one example of it but think about every possible position this window could be in it could be over here it could be over here and every position pretty much right so for any given spot like this one we want to compute for only the positions where grumpy is a one we want to compute the sum of these values because these are the ones we're allowed to flip back so in this window we say that it's a three for the next window here we'd say that it's actually just a one because this one 's already zero this one's already zero this one is a one we flip that and we get the one back from here so pretty much every single window is going to have some score assigned to it we obviously want to maximize the result the result is the original array like after turning them into zeros so that was 10 plus the max window that we can get and the max window in our case is going to be six so that's how we're going to do it we're going to look at every single window and compute whatever score we could get from that now now if you're thinking how is this a Brute Force solution you might already know the technique I'm about to show you which is called the sliding window this is a very textbook sliding window problem I actually have a pretty good lesson on it in my Advanced algorithms course it's called the sliding fixed window where the size of the window is fixed there's also variable size which we're not really going to get into but you can see we talk all about that here so with the sliding window the idea is that we don't have to go through the window every single time we don't have to go through these values and recompute that and then when we're over here go through the same values again because when we take our window from here and then move it to the next position over here all we have to do every time we shift the window we just add a value here and remove a value here so whatever our score was with these three values we're going to now compute the score with the next value after removing this one that's pretty much the idea now let's go ahead and code this up with this sliding window optimization it's just going to be an O of n time solution where n is the size of the input and constant space because we're not really using any other data structures so let's code it up so while I feel that conceptually this problem isn't too bad I think coding it up has a few areas that can be confusing so the idea is we're going to have the sliding window we're going to have our left pointer I'm initially going to set it to zero then we're going to have the right pointer going through the length of the input array now we want to know the score of the window right like when I say score I mean how much we could get from the current window if we flipped everything in that window to a grumpy score of zero so that's why I'm not saying all of that every single time because it's a lot to say and it kind of just makes the explanation more confusing in terms of code it's pretty simple if grumpy at the current index R is one then we're going to take whatever value is at the same index in customers and we're going to add that to the current window now I also want to keep track of how many are satisfied and what I mean by that is I want to sum up all the satisfaction scores where grumpy happens to be zero so where it's not set so I can actually put this in an else condition and then I can say this add to satisfied the value of the customer at that index because this satisfaction score is like the base score score that I was talking about earlier and the example it was 10 and that's because this is how much satisfaction we have without changing anything at all so that's like the base and we have our current window there's one last variable I'm going to have and I'm going to show that to you in a second but first let's check what if our window becomes too big because we have to remove characters from the left side so the length of the window can be calculated like this R minus L + one that's how many values are in the range from R to L inclusive and so basically if this is greater than the third parameter minutes we want to do something we're going to say remove from the window the value at the left pointer and then increment the left pointer but we're only removing a value from the window if we added it to the window so make sure you have this condition here if grumpy at index left is one only then do we want to remove cuz only then we actually add that value to the window so this is just some bookkeeping to make sure we don't get any errors and everything stays consistent with our window and now lastly I'm going to have a another variable up here I'm going to call it the max window cuz we want to keep track of the current window and also the Max and you could probably do it with less variables but I want to make this mostly readable so max window is just going to keep track of what is the max window that we saw pretty straightforward at the end you probably can guess the calculation look at the variables I wrote out what is the return value going to be based on the drawing explanation you should be able to figure it out it's going to be satisfied like the base score plus the max window it could be zero it could be some other value doesn't matter we just want to return the sum of these two values and as you can see on the left we are bigger than everybody else if you found this helpful check out N.O for more thanks for watching and I'll see you soon