Max Chunks To Make Sorted - Leetcode 769 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem Max chunks to make sorted I feel like there should be another word after that but anyways we're given an integer array of length N N's not like a parameter to this problem but the numbers that were given are going to be in the range from 0 to nus1 so we're going to have all of those numbers so let's look at a concrete example if n equal 5 that's not a parameter again we're going to be given an array so we can just take the length of this to maybe get the N value but we will be given the integers 0 through 4 and while the problem description is pretty short I think it could be a little bit confusing so the idea is that we want to split the array into some partitions so they will be contiguous I guess even though I don't think that's like specifically stated but basically like we could partition it kind of like this where we have these values and these values and these values what we want to do is split this array such that if we take each individual portion so this portion here this portion here and this portion here and we were to sort this and sort this and sort this so basically piecewise sorting sorting this part individually and then sorting this part individually Etc could we form a entire sorted array and basically what is the largest number of chunks or partitions that we could make again that can be kind of confusing so think about for this example what would the answer be well the max number of partitions so ideally we want to be greedy right we want to maximize the number of partitions they don't give us the word maximize I feel like largest is not the technically correct word to use in this context so let's think of it in terms of the max number like we're not trying to make the chunks large I feel like using the word large here can make this confusing but we're trying to maximize the number of partitions so ideally like the maximum would be this like partition every single number and then the max possible answer we could have is n in like the best case and it looks like this particular example actually uh satisfies that like if we were to just sort each of these individually which is not doing anything and it basically means that the original array is sorted but consider the example over here where it's reversed think about it for a second think about this all we need to solve this problem is really just a couple key observations so let me try to walk you through those this whole thing I'm trying to like place the partitions what am I going to do dynamic programming am I going to do two branches like for every single spot either put a a split there or not put a split there I mean maybe I guess that can be our backup plan but let's just think for a second in this first spot I need their to be a zero right I'm just looking so far at this portion just a single element I need this to be zero and if it's a zero fantastic then I put the line there now if it's not a zero what's going to happen think about it this is part of the partition that's going to belong to the first element like this uh could be a partition like we could put the line here or we could put it here and then this would be the partition or we could put it here this would be the partition well at the very very least we know that we need a zero in this spot so would we just wait until we find the zero like would we just say this is the partition well yes in this example it is the case so naively you might think okay so I need the zero in this spot as soon as I see the zero I can just put the partition right well not quite let's think about it don't just go based on like the first example feel free to come up with examples of your own sometimes that is necessary to solve these problems so let me swap these let me put a zero here and a three here now going based on our previous approach we would say like this is the partition because once I see the zero then like if I were to individually sort this part I'd get the zero here and the four here and then these values what would they be and I think once you kind of ask this question you've pretty much solved the problem well provided you know a bit of math and I guess just some of the patterns they're not like complex patterns to be honest like if you just go through the neat code 150 which is completely free like I guarantee you'll understand them pretty well just a little bit of math and prefix sums but uh before we even get into that think about this what we're trying to do is get the entire array sorted we need a zero here and we need a one here and we need a two here and we need a three here and we need a four here now it becomes kind of clear like this is the array that we're trying to create and when I'm trying to pick the first partition what am I trying to do I'm asking the question can I put the first partition here I want to be greedy I want to put the partition there that's what I want if I can do it but I can't how do I know I can't because this value is not a zero okay let's put uh the partition here let's try to once again I can't I have zero and four but what I needed was zero and one doesn't matter what order they were in but I needed them well I guess order does matter cuz you know we could have put the partition here but I hope you get the point we need 01 we have 04 so that's the problem and then we can kind of just keep going like that now how do we make that comparison are we going to compare the subarrays we could I mean we could say this is the expected output this is what we have but could we do something even more simple because I mean how many different partitions could we make we could have like this as a partition or this as the first or this or this or that you're probably thinking okay sure once you get the first partition however you do it well how are you going to get the second partition well the second partition doesn't necessarily have to be distinct from this one because this one sort of has a dependency on the previous one anyway so again how do we make that comparison I think if you just know the math it's not that difficult like the fact that the numbers we were given are 0 through n they are different numbers this is what the expected array is supposed to look like if we put a partition here then we expect the sum of this to be zero if we put the partition here we expect the sum of this to be one if the sum of this is one we guarantee we have 01 because it's not like we have any other choices and so then you get here 0 1 2 the sum has to be three here sum has to be six and even if we did the first partition now we're looking at the second partition well if we want to put the partition here we expect the entire sum of everything we've seen aka the prefix sum hopefully you've seen this pattern before if not definitely I check out NE Cod iio at least at some point uh but that's the idea so long story short to solve this problem we can say this I look here I'm iterating basically so it's a linear scan and I'm Computing the prefix sum so right now I have at every step I'm going to have my current sum and as I'm doing that I can iterate over the numbers 0 through n pretty much at the same time it's easy to do that and since they're isn't a match right now don't put the partition there and we kind of just keep going like that so just keep adding numbers get the current sum um also at the same time get the expected sum compare them just keep going and for this example it's going to take the entire array for us to arrive at like the expected output there should have been three here sorry and when you think about it it does make sense that it would take the entire thing because if you look here we don't have all the numbers here again we don't have all the numbers the fact that we have a four we kind of already know that we have to wait until we at least get there another way I guess to think about this would be just kind of keep track of the max number and in fact I think that's probably easier to code up so I'll go ahead and do it this way but if you do it the other way I promise you it'll work I just think this was maybe a little bit easier to kind of explain but now that I think of it this might have been the easier way so just to make sure we visualize this when we see a number we know whatever the max is right now it's four we'll have to at least wait until we get to this index before we can make a partition guess if you want to you could kind of make a jump so you could optimize this slightly better than like a standard linear time algorithm but not like in terms of Big O it'll still be linear in terms of Big O because the worst case could be an example like this one where we're just kind of jumping uh by almost zero each time like this is the partition this is the partition and yeah just to go through an example that has not like five and one partition let's look at a different one so just a quick dry run here we have one okay I have to wait release until I get there and so now I'm here the max which is one matches the current index which is one so just to put the indexes here so here I'm going to put the partition okay now I'm here I have two that's the max I've seen so far I'm at index two so great I put the partition I'm at three index three put the partition so it looks like we had one two three four partitions we can just keep track of like a counter I'll do that with the result variable so let's code up this linear time approach I don't know if you guys care about this but I was curious what my original submission looked like on this about four years ago uh no data so this one was I believe technically a Brute Force solution I think this was n squ actually kind of used the same idea and I think this one looks like this is the same as the one I'm going to code up today so let's go ahead and get into it so what we want to do is go through the array I'm going to use en numerate in Python because it's very nice we can unpack the index and the number at the same time because we're going to need both of them we want to maintain the current Max it's going to be the max of N and whatever the current Max originally is what is it originally though well we're given 0 through n so I guess ne1 isn't a bad value to set it to and let's also maintain the result so that's the count of the sorted chunks like the different partitions and that's what we're going to return so down here and now the problem is as easy as just saying if the current Max is equal to the index increment the result by one let's run it and it looks like it works I'm pretty sure it's efficient at least in terms of Big O and I think the code is as clean as you can get it I mean I'm sure some of you can put this into a oneliner or something but in terms of interviews I think this is a sufficient solution thanks for watching and I'll see you soon