Minimize Maximum of Array - Leetcode 2439 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimize maximum of array this is a pretty tricky problem especially for a medium if you couldn't solve it definitely don't get discouraged we're given a zero indexed array where every integer is going to be non-negative so basically zero or greater than zero the way they describe this problem is that there are like a few operations that we can do I'll go through these but then I'll kind of explain a better way to think about this problem like a more simple way so I'll just use the same example that they do in this problem what we can do is choose any integer except the leftmost one and you'll see why in just a second so among any of these integers we are going to pick one of them suppose it's this guy we're going to decrement it by one minus one so this is now going to be six and we take that one that we decremented and actually move it over to the left over here so this is going to be plus one now four now since we can't decrement this the reason we can't decrement this is because where would the value go if we say this is 2 now that one is kind of lost that's not something we're allowed to do and given these operations we just want to return the minimum possible value of the maximum integer of nums after performing any number of operations so that's the simple part we can perform this operation any time we want like an infinite number of times if we want this part you'll probably have to read a few times to understand what exactly it's saying basically in this array we're always going to return the maximum value in this case it's seven but what we're trying to do is minimize that maximum value so one way to do it would be to do exactly what we did make this a six and make this a four now the maximum is six well it's in two spots but it's still six so that's what we would return but we can actually do better you can see in the output over here the result is actually five how exactly would we get to to that point well you kind of have to prioritize by taking the maximums and decreasing them as you would guess by decreasing this we're not going to get anywhere so for this guy let's decrement it one more time let's now say it's going to be a five I'll write it down over here and this guy is now going to be a five we took two from here and moved it to the left now our maximum is still six but we can make this a five and make this a two at this point we can't really do anything we could definitely get this smaller and we could probably get this smaller but this is going to be our bottleneck it's basically going to keep growing or the best we can do is just leave it as it is so in this case we return five now based on that kind of quick walkthrough you might think that we could go with like a Max Heap approach where we just take from this entire array and get the maximum value so that we can decrement it and try to lower the overall maximum if you try doing it this way you'll see it's pretty tricky and even if we could get it to work Arc the overall time complexity would be higher than the solution I'm about to show you and using a Max Heap how would we even know that we're done that's kind of the complicated part so there is a better way to do this and it has to do with a kind of again simplifying this problem first of all let's make an observation we know that the result can't possibly be smaller than the initial value in this spot because this value is never going to get any smaller it's possible that everything over here is smaller than this but we're returning the maximum remember so that's something to keep in mind this is initially going to be our result and now just going down this track of thinking let's see if we can arrive to A solution just by iterating through the array the reason we're going to start from left to right one is because that's what we usually do but also because we're kind of thinking of it in terms of sub problems what is the result of this subarray what's the minimize maximum of this subarray and then we can EXP ban that what's the result of this subarray and kind of keep expanding that just by adding a single value we couldn't do that the other way because when we take a value we're only allowed to move values to the left so just like we know that this subarray can't get any smaller the three can't get any smaller as a result our result will never be smaller than three we can use that same idea as we slowly expand this array like at this point when we just have two values here and what we're going to do of course is turn this guy into a five and turn this guy into a five once we get to this point we know that the result can't possibly be smaller than five so that's the idea behind this problem it's definitely not easy to come up with if I was your interviewer I would definitely give you a hint so now let's run through the algorithm we start at three and then we go to the next value seven what should we be doing here well our goal is to evenly distribute the values like if this is a 3 e and this is a 7 we want to evenly distribute the values how exactly can we do that well probably by taking the sum of the array and dividing it by the length of the sub array which is 2 in this case so in that case we would get 10 divided by 2 which is 5. we'd probably want to round up so in the case where we had something like 11 divided by 2 we'd get 5.5 but we'd probably want to round that up to 6 because remember we're trying to return the maximum so that's another observation to make then what do we do with that value five well we know that that's kind of the average of this subarray but in other words we know that this is going to be the maximum value so we would take this value and then assign it to the result but only if this value is actually greater than the result because notice the opposite case here what if these values were in the opposite order what if this was a 7 and this was a 3 then our initial result would have been seven by the time we're only at this part but then when we add this second value we have a sum of 10 we divide that by two now we get five should we take the five and assign it to our result no because if we previously saw a seven we're never gonna decrease the result so in other words we're always going to say result is equal to the maximum of itself and whatever this value is that we computed which in this case is five the reason is because as we mentioned earlier we can move values to the left but we can't move values to the right so now let's just kind of walk through the rest of this problem remember we calculated a five so that's what we're going to now reassign our result to and we don't really need to actually update the array so I'm not really going to do that but I guess I will just to kind of show you what it would look like but we don't really need to do that we just need to keep track of what our result is and also as we are adding new values like now we're going to visit this one one so this is our subarray at this point remember what we're doing is taking the sum of that sub array which now is going to be 11 and dividing it by the length which is 3 so this computation is pretty easy it's going to be less than 5 so we don't need to update our result in this case but another important observation is if we're keeping track of the total we probably don't want to have to recompute that every time so the easiest thing to do is just have like a variable to keep track of the total which I'm not really showing but it's pretty simple so I won't do that now lastly we get to this 6 here our total sum is now going to be 17 divide that by 4 which is the length and that's going to be 5 after we round up so our result is still not going to change and 5 is going to be the result that we ultimately return clearly the time complexity of this is not bad we're not using any advanced data structures we're just iterating through the array keeping track of the total and updating the result periodically so the time complexity is Big O of n memory complexity is Big O of 1. now let's code this up so the first thing I'm going to do is initialize our result to the first value in the array at index 0 and I'm also going to well before I do that actually since we're going to be iterating through every value in the input array except of course the first value so I'm going to say for in range starting at index 1 and then going up until the length of the array the reason we're skipping the first value is because we can't take values from the first value and move them to the left so it doesn't really make sense to do anything with the first one so what I'm also going to do is set our total AKA our prefix sum also to the first value so we're basically skipping the value at index 0 and then starting at index one now after we do that it's pretty straightforward just as I kind of talked about we're going to keep track of our total by just adding the value at index I every single time and also updating our result which is going to be the maximum of what it currently is as well as the total and we're going to divide by the length which is going to be I plus 1 because arrays are 0 indexed make sure not to forget that this operation we want to take the ceiling of it so math dot ceiling we want to round up that's what we're trying to do here so among these two values we want the maximum and we'll get that and we'll assign it to the result our result can never get any smaller and then we're just going to go ahead and return this I'll run it to make sure that it works and as you can see yes it does and it's pretty efficient though this was a small amount of code there's a lot of logic to it and I think it would be a decent interview question if your interviewer is willing to help you out I think it would make a good discussion trying to solve this problem 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