Capacity to Ship Packages - Leetcode 1011 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem capacity to ship packages within D days so we're given an array of weights for example something like this one two three four five starting at the beginning of the array we want to break it up into chunks such that carried by a ship the ship will have some capacity so we have to make sure that the ship can hold all of these weights and then we'll have another ship maybe for this set of Weights our goal here though is to choose a capacity we are the ones choosing the capacity of the ships and our job is to choose a capacity for the ships such that it is the minimal capacity that we need to carry all of these weights given this many ships now you might notice that the context of this problem they're talking about the number of days that it's going to take us not the number of ships but I think thinking about it in terms of the number of ships makes a lot more sense because it's equivalent to this problem and I think they're probably just trying to make it more confusing by making it number of days so let's think about it in terms of number of ships so for example if the number of days aka the number of ships is equal to two that means we have to load all of these weights onto the two ships and we have to choose the minimum capacity of our ships each ship will have the exact same capacity but we have to choose this value maybe let's try choosing one for the capacity so when now when we break up the array we have to start at the beginning and create contiguous chunks our first chunk is just going to be one that's going to fit on the ship and then we have a second chunk that's two well that's not going to fit on the ship so it's not even possible to do this with ships with a capacity of one this is is the first observation that I made when I was solving this problem that at the very least the minimal possible capacity that we have to choose will be the max value in the input array in this case it's five so that's the lowest capacity we should even try going with so let's now change this to five but even knowing this but even knowing this how do we make sure we minimize the solution with a capacity of 5 we could do this subarray it has a sum of three we could then do this subarray in another separate ship that has a sum of three we can't include both of these together because that's a sum of seven we can't fit those in a single ship but you can see we're already running out of ships we have two ships and we'll need a third one for this and a fourth one for this that's not gonna work so now what should we do we tried five that's not the minimal answer it doesn't work so then maybe let's try six that won't work either but the only way we'll know is if we go through the entire array we can load these three on a single ship this on a single ship and this on a single ship that's three ships but we can only have two ships so this is a Brute Force approach but you can tell it's gonna be N squared is there any other observation you can make well we know we're gonna need at least this much capacity is there an upper Bound for the capacity as well well for sure at the very least we know the highest possible capacity we would want to choose would never be higher than the total sum of all of these weights because why would we do that when we're trying to minimize the capacity we don't need a ship with more than this much capacity and if we have multiple ships we'll probably need less than that but this is still a good upper bound the sum of the input array so in the context of this problem for for our capacity we know that the lower bound is going to be 5 that's the maximum value in the input and the upper bound is going to be the sum of the input array which in this case is 15 so this is our search space we know our solution is somewhere in here so we can try the Brute Force approach going through each of these but an even better approach would be to run binary search on this search space now that we have decomposed it into a binary search problem that is going to be the most optimal solution and if you're wondering how I was able to figure it out well as soon as I noticed that the capacity had a lower bound the next question I asked myself is does it also have an upper bound and the answer was yes as I just explained and as soon as I knew that I knew this was similar to another leak code problem that I had solved leak code 875 and this problem is nearly identical so it's all about pattern matching I have a video on this problem as well if you're curious It's Coco eating bananas but now let's simulate a binary search on this so I'm going to initialize our left bound as being five just like down here and our right bound is going to be 15 for our binary stretch we're going to take these two atom together and divide by two that's going to lead us to a mid of 10. it's not a traditional binary search like we do like on here like left and right but we're going to be searching this so it's a bit different but with a mid value of 10 what does this 10 represent it represents the capacity of the ship we have two ships at most so let's try this a ship of 10 capacity we can fit this guy this guy this guy and this guy I would know that by summing all of them up and they sum up to 10 we can't fit the 5 though but now we can add it to its own ship so with a capacity of 10 it does work but we're trying to minimize the capacity so let's try again with a smaller value so what I'm I'm going to do now is set the result equal to 10 that's the minimum so far but I'm now going to try to lower my search space to find maybe an even smaller value so I'm going to change the right pointer now to M minus 1 that's 10 minus 1 which is 9. so now let's try adding these two dividing by two that's going to give us a mid of seven so a capacity of seven can we fit all of these with two ships with a capacity of seven we can fit this this this and we can't fit the four but we can add it to its own ship but with a capacity of seven we can't add both of these so seven does not work our result is going to stay nine but now we actually want to increase our search space so we're gonna set left equal to Mid plus one it was seven so we're going to set it to seven plus one which is eight and at this point I'm just gonna fast forward and and tell you if we try a it's not going to work we're gonna get this and this and this in its own ship but if we try nine we're gonna get these three in its own ship and this in its own ship that does satisfy the requirement we only needed two ships and this happens to be the minimal capacity that we needed among all of them that we tried so that's the solution now in terms of time complexity it's going to be n because for every capacity we try we have to in the worst case iterate through the entire array so that's where the N comes from now multiply that by the binary search at first you might think it's log n but what we would log is the size of our search space what is going to be the size of the search space in the worst case well the lower bound maybe might be zero or something like that but the upper bound is where the time complexity is going to come from because it's going to be the sum of the input array so let's just say m is the sum of the input array now it turns out that m is not going to be like a huge number because each individual weight is capped at being less than or equal to 500. so this is a pretty efficient solution about as good as we can get so now let's code it up so the first thing we're going to want to do with this pretty non-traditional binary search is to initialize our range we know that the lower Bound for the ship capacity we're going to need is going to be the maximum of the weights and the upper bound is going to be the sum of all of the weights and we're going to initialize our results since we're trying to minimize it initializing it to zero wouldn't be great so we're going to initialize it to the maximum of our search space equal to R But ultimately we're going to try to minimize it so now to move on to the actual binary search this is how I like to code it up because you can pretty much do it almost the same way every time I usually set left less than or equal to the right pointer then I compute the mid so the simplest way to do it is left plus right divided by 2 though sometimes this can give overflow but then we want to know does this m which is the capacity maybe I should rename it cap can this ship all of the weights given this capacity can we ship all of the weights if true and I'm going to Define this helper function in just a minute but if it's true then we're going to do something otherwise we're going to do something else if we can ship it maybe this is a new minimal result so we're going to set the result equal to the minimum of itself and the capacity that we just computed and we're going to update our range we want to now try to find an even smaller capacity so we're going to set our right pointer to M minus one in the other case we would want to increase our range because we're trying to find a a higher value so we're going to set left equal to Mid plus one after this binary search is over we know result will have the minimum capacity so we're just going to return that now the only thing left to do is our helper function which we know is just going to be a loop we're going to Loop through the entire input array so can ship given some capacity so we're going to go through every way in the input weights what we're trying to do though is count the number of ships it's going to take us I'm going to initialize that to one because we know we're going to need at least one ship and I'm gonna set the current capacity of that ship equal to the capacity that was passed in as a parameter so now I'm going to go through every way and we're gonna subtract from the capacity the current capacity the weight that we're adding to the ship but it's possible that the current capacity can't hold the weight meaning the current capacity subtracted by W is going to go negative that means the current capacity can't hold the weight so then what we're going to do is increment the number of ships that means we need another ship let's increment that by one and then reset the current capacity equal to the original capacity this is a fresh ship therefore it should get a fresh capacity and then we will subtract from the current capacity now if we execute this if statement this is never going to make the capacity go negative because remember our search space was initialized like that deliberately we took the maximum weight so no matter how big an individual weight is it's never going to make this go negative if it's a fresh capacity after all of this is done we're going to return the result the result is can we ship or not and we know that if we take the number of ships that we computed is less than or equal to the number of days that was given as a parameter which you know I've pretty much ignored the context of the number of days this should just be the number of ships but oh well that's the entire code though and of course I called these M instead of cap because that's what we were doing in the drawing explanation so let me fix that and rerun it as you can see it's pretty efficient if this was 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