Check if There is a Valid Partition For The Array - Leetcode 2369 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem check if there is a valid partition for the array we're given an integer array nums and we have to partition it into one or more contiguous subarrays and the catch here is that each of the sub arrays has to be considered valid where this is our criteria to check if that subarray is valid and there are three types of valid sub arrays the first one is where the length is exactly two and each element is equal in the array so in this example they show us 2 2 alternatively it could be three three or four four basically it's length two and both values are equal so first thing that you might notice is that's pretty simple to check like we don't need a loop to check that that's something we can literally check with an if statement so let's take a look at the other two cases as well the second case is where the subarray is exactly of length three and the example they show us is four four four and you can imagine it can be five five basically length three all values are equal now that's also pretty simple I mean we can do that again with an if statement it might be a kind of long if statement but it's still doable I'd rather not use a loop if we don't have to it's not like the length of the subarray is a variable length it's always going to be three in this case last case it's also going to be exactly of length three this one is a bit more complicated though each value in the subarray for example three four five has to be in increasing order not just an increasing order a sub array like one three five this is not considered valid because they have to be incremented by one each time so a subarray like one two three would be valid one two four would not because each value has to be incremented by one in the sequence so once again this is pretty simple we can actually check this with an if state statement as well we can check that the left value is exactly less than the middle value and that the right value is exactly 1 plus the middle value now when it comes to solving this problem the first thing that you might try is the Brute Force like trying it recursively because there's not going to be an easy way to determine like a greedy way to split this up because there could be multiple ways and that's kind of obvious from the first example because we could take this I'll actually draw it out so here we could take this as the first valid sub array but we could also take this as the first valid sub array so that gets my brain thinking that we can kind of have a decision tree we can solve this recursively we have choices that we can make so one choice could be four four another choice would be three fours now all we want to know is can we split this up such that every single sub array is valid so we're either going to return true or false so we're going to be exhaustive here we want to explore every possibility so here how many choices do we have well we're kind of at this position that kind of tells us we should probably maintain an eye pointer telling us where we are because in this case we went two spots an hour here but over here we went three spots and now we're at the five so when we're here we can check three different ways we can check are these two values equal nope then we'll check the second case are these three values equal nope then we check the last case are these three values in ascending order where each is being incremented by one yep that's the case and at that point we select four five six and then our eye pointer will be all the way over here outside of the array and since we're only choosing valid sub arrays as we shift our I point or we know by the time that it's out of bounds we have found a valid solution we've found a valid partition and at that point we can go ahead and return true now just to explore this other side really quickly when our eye pointer is over here we don't have many choices actually we can only make the first choice we can only check are these two values equal and they're not and the reason we can only check that is of course because there aren't three values here to check if we tried to check if all three values were equal we'd get an out of bounds error and same with this other case if we check if the three values are ascending we'd get an out of bounds error so this path did not lead us to a valid solution from here we would actually return false now just because we solved the problem recursively doesn't mean we found an efficient solution but you can imagine that there are sub problems they're going to be repeated sub problems we don't care like if our iPhone got to this point we don't care how we partition the array there could be 10 different ways that we partition the array like imagine we had a bunch more values here it doesn't really matter to us this sub problem is the same regardless of how we partition these values this leads me to think that we can solve this problem with caching a dynamic programming technique where the only cache key that we will have is the index which defines the sub problem that we're currently looking at could be here it could be over here which defines this sub problem it could even be at the first index which defines the entire problem and of course each I index will be mapped to a true or false value and the number of sub problems that we have in this case is of course going to be the length of the input array which is Big O of N and each subproblem actually like I said is since these sub arrays are of length 2 or length 3 we're not going to need a variable while loop inside of our recursive function therefore each subproblem is basically going to be an O of one operation and that's why I'm getting Big O of n as the time complexity because there's and sub problems each one is going to be a constant time problem therefore Big O of n also memory complexity is going to be Big O of n from the DP cache I'll quickly code up the solution but I also want to show you the more memory optimized solution it's the bottom up DP solution it's going to be big of n time and Big O of one space but that's going to be later let's jump into the recursive solution now so the first thing I'm going to do is Define the recursive function I'm going to call it DFS because why not and I'm just going to have a single variable I and like I said the main base case is going to be if I is out of bounds therefore it's going to be length of nums and in that case we're going to return true because we were able to split it up now I'm going to quickly show you how we're going to call our DFS we're going to start at index 0 so that's going to inform how we implement the rest of the problem because we're starting at the beginning of the sub array so now there's a couple cases remember one is we're checking to two adjacent values so we're checking is nums of I equal to nums of I plus one but before we even check that we don't want to get an out of bounds error so let's make sure that we have two values in the first place we know that if our eye pointer is less than the length of nums well this tells us we have one value at least one value now if this is less than the length of nums minus one then we have at least two values so we want both of these to be true and I'm checking this first so we don't get an out of bounds error when we try to evaluate this part now if this does evaluate to true that doesn't mean we found a solution now we have to solve the sub problem so we have to call DFS again what do you think we're passing in well we probably want to shift our eye pointer two times so I'm going to pass an i plus two and this is what we would want to return but there are some other possibilities as well for example if three adjacent values are are equal and that would look pretty similar like this so now we're checking that but just like before we want to make sure we have at least three values so I'm going to copy and paste that and now I'm going to set it to minus 2 which guarantees that there are at least three values and if we do that we're going to call DFS on I plus 3. now I'm going to copy and paste this because we know there's one more case and that case is similar because we need to check three adjacent values but we're not going to check them like this we don't want to know if they're exactly equal we want to know if they're in ascending order so we want to know that the middle value is equal to the left Value Plus 1 and we want to know that the middle value is equal to the right value minus one so we can do that just like this now there's actually an issue with this code just because this happens to be true doesn't mean we want to return the return value I mean if the return value here is true that's great because all we need is one valid partition and then we can return true but if this were to return false we don't want to necessarily return false we might want to explore these two possibilities as well basically we have a recursive function here that is not branching at all that's a problem so instead of returning each time we call a recursive function I'm actually going to have a variable over here and I'm going to call it result and I'm initially going to set it to false and that's going to be the value that we return out here not false we're returning the variable so that's one Improvement but this is still not correct we want to now take result and set it equal to the return value of this function and also we want to combine these two cases as well the first thing that's common between them is that we're checking that the length is at least three we probably don't need to have this in both places at least not the way I want to write it so I'm actually going to have have an inner if statement here and you can also see by the way that the recursive call is the same for both of these cases so we probably don't need to call it twice that's another reason why I'm combining these so I'm going to cut this condition up here and paste it down here so either this is true or this condition down here is true if either of these is true then we're going to execute this DFS so now I'm going to clean this part up so now you can see we're checking is the length 3 and are either of these true and if they are then we call this but we don't want to return it necessarily we're going to set result equal to either whatever it currently is or the return value of this reason being if this returns false but this return true that doesn't mean we want to set this to false if any of these return true we want to return true as the result now the last thing that we have to do is add caching and I'm going gonna do that with a hashmap you can do that with a one-dimensional array so here we add an if statement we check have we solved the sub problem before is I in our DP cache if it is that means we solve the sub problem and we can immediately return and we don't have to do any recursion down here but if that's not the case then before we return our result down here we want to make sure we cache the value in our DP cache at index I just like this and now we're almost done actually I see an issue here we are missing a colon in our if statement and this should be indented whoops let me go ahead and indent that because it has to belong to the if statement scope so now let's go ahead and run the code to make sure that it works and as you can see on the left yes it does and it's pretty efficient but there is an optimization that we can make so we talked about how we solved it recursively and what we were kind of doing implicitly was building up a one-dimensional array well in my case I was using a hash map but basically this is the structure that we were building up we started at the beginning of the array and that was the solution like this is where we store the true or false value whether we can partition this array successfully but we also solved sub problems meaning like at this position this defines this sub problem and here we can partition this it follows case number three so here we would put a True Value because we are able to partition this successfully now the bottom up DP solution in my case following like the way I solve this recursively I'm going to fill up this array from right to left you could also do it from left to right but then it's going to end up different from the recursive solution that we implemented so that's why I prefer doing it from right to left but if it bothers you you can always do it the other way but in my opinion that actually ends up being more confusing at least for me before I start like at the end of the array and start solving sub problems we should probably just initialize the last three values first because first of all we know that the last value if it's just a value of length one then we have to put false here because there's no way to partition that successfully and for the last two values it's pretty easy to check just check are these two values equal in this case they're not so again I'm going to put a false here now for the last three values they're not equal but they are in ascending order so here I'm actually going to put a true value now we can start filling up this array from right to left it's a pretty short array but we'll still get a pretty clear picture of how to solve this problem in the general case and that is so now our eye pointer is going to be over here which is basically the last index minus 3 because we already filled up these three so here we know that there's three different ways that we could partition this array we could take these two values and if they are equal then we're going to take the value that's stored here and then put it there because if we can partition this like this then we want to know are we able to partition the rest of the array starting at this value and this is where we store the result of that but clearly this is false so we can put false here for now but also let's ask ourselves what about these three values are these three values equal nope they're not okay well are these three values in ascending order again no they're not if either of those statements were true then what we could do is take the values stored here and then move it over there but they're not so we can't do that now we're going to put a false over here and now we're going to shift our eye pointer to the left by one and try to solve the entire problem here so we're going to ask the same question are these two equal yes they are so then we're gonna try solving this sub problem and clearly there's a true here so at that point we're pretty much done with the problem now the other cases we would have checked is are these three equal or are these three in ascending order well they're equal so what we could do is take the value stored here it's a false anyway so we don't care about that false but we know we were able to partition it like this and grab the true from here and then move it there so ultimately the result of this problem is going to be true but there might be a thing that you noticed every time our eye pointer is in any particular position we don't really need the entire array in memory do we because there's only two cases either we partition the array like this in which case we would want the value stored over here or we can partition the array like this in which case we'd want the values stored at I plus three basically what I'm getting at is we only need three values in our array in memory at a time that's how we make the memory optimization from Big O of n down to Big O of one so that's how I'm going to solve this problem now so I'm going to leave this recursive solution here because we're actually going to use some pretty similar logic at least for like this portion of it the first thing I'm going to do is check if the last two values in our array are equal because what we're ultimately trying to do is build up a DP array of length 3 and for each position we want to fill in the slot we already know that the last value is going to be false because an array of length 1 can't be partitioned but we want to know are the last two values partitionable and we know that's the case if the last two values are equal in Python it's pretty easy we can take negative one that's going to give us the last value and we can take nums of negative 2 that's going to give us the second to last value now there's one Edge case our nums array actually could be exactly of length two if that's the case we can check that like this is the length of nums equal to two if it is we can return turn the value that we just computed in this variable if that's not the case then we pretty much know that the array has at least three values in it and that's where we can go ahead and pretty much copy and paste this code well not exactly because we're going to have to shift it around we'll not shift it but we're going to have to update this I pointer we want to check if the last three values are equal so we can check that like this negative 1 negative 2 and negative three either that or the last three values are in ascending order and we can do that by changing this to negative three this will be the value to the left of the middle element the middle element will be at index negative two and the last element will be at index negative one so now we can take these two variables and put them into our DP array just like this so now let's start looping we're going to start at the last index minus three so I in range length of nums minus four the reason it's minus four is because minus one is the last element in the array and we want to shift that by three so we put negative or minus four and we want to iterate in reverse order in Python it's kind of weird but we have to put a negative one here that will iterate until we reach the beginning of the array and we want to decrement our pointer so then we put a negative one there as well and by the time we're done with this Loop we want to return the first value stored in our DP array because that's going to be the result of the entire problem like can we partition from the beginning of the array so we're going to return DP at index 0. okay now this part is actually going to be pretty easy we want to know are we able to partition taking the first two values so we can check that pretty easily as numbers of I equal to nums of I plus one so this is pretty similar to what we did up above except now we actually have like a pointer and we're not just hard coding it and I think if you really wanted to you could rewrite this code such that we don't even have have these you could start our eye pointer I believe from like the end of the array and then you can kind of just move these inside but I think it's a bit more simple to just write it out like this this is actually not enough for this problem remember we want this to be true and we want DP at index one to also have a True Value y DP at index one well that's gonna be us shifting by one and then shifting by two so that's a possibility the second possibility is and this is the part where we're now going to say current or this condition because it could be possible that current is already true now so here we're gonna copy the code from down here in our recursive case so I'm literally just going to copy and paste it I'm going to move it here I think we're gonna have to update it a tiny bit so we're asking either the current three values are equal or the current three values are in ascending order but that alone is not enough remember we want this to be true and we want DP at index 2 to also be true and again the reason why it's DPI index 2 is because we want to shift our I pointer by 3 so we'd say one two three and we'd get the value that's stored there now after we've computed that we can actually just put current into our DP cache but it's not going to be as simple as just saying DP at index 0 is going to be equal to current because remember we kind of have to shift that window over to the left so actually we're going to be reassigning this entire array that's okay because it's only of length three so we're actually going to Now set it to current is going to go in the first spot DP of 0 is going to go in the second spot and then DP of one is going to go in the last spot so you can imagine we're basically taking these two values and then shifting them over by one so that they're here we're literally taking these two values and then shifting them to the right by one and then for the first value we're taking the value that we just computed and storing it there so this is the entire code it's memory optimized let's run it to make sure that it works and as you can see on the left yes it does and it's about as efficient I think I guess comparing the memory down here it does look like we used a lot less memory so if you found this helpful please like And subscribe if you're preparing for coding interviews check out neatcode.io thanks for watching and I'll see you soon