Minimum Limit of Balls in a Bag - Leetcode 1760 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum limit of balls in a bag feel like there's some jokes in that that I'll avoid for now the idea is that we're given an array of positive integers so let's consider the example that we have where we're just given an array of a single number nine which is not a horrible example we're also given another variable called Max operations I'll abbreviate that with an m and we'll say that for this example it's two so we can do up to two operations so we can take any given integer right now we just have nine and we can divide it into two integers when we say divide what we really mean is that we can split this integer so that the sum of its parts for example 2 and 7 or 1 and 8 something like that knowing that that's the operation we can do and we can split into any two integers that add up to nine and that we can perform that operation two times after we perform the operation what we want is the maximum element remaining to be minimized that's kind of confusing wording so let's look at an example suppose I split this into let's say 2 and 7 and then I split the seven into maybe four and three this is what we have left over the maximum among all of these is a four what we want to do is minimize the maximum right now it's four could we have made it smaller well we can't split these any further we already did the two operations we split the nine first and then we split the seven into these two but maybe had we split this a different way had we have done three and six and then took the six into three and three then the max is three Which is less than the previous Max that we had which is four we're trying to minimize this number and I believe for this example three is the smallest we can do can't really make any of these smaller so now hopefully you at least understand understand what the problem is asking and now before I get into the solution I guess I want to say if you've been solving these daily leak code problems you might be able to realize that this is very similar to a problem that we've solved before well you might not be able to realize it because it's kind of difficult to come up with but this is the problem that I'm thinking of leak code 2064 I think it's when we started doing the uh sort of cringey thumbnail but was like 3 weeks ago and I'll just say that today's problem is going to be similar to this one let's consider even a Brute Force approach what would that even look like let's just start taking some observations for this problem well we know at the very least that the result the output it can't possibly be greater than the max element inside nums because there's no way by splitting these we're going to make any of the numbers bigger and the maximum in the original array is never going to be bigger than what it started as so we know that the max possible result is going to be this the max in the input array we also kind of learned from the first example that if there is a greedy approach it's probably not going to be super straightforward like you could try to be smart you could try to be clever and say maybe the greedy way is just to take every number and split it exactly into two if you can so if this was an eight we'd split it into four and four but since it's a nine we can't do that so maybe four and five is the best that we can do but no that's not the case it's not that simple it's not like that so let's go back to the basics and think if there is a Brute Force approach what would it look like well since we already know that there is a ceiling so let's say one all the way up until x x is the ceiling it's the max number in the input well we could just try to work our way down we could just try to find the biggest one of these that is valid so basically the first time we find one that we cannot form that's when we know that we can stop so if there was a point where we can split this such that it satisfies like these but this is the first one that it doesn't anyways I think this is kind of abstract let me just explain it with an example so you might see where I'm going with this but with this example this very very simple example the max number is nine so that is kind of our right bound the left bound is going to actually be one and that mainly comes from the fact that when we split uh the balls you want the two new balls or bags or whatever these are called called to still be positive so that's how you know we can't go below one so this is kind of our search space and what we can try is go one by one try nine can we split the array such that the max element is nine this is kind of like our threshold or our Max um I think Max is probably a better word for it the max number of operations or not the max number of operations Max um balls so it looks like we don't even have to do any operations for everything things to be less than or equal to 9 so we're good and we can kind of just keep going down like that so now that we H checked nine it's good we're going to check 8 and then we're going to check 7 and 6 etc etc so for 8 right now we see that 9 is actually greater than 8 so is it possible in two operations for us to reduce the 9 so that it's less than or equal to 8 well we could just split this into 1 and 8 and would take a single operation we have two operations available to us so it looks like we are good here um but we maybe do need to find like a general way of figuring this out so we're kind of building up our intuition for now it seems like eight is valid eventually we'll get down to uh let's say four so let's assume all of these were good let me actually redraw this so let's assume we just went down the list all of these are good we eventually get to four so we're going to go through the input there's just a single number here we're going to check nine can we split this into numbers that are less than four yes we can we can split this into a four a four and a one how many operations did that take it took exactly two operations so it looks like in two operations we can split this array into something that will have numbers no bigger than four so this is also good so now we're kind of realizing that the intuition of this is that first of all every time we split a number we will be increasing the number of numbers that we have left over and every time we do split a number we want the new numbers the parts to be less than or equal to our threshold four and ideally the bigger the parts the better as long as they're smaller than the threshold so the intuition is just this you take the number you have in this case it's nine you divide it by the threshold so 9 divided 4 we get 2.25 this tells us how many operations it would take specifically just this part like without the decimal so it's two right now so it'll take us two operations it makes sense CU you have a nine you split it up into three elements it took two operations to go from a single element to have three elements that are all less than four so that's the idea um but it doesn't quite work with three so what you'll see uh if we were to do the operation if we were here um let's say we validated this one but now we're at three we're going to take n divided by 3 that gives us three operations but that's actually misleading because 9 can be split up into three three and three with just two operations so how do we make the math work out well you can just take the ceiling of this calculation and then subtract one from it so 9 / 3 gives us three operations and then we subtract one operation because we already started with a single number so if we had 4 9 / 4 we get 2.25 you round that down you get just two or sorry you round that up and you get three and then you subtract one from it you get two so we're going to round the result of this division up and then subtract by one so far all I've done is cover the Brute Force approach so how it would run on the rest of this example is okay we'd find that three is valid is two valid well can we split n into groups that are less than or equal to two well take 9 and divide it by 2 you get 4.5 I think if you take the ceiling of this and subtract one it gives us 5 - 1 which gives us four operations and unfortunately we don't have four operations available to us we only have two so this is the point where we would stop there is going to be a point somewhere here and we will pick the minimal valid number three was the minimum number on this timeline that's valid so that's what we return now you're probably realizing that this is a linear scan but we can actually do better we can actually run binary search on this below search space I won't go in depth on that because we cover it in that video I mentioned earlier leak code 2064 and I think that this picture probably explains what I'm about to do anyway but if you're not familiar with this recommend checking out that video if you are a neat code user this is the advanced course sorry you should go to the beginner's course this one this problem falls under the binary search pattern but we're not searching like a normal data structure like an array we're actually searching a range so I have a variation of binary search uh which kind of talks about that if you interested has some uh problems here as well so I'll kind of start just by coding up the Brute Force approach and then I'll try to convert it into the optimal approach there won't be many changes so first of all given some threshold we want to know if the array can be divided such that all the values will be below that threshold so I'll have a variable threshold and then we'll have in here counting the number of operations which initially I'll set to zero we want to know if all the numbers in nums can be validated and we stay under this number of operations so we'll return true or false based on that so for every number how many operations is it going to take to make this number valid well our equation was this the number itself divided by the number of like the threshold this gives us the number of operations we want to take the ceiling of that and then we want to subtract one from it and then this is the number of operations so we want to add that to our variable here now if the total number of operations goes above the maximum operations threshold then we will return false so sorry I shouldn't have used the word threshold when referring to this variable it's not really a threshold though I guess it kind of is or maybe I should have renamed this one I don't know but uh the threshold refers to the max balls so let's call it that Max balls now you might be wondering well what if n is actually below the number of Max balls well in that case this will be zero or actually I think it'll be one because both of these numbers will be positive so this will be one and then this is minus one so this will evaluate to zero so we don't need to check that this is positive or anything like that now if we never return false down here it seems like we validate everything and we can return true up there so now we're nearly done actually let me see if I can do the Brute Force real quick I actually didn't do it myself but we know that the maximum it could possibly be is Max of nums so like this and then we want to go in the opposite direction to zero but not including zero and 1 so this is just a loop starting at this and then going in the opposite direction So eventually we'll be able to using this as the max number of balls validate one of these and honestly we don't even need to go from right to left we could just go from left to right and just return the max value valid one so I'll probably just do that XS + one starting from one we could probably start at two so our result initially all set to zero we'll try to maximize the result and that's what we'll return and so for each one of these I will call the variable or the function can divide I if so the result will be set to I and that's what will'll return so let's see if this works actually if I'm going to be doing it this way we could probably just return the first one so at this point I'll just go ahead and say return I and then we can get get rid of the rest of this so hopefully this works so it looks like it probably works no way to know for sure but this one does get time limit exceeded because as you can kind of tell from this the time complexity we're going uh this many times and so this function here is pretty self-explanatory this is an O of n time algorithm because we're iterating over uh the entire input array nums and this part here is the max number from the input so the overall time complexity let's say is going to be o of n n is the number of elements and let's say m is the max element in the input we can actually do better we can do binary search on this part so we can get this down to be log M which is actually a very big Improvement bigger than it seems and it's very easy to do this we will just set up our variables like this I've done this a million times so I have it pretty much memorized we set up our search space like this I always start it like this left is less than or equal to right and change it if we need to and this time we actually are going to end up changing this condition I'll uh tell you why in just a second first we're going to get the middle value so we're going to say left plus right / 2 if you want to prevent overflows you could also do it this way right minus left and then add that to the left pointer doesn't really matter that much if you want to do it the other way that's fine too and then we want to know just two things can we divide this so call can divide on the M value and otherwise the else case what are we going to do in each of these cases that's the only thing that really matters here well if we can divide it that means this Max balls threshold is good enough and we want to try to find the smallest threshold so we are going to take our right pointer and shift it to be uh at the midp pointer because technically the midp pointer is valid so we want it to be included as a part of our binary search space we're trying to get the minimum valid threshold and otherwise if it's not valid it's too small meaning this middle pointer is not valid so we will set our left pointer to be mid + 1 and so after we're done with all of this the left pointer actually will have the result so let me just make sure that this works first so we'll return the left here and I think that's the only modification that we need to make let's confirm that this works okay actually it won't work because I forgot to update the condition here so why exactly are we going to be updating this condition because down here instead of doing right equals m minus one we're doing right equals m and the reason we're doing this this is not like the normal binary surch search sometimes you'd have three conditions one of them we'd return for sure and the other two you'd update each of the pointers but we're not doing it this way this time because this is a slightly different binary search where we're actually looking for the smallest valid element we're not just looking for a specific Target value that's what makes this binary search a little bit different and so if we're going to have right equals mid well what if the left pointer was at Mid and right now we're setting right equal to Mid then these are going to be equal and maybe they're going to stay equal they're just going to keep executing this line so that's why we need to change this up a bit so now running the code you can see that it works it's very efficient I think maybe if this like binary search part was kind of confusing to you there is a different way that I used to write this I will write it like this result is let's say initially just equal to the max of nums or even just set it equal to the right pointer up here every time we find a valid pointer let's go ahead and set the result equal to that valid uh pointer and with this binary search we're going to only be looking for smaller valid numbers after we find valid one so it looks like that will work and then I think down here we could just change this to return the result and running this code let me just zoom out so this is the updated binary search code so running this you can see that it also works and is just as efficient so don't get too caught up on like the Minor Details as long as you can explain your thought process and do things in a mostly valid way you should be fine thanks for watching and I'll see you soon