Put Marbles in Bags - Leetcode 2551 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today I actually wasn't going to make a video for today's problem but I saw that the problem is honestly easy enough at least in terms of like the explanation we're going to be solving put marbles in bags and I have I think like the next three or four daily Le code problems pre-recorded and if you're wondering how do I know which problems are going to be the daily problems well on Le cod's homepage if you scroll down you see that there's a feed of Articles being published these are going to be the daily leak code problems and I have recorded videos for all four of these these after that you might not see me uh for a while so you're going to have to you know get along without me I'm sad to say but the idea behind today's problem is that we're given this array of positive weights I believe and we want to split it into K different contiguous subarrays they don't tell you exactly that but you can pretty much figure that out from the description so suppose we cut it into this subay and then maybe this one so let's say we have this and this that is a valid way to do it continuous subarray here and continuous subarray here they give us a bit of terminology and by the way the K parameter here was two that's why we do two sub Rays exactly two sub rays and we're guaranteed that K is always going to be less than or equal to the length of the input so it should be possible for us to do this okay with that said the terminology is uh starting down here we say that the cost of a specific back but I say subay because I don't really care about the story that leak code has to tell us in today's problem I say this sub's cost is going to be the sum of the end points so this and this is going to be the cost of that subay and this and this is going to be the cost of the second subarray they give us another word they call it the score I call it the sum of all of the costs because that's exactly what it represents so again I don't really care about the words that they have for us we say that the score is the sum of the costs and what we want to do is so this was one way that we partitioned these arrays into K different contiguous subarrays so we say that okay the sum here is going to be um I believe 1 + 3 for this one and then 5 + 1 for this one so the total is going to be I believe 4 + 6 now we could have done it differently as well another possible way would have been to put the split over here so I uh let's just note down that the score with the blue way was equal to 10 and then another way I could do it is like this this and then this so then we say okay this the left and right end points of this are the same it's just two or or rather it's one for both of them so one + 1 is equal to 2 for this other guy over here we have 3 + 1 so that's going to be 4 four so the cost of this one was uh two the cost of this one is four so we say that the total score is going to be 2 + 4 6 so this was a separate way to do this and a third way possibly would have been like this maybe take this and then that but I'm not going to show you that um but the ultimate result that we're trying to do is not return the maximal score but actually what we want to determine is what is the maximal score and what is the minimal score that we could possibly get because once we know that we just take the max subtract from it the Min and then that's what we want to return so don't let leod fool you don't let them confuse you what they're asking for is relatively simple once you kind of know now in terms of how we're going to solve the problem I guess it seems like maybe doing this recursively will definitely allow us to arrive at the correct solution because we could try every single possibility and then among all of those possibilities with our recursion we could collect what which one was the minimum and collect which one was the Max and then compute the difference it's possible and I think we can actually optimize this with dynamic programming but I believe and I didn't code this one up I believe the time complexity is going to be something like n^ 2 * K it might be possible to do K * n but I'm pretty sure it's going to be n^2 * K because roughly like for any given part we have have like n different choices for our recursion and then the height of this tree I believe is going to be K and obviously that's going to be exponential but when we um have the parameters we will have I and K for our recursion and then inside of that function itself there's going to be a loop so that's where I'm getting the n^2 * K from but that's not the solution we're going to cover there's actually a easier solution which is greedy now to arrive at the greedy solution you have to make observations you can't just think about this problem from like a black box perspective you can't just naively say okay well I'm just going to try to maximize it I'm just going to try to minimize it I'm not going to take a look at what exactly is going on under the hood I'm just going to think of that as a black box yes that's the lazy way to solve problems yes that's why I say when I'm coding up a recursive solution that I'm just turning my brain off because really I am I'm just following a template inside of my head and I'm not even thinking about the problem any further but when you think about the problem a little bit further this is what you find let's look at a larger example hopefully this turns out to be a good example now obviously it's not guaranteed that the input array is going to be sorted um I believe the answer to this example is going to be 10 so with this example let's just try to draw things out and see if we notice anything this is let's say one way I could split this up into two subarrays and then here I have 1 + 1 and then for this I I have 2 + 7 okay remember we only care about the end points so in some sense there is going to be some repeated work I don't know if you could call it repeated work but there is a pattern going on over here and that's what leak code is about pattern recognition not only in terms of which data structure or algorithm but also making observations about problems and noticing the pattern that's going on here let me show you the second split we could put a split over here and here and then what would I do I would say okay take 1 + 2 + 3 + 7 okay what am I going to do next I'm going to try this one 1 + 3 + 4 + 7 okay I'm going to keep going and eventually you might notice that something is going on I'm taking one again this time 4 + 5 that's where the split happens do you notice that we only care about the split values nothing in here or nothing in there and then once again we take the seven so it looks to me no matter how you slice it we're always going to have a one and we're always going to have a seven and maybe even if K was equal to 1 we would still have that because then we just have a single subarray and then we would take 1 + 7 so this is telling me something we care about what is the max score we could get the max sum of costs and we care about the minimum as well now I don't know too much about what the max or Min is but I definitely know in this example the max is going to have a 1 + 7 and the minimum is going to have a 1 + 7 now what about the rest of the terms in here well we're only going to have one split right there's only going to be a single split and so which split would we want to choose for the maximal probably the one that has the two biggest values so in this sorted array it becomes pretty obvious that for the max I'd probably want to put my split over here because take a look what's going on this guy and this guy I already have my 1+ 7 over here and now with this split I'm going to take 6 + 7 if you have a subarray of size one I guess you end up including that number twice that's not really a problem for us so now over here we're going to have 6 + 7 and now to do the other one down here I guess in my case with the sorted array becomes pretty obvious I'd want to put the split over here and then there because then I take 1 + 2 and I get this so the sum of these is three the sum of these is 13 so the total taking Max minus Min is going to be 10 so again do you notice any patterns do you notice anything that's going on well first of all if you have a decent math teacher if you had like a decent Elementary School math teacher you recognize that actually we don't really care about this right and also K was two but we only needed one split to get two sub Rays right this and this subay or this and this subay when the split is over here because if we do one split then we end up with two sub Rays if we do two splits we end up with three sub Rays etc etc so if we're given a k parameter of two we only need to perform one split and for the max we want to perform that split where the two adjacent values are maximized for the Min we want to perform that split where the two adjacent values are minimized so I hope I've given you enough intuition to solve the problem but if I haven't it's probably because this example is relatively simple it's because we only needed to do one split what if we had to do multiple splits what if the K parameter was equal uh to three instead well the 1 + 7 is going to be the same we're still going to take the end points because again no matter how you slice it we have one subray over here we're going to end up having a subarray that ends here and a subarray that begins here so I'm always going to have my 1 + 7 1+ 7 over here but you don't even need to account for those because they're the same here and same here if you take the difference between these terms you're always going to get zero so that's why I'm not really drawing them out and you don't even need to compute them when you take the Max and minimum so now with three splits how would I go about solving the problem well I guess I could try every single split and then among those collect in this case since is three I want to collect the two maximal splits and the two minimal splits but in general K is a variable so doing it K times is going to have some complexity associated with it so I think there's multiple ways to go about doing this one would be like the Heap based approach and the other would be the Sorting based approach I'm going to choose this one just because it's easier to code up I highly encourage you to try out the other one though just to challenge yourself this is a hard problem if you weren't able to come up with it on your own that's fine but if I show you the Sorting solution you should be able to come up with the Heap Solution by yourself or at least implement it by yourself but anyways finally to finish this up what we're going to do since we're trying to pick the biggest and smallest splits why don't we just compute all possible splits so in this case just to make some room here on the left I'm going to uh in this case get every possible split so if I had a split over here then the sum of these two values vales would be three if I put my split over here some of these two values would be five and I'm just going to kind of keep going if I put the split here some of these two adjacent values is seven so kind of just keep going I think 11 and then finally 13 so it looks like we had six different possible split values it does make sense because we can't put the split over here we can't end up with an empty subarray so we can split here here here four five six we had seven elements in the input we have six possible splits that makes sense so now among all of these splits it probably becomes obvious what you want to do K is three we take the two biggest splits and then put them over here 11 + 13 we take the two smallest splits put them over here 3 + 5 so we would get something like 24 - 8 so it looks like that is going to be uh 16 now keep in mind that the only reason that all these splits were already sorted was because my input was sorted if my input was not sorted this is not going to be the case and there's no guarantee that the input is going to be sorted thus we are going to end up sorting this ourselves so I believe the bottleneck in terms of time complexity is going to be that sorting which is going to be n log N I believe the space complexity is going to be roughly proportional just to n because that's what the size of the splits array is going to be so like I said this problem isn't too bad I think for a hard one I think the hardest part is just recognizing that the dynamic programming solution is not the intended one okay so let's go ahead and reset ourselves and so first thing I'm going to do is just get that splits array and I guess I'll be kind today and not show you the pythonic code even though we could do list comprehension and I always recommend people to Learn Python for coding interviews I promise you you won't regret it but anyways let's uh do this we want to go through the length minus one because we know that's how many splits we're going to have and we don't want to end up with an index out of bounds error so the way I'm going about this is this taking weights at index I plus weights at index I + 1 and we always know that this is going to be inbounds because we're not actually going up until the end of the array we're going one minus that so taking this sum adding it to splits uh like this and then we can take splits and sort it and then what we want to do is compute the Max and minimum score and if we care about the actual score itself we would do something like this we' take first of all uh weights at index0 the beginning of the array and the end of the array in Python you can get that with ne1 and then also the sum of the last K split values the largest K split values and in the minimum score we're going to do exactly this part and also the smallest K split values to get that it's pretty easy you take some of a slice of the splits array you go from the beginning up until index K minus one I'm going to put that in a variable actually cuz we're going to need it here I = kus1 so I'm going to replace this with I and then over here we want the last K split values so we would do this in Python if we want start at the last index from splits we would do-1 up until the end if we wanted the last two elements we do -2 since we want the last I elements we can do netive I and then at the end what we would return is um the max score of course minus the Min score now there's a bug in this code and the only reason I figured it out is because I submitted this code and then I got a wrong submission the reason is that we're actually missing an edge case the fact that we're taking advantage of python here and not using like a loop because think of the edge case when K is actually equal to one in that case we're not actually doing any kind of split in the array so this would end up giving us a wrong answer so to mitigate against that I just put an if statement up here I mean you could code this up with a loop that would also prevent it because if you're iterating K minus one * K is 1 that means you would iterate zero times so maybe a loop would be preferable to compute these parts but but I think an if statement is also fine if K is equal to 1 go ahead and return zero and also now I think it's pretty obvious why we don't include this part and this part if it wasn't already obvious before because when you do the difference they're going to be canceled out anyway so I don't have to put these here so now let's submit it and you can see here on the left it works it's pretty efficient thanks for watching check out n code iio for a lot more I'll see you soon