Time Needed to Buy Tickets - Leetcode 2073 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem time needed to buy tickets so the premise of this problem is similar to the last one we still have kind of a cue of people in this case though we're given two inputs we're given an array called tickets now this actually represents the number of tickets each person wants so the first person in the queue wants to buy two tickets the second person in the queue wants to buy three and then the last one wants to buy two and so the queue is ordered in this way the problem is that a person can't buy two tickets they can only buy one ticket at a time so this person buys a ticket now they only want one ticket okay now this is the beginning of the queue so in a sense this person goes to the end of the queue and we could model it that way if we wanted to we could use a builtin q data structure that's perfectly valid but the problem is easier than that if you can recognize a couple things and I'll try to explain the intuition of how we can make those observations that will make us be able to solve this problem more easily so for now let's just say Okay this person bought one ticket now they only want one we can instead of manipulating this like a queue we can just have a pointer right so this pointer will now be over here next person wants three tickets but they can only buy a single one so they buy two now we're over here this person wants to buy a ticket they can only buy one so now this is what our que looks like everybody still needs to buy at least at least one more ticket now next this person could buy their last ticket now they only want zero tickets now we're here this person buys a ticket only one ticket this person buys one zero tickets left so now it kind of becomes useless to have a pointer because not every pointer is going to be at a valid value this person wants zero tickets we can skip them now we can automatically go over here this person wants to buy a ticket so they buy it and now we're left with all zeros nobody needs any more tickets so that's how we could run the simulation if we wanted to with an array and again you could also more appropriately run the simulation if you are using a built-in Q data structure because you could pop from here and then push here pop here push here etc etc if we ever got to a zero then we pop it and then we have no need to push it to the end of the queue the person doesn't need any more tickets so that's why it's kind of a q problem but this is the observation that we can make that will make the problem pretty trivial first I guess we should start with what exactly are we trying to figure out like we're not trying to run the simulation we're trying to actually answer a specific question and that question comes from the second input parameter so that parameter in this case is k equals 2 what that means is the person at index 2 which is this because we're zero indexed this is zero this is one this is index 2 we want to know how many turns does this person have to wait to buy their tickets now that's not how they really phrase it they say 1 second so I guess I'll stick with that so every time time we want to buy a ticket it takes one second so this person to buy a ticket now they only want one ticket that took a second now this person wants two tickets left now two seconds have passed this person wants to buy a ticket now they only want to buy one ticket so doing those three turns those three steps took 3 seconds and if we continue again this person buys a ticket zero this person buys one one this person buys a ticket now zero so in total it took 6 seconds before the person at index 2 bought all the tickets that they wanted that's the question we're trying to answer how many seconds does it take before this person buys all the tickets that they want and if our parameter K was equal to index one then we'd be asking how many seconds before this person buys all the tickets that they want it would take one additional second cuz now they get to buy a ticket so then it would take 7 seconds so at first it seems like you have to run the simulation to answer the question right but there's a pattern here let me kind of explain it to you it took 6 seconds for this person to buy both their tickets why is that let's dissect it first of all for this person to buy their tickets the people ahead of them have to make a move so this person wants two tickets therefore everybody before them has to go twice like through that line of buying tickets this person would have to go twice this person would have to go twice and then this person would have to buy both of their tickets after these people have gone twice it would take 6 seconds but is that always going to be the case consider this what if the value here was actually a one this person only needs to go and buy a single ticket well they're going to buy that ticket in 1 second and then they're never going to buy another ticket so then they wouldn't need any more tickets this person though would still have to go ahead of this person twice so it would take 1 second for this person it would take two seconds for this person to go twice and then this person would buy both of the tickets that they want that takes 5 Seconds what's the pattern what's the difference between this new example I showed you and the previous example we were looking at pretty much this we go to index K this is the person we care about then we go through every person before this person and we add to our total which I'm going to call the result so this is the number of seconds we're trying to total up and we're going to go through every value and we're going to ask a simple question is this value less than the value at index K if it's less than the value at index K we take this value itself and add it to the result it's just one we go to the next value is this value less than the value over here it's not so what do we do it's three but does this person really have to buy three tickets before this person can buy two tickets nope they definitely don't what we are recognizing here is that the person at index K is the bottleneck so either we will take a value here which is smaller than two and add that to the result or this value is greater than two in which case we're just going to still add two because we only need this person to go twice before this person can buy a ticket and to finish the example we get to the person at K and add their value which is two so in this case it would take five total seconds now let's quickly go back to the previous example where this was a two just to spot the edge case where this value is equal to the value at index K in that case we also would add that value so basically if this is less than or equal to the value at K we add that to the result and if it's greater we will just add the value at index K to the result and for this value itself we'll add that as well so in this case we would get six there's one last thing that this first example doesn't actually illustrate for us because it's a special case where the index that we're considering only has people in front of them what about if there were people behind this person that matters as well so let's change this example to k equals 1 now we want to know how many seconds does this person have to wait before they get to buy all three tickets so let's follow what we had before to our result we're going to go through every value we're going to see this one it's less than or equal to this so we're just going to go ahead and add two this person definitely needs to buy two tickets before this person can buy three tickets okay now we get here this value is three it's less than or equal to three technically so it does follow our rule so three is going to be added that makes sense because this person of course needs to go three times before they can buy all three tickets now though when we get behind in this case it is true that this person needs to buy two tickets before this person can then buy their third ticket so technically we do add this value to to the result but is that always going to be the case let's change the example for a second what if this was a three does this person need to buy three tickets before this person can buy their third ticket I mean this person is ahead of this person so really what's true is this person only needs to buy three minus one tickets before this person gets the third turn so for any value that's going to come after index K if that value is less than the value at index K which it was previously when this was a two we will go ahead and take that value and add it but if that value is greater than or equal to this value then we can ignore that value and just replace it with this value minus one so 3 - 1 which is a two so in that case we would add two here and it would only take 7 seconds for this person to buy all the tickets that they want just to make this even more Crystal Clear let's replace this value with a 10 this person wants to buy 10 tickets so are we going to add 10 to this no of course not we don't need this person to wait 10 seconds before they buy their third ticket we only need this person to buy two tickets before this person can buy their third so again we would replace this value with the value that goes here minus one so we'd put a two over here so it's all about how we add values that come before index K and add values that come after index K so knowing that I'm going to go ahead and code it up this is a linear time algorithm by the way cuz we're just iterating once we're not doing like the entire simulation and it's constant space CU we don't really have any data structures we're just keeping track of what the result is okay so I'm going to initialize the result to zero this is like the number of seconds that it's going to take for the person at this index to buy all the tickets that they want and this is what we're going to end up returning so now I'm going to iterate over every position in the input length of tickets and I am keeping track of this index because we know it kind of does matter because we know there's two cases either I is greater than or equal to index K and the reason I'm saying equal is because the value at index K matters as well or it's not and the else case is that the index I well I guess actually this should be the opposite we want this to represent where the index has not passed K and this is going to represent when the index has passed K so what we learned is everybody before and equal to K has to buy tickets before this person and either the value so let's say nums of I is either equal to K or it is less than K so basically what we're saying is we want to take the minimum of these two values we could write an if statement if we wanted to but the easier way to code this up is to take the minimum so either this value is less than this value or this value is greater in which case we want to replace it with this value so what we're saying is we want the minimum of these two that can be taken pretty easily this is basically the number of times that this person would have to buy a ticket before this person can buy all the tickets that they want to so this is what we add to the result and I realize I'm using nums here when we should be using tickets sorry about that now the else case is going to be pretty similar the only thing was that the person at indexi does not need to buy this many tickets doesn't need to buy the same number of tickets as the person at index K so they only need to buy at most this many minus one tickets so either this value is less than this value which is fine or it's equal to this value or greater than this value in which case we want to replace this one with this minus one just like we kind of did in the drawing explanation I know this is a little bit different than how we kind of talked about it in the drawing explanation but the core principle is kind of the same the only difference is I'm using the Min function here when we could just be using an if statement like we could have been checking is this less than or equal to this and could have done the same thing like up above but to be more concise leaving it like this so this is the entire code let's go ahead and run it to make sure that it works and as you can see on the left yes it does if you're preparing for coding interviews check out n code. thanks for watching and I'll see you soon