Minimum Number of Removals to Make Mountain Array - Leetcode 1671 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum number of removals to make Mountain array and before we get started I will mention this is a difficult problem I'll try my best to explain it and I honestly think by the end of it you will understand the solution but you might still feel discouraged you might feel like you wouldn't be able to come up with the solution by yourself and in these kinds of moments the best advice I can give at least what's worked for me is I just try to appreciate how elegant some of these Solutions are the solution to this one is particularly nice and I know it's stressful to be preparing for interviews and all that but I think it's also nice to just take a moment to appreciate algorithms like this one the idea is we're given an input array which is going to be at least of length three and that's important because there is something called a mountain array by definition it has at least three elements we can pick an index I in that array if it's a mountain array where I will not be one of the end points so I will be like a valid index somewhere in the middle so for example if you just take a look at these three elements here and just ignore everything else in the array we could say our index I is this this is kind of the peak of the array and so this itself is considered a mountain array because every value to the left of index I is in increasing order and it is less than that middle element at index I and everything after index I is technically in decreasing order there's just a single element on both sides but that element is less than the middle now if we were to change the array to make it something like this 5 6 let's say 2 and 1 this is still technically a mountain array like it's increasing up until it gets here and then it's decreasing now if we change it to this this is not a mountain array because we cannot pick any index I where we would have increasing and decreasing if they're equal it's not a mountain array so if you have something like this 5 665 this is not a mountain array we can't have I here or we can't have it here because then the elements are not in increasing and decreasing order since these are equal this like would not count as increasing so now that that definition is out of the way this problem is specifically asking us what is the minimum number of elements that we would have to remove move from this array to make it a mountain array and in this example it happens to be three we can remove this this and then this one and then if you look at the remaining elements we have 1 5 6 3 one this is a mountain array where do you think we are going to put the middle of the mountain when I say middle I don't literally mean like it has to be in the Midway point I just mean like the peak of that mountain and so of course it would have to be here cuz this is where all elements like increase to and then they start decreasing after that so this is a difficult problem and as is the case with difficult problems like this there's so many different trains of thought that you could have when trying to approach this one rather than listing out all the approaches that won't work I will try to show you a somewhat Brute Force approach like how can we even conceptualize this problem how can we kind of break it down into something that will have an algorithmic solution and then we'll try to optimize it so the idea here of course is we want elements to be in increasing order up until some point and then we want elements to be in decreasing order so you might think well maybe a monotonic stack is going to be helpful and that's an approach that gets complicated quickly and that's how I kind of knew that okay maybe there is a better way and then I approached it in terms of how can we even just break this down what would a Brute Force solution look like well that might involve picking the peak of the mountain so let's just try what if this was the peak how many elements would we have to remove well we want everything to the left to be in increasing order up until this point and it looks like that's not even possible the reason I said that this can't be the peak the reason I just skipped that and just started from here is because we need elements to the left of the peak and we need elements to the right of the peak so this would be the first valid choice but it looks like even that isn't going to be valid cuz nothing to the left is less than this so let's try the next spot over here once again we run into the same issue nothing on the left is less than one so let's try over here okay so if this was the peak we want to maximize the number of elements here in other words we want to minimize the number of removals so what are some possibilities well if we just have two then we can't have one after it because those are not larger than two so then we would just have this and if we pick one we obviously can't have two and we can't have the one that comes after it because these need to be in increasing order so it would just look like this or it would look like this either way it doesn't really matter they're all the same length so we're going to have to remove two elements on this side regardless now what about elements that come after it we have to remove the six it's greater than five we can keep the two but if we keep the two then we have to skip the three and then we can keep the one or we could skip the two and keep the three and the one so we could keep two elements on this side and we'd have to remove two of them so that's four removals and we could kind of keep doing it this way but the way I'm showing this is a bit misleading because we're picking every possible element as the peak or let's say the pivot I'll start using that word the pivot of the mountain that's going to be o of N and then to figure out what's the minimum number of removals on the left side and the right side of that pivot it seems like it's a linear algorithm so that this approach this Brute Force approach I'm showing is an N squ Solution that's actually not the case to find the minimum number of removals on either side of that pivot it's actually not trivial that's the complicated part about this problem figuring out which algorithm you can use on that remembering that that algorithm itself is actually its own problem it's a leak code medium problem and it's a dynamic programming problem which you know makes it more difficult for many people and then realizing how to optimize this so that's what I'm going to be focusing on if you do it the naive way you will arrive at a n cubed solution so first let me mention there is a very popular algorithm called Lis it's the longest increasing subsequence and yes it actually happens to be a NE code 150 problem if you head over to n code iio go to the 150 list and you go down to the one-dimensional dynamic programming section you will see that one of the last problems in that section because it's a difficult one longest increasing subsequence highly recommend you solve this problem and get really really good at it I do have a pretty good video explanation on it it is leak code 300 I will be briefly explaining this but if you're new to it I would recommend checking out the other video If you see what I've kind of been doing when we pick the pivot we want to minimize the number of removals on this side in other words we want all the remaining elements here to be in increasing order and they don't have to be contiguous like if I could have removed this one and these two were in increasing order that would have been fine we're not looking for sub rays and they don't use that word in this description the word that I'm thinking of it's called subsequence so that's the way to describe what we're doing here subsequence when you think about it what we're doing here is when we pick a pivot for the elements on the left we want to find the Lis the longest increasing subsequence and on the right side we want to do the opposite we want these elements to be in decreasing order and they don't have to be contiguous so in other words we're looking for the longest decreasing subsequence now there is a catch when we say longest increasing subsequence we want those elements all of them to be less than five they need to be increasing order and be less than five and for this side they need to be less than five but they need to be in decreasing order now if you remember Lis longest increasing subsequence it's not super difficult to figure out how to code up the longest decreasing subsequence it's pretty much the exact same code with just like a couple lines changed but that algorithm is an n s algorithm in other words finding the longest increasing subsequence here or longest decreasing subsequence would be n^2 time if we're doing that for every single pivot that's how we're going to arrive at the N cubed solution not a bad solution but there is repeated work imagine instead of doing that for like this and then doing that for this and this Etc we just found the longest increasing subsequence of the entire array now that's a dynamic programming algorithm I'll quickly walk through it right now and you'll see that by doing that we actually end up solving all the sub problems as well if we want to find the longest increasing subsequence sorry I'm messing up my words of like the entire thing though we will have to find all the others and you also realize that that algorithm is a very natural one for this because if I picked this as the pivot what I'm saying is I want to know what's the longest increasing subsequence ending at this element if it's ending at this element we already guarantee that everything to the left of it is less than five so thus they're in increasing order and you can see why it would be similar with the longest decreasing subsequence okay now let's just get into what that algorithm is and how we're going to do it the Lis algorithm works like this we start out with just the first element of the array what's the length of the longest increasing subsequence ending at this element well the length is going to be one and the last element is going to be two because if it's ending at this element this is the last element we're only concerned with the last element because that's how we know that it will be in increasing order because if five is greater than two we know that this can extend this subsequence we just need to compare it with the last element because we already know they're in increasing order okay so now we continue we're here this is a one element so we can only add this to previous subsequences that had an element less than one we scan through all of these it's just one this time that element is two it's not less than one so this has to start with its own subsequence which is just one so this is the length of the subsequence this is the last element in that subsequence this is one so same thing we'll scan through both of these none of them are less than one so we still have a one here now we have five we scan through all of these all three of them are less than five so what we would do is say this by itself is of length one and we could add the maximum of these three all of them are one so we say 1 + 1 and then we get a two here that tells us that the longest increasing subsequence ending with a five is going to be of length two and we can continue so this is six uh we'll scan through all of these all of them are less than six the maximum is two so 2 + 1 is 3 continuing this is two only these two are less than that both of them are of length one so 1 + uh one is going to be two here we have three these are less and this is l less than three the maximum length of all of these is 2 so we say 2 + 1 is 3 this three means that the longest increasing subsequence ending at this element is going to be of length three this is what it could look like these uh that I have circled and finally we get one here and that's going to be one so now if I was going to do the original algorithm I was doing and let's say I picked this as the pivot I would ask myself what's the length of the longest increasing subsequence ending at this element it's two so that means including this element there are two elements like on this side that we can keep and thus there are two that we have to remove how do I get the same for the right side what question would I even want to ask I would say what's the longest decreasing subsequence starting at this element not ending at this element but starting at this element in this case it is is 53 1 that means there are three elements and thus there are two that we have to remove so that tells us intuitively what we need when we compute the longest decreasing subsequence for each element we want to know starting from here what's the length of the longest decreasing subsequence if we're doing it that way we will have to iterate through the input in reverse order to populate that cuz here if we had increasing we're going left to right if we're doing a decreasing we're going to be going right to left okay so starting from here the LDS algorithm is going to be similar we have one just by itself technically that is a decreasing subsequence we can put one here we have three so we're going to scan through everything on the right we're looking for elements that are smaller than three we found one the length of the subsequence is 1 so we say 1 + 1 we're going to get two here we have two we scan here we only find one element less than two 1 + 1 is going to be 2 6 we scan through all of these all of them are less than six the max length of them is two so we get 2 + 1 that's three here and I'll just quickly go through the rest so five looking on the right these three are less than five the max length of those is two so we get 2 + 1 that's three again and one here nothing is less than one so this will be one here again nothing is less than one this is one two uh there are three elements less than two all of them have a subsequence of length one so the longest decreasing subsequence starting from here is of length two now that we have this solving the problem the original problem is going to be trivial I'm going to still scan through the input picking each of any of these as the pivot and let's just say arbitrarily our pivot was over here I would say what is the longest increasing subsequence ending at this element it is of length two so there are two elements that we can keep in including this one now I'm going to ask what's the longest decreasing subsequence starting with this one what's the length of it three so that means we can keep three elements including this one let me just review to you what we just did with this two we basically said okay we can keep this and let's say we can keep that one with this three we said we could keep this and we could keep a two more on the right side of it let's just say we pick this one and this one so we double counted the middle element we double counted the pivot remember we're looking for how many elements we have to remove so how do we calculate that well uh let's put it this way I started with n elements in this example that's eight so I have N I got to keep two elements these two so I'm going to minus that two from them or l i of I let's say or I is the pivot I'm also going to subtract from it the LDS of I that would tell us we're remov moving three elements now I'm going to do a plus one because we double counted that one so that's where the plus one is coming from so with this math we start with eight elements we're keeping these two and we're keeping these three and then the plus one is to counteract the one that we kept twice so this formula will compute the ones that we have to remove it'll compute one 2 3 4 the math will be 8 - 2 - 3 + 1 that will be four and in this case that is not the correct answer so the correct answer is when the pivot is in this position because we get 3 and 3 so that'll be 8 - 6 + 1 that will be three that is the minimum number of removals now there's one difficult thing about this approach and the hardest thing is recognizing this the same thing I was talking about with the Brute Force solution what if our pivot was over here now we know that this is not a valid pivot cuz there's no element on the left side of this that is less than one so that can't possibly be the pivot now how do we know that with the data that we just collected over here how would we know that this uh well we're going to skip the last element and the first element anyway but imagine that we weren't how would we have known that like let's say there's a one on that side and then we have a one and one here how would we have known that this is not valid because either the longest increasing subsequence from that pivot is going to be one or the longest decreasing subsequence is going to be one because when you look at it from this element actually there aren't any elements on the left that are less than it there also aren't any elements on the right that are less than it so if either the Lis or the LDS are equal to one we're going to skip that as the pivot in this example I don't think that would matter but imagine if we had an input uh something like this maybe maybe this is like 8 and this is seven this can't be the pivot cuz nothing on the left is less than it but there are plenty of elements on the right that are less than it so it might lead to us uh getting an incorrect result I think you know this would have been four here and in this case maybe it doesn't matter but you can imagine that there are some examples where this would have been really big and it would have thrown off our answer anyways with this approach Computing this and this is going to be o of n^2 for each of them and then after after that we will just scan through the input and that portion will be linear time let's code it up so for once I'm actually going to get the length of the input array up front because we're going to be using this several times and I'm going to compute the Lis and LDS arrays so let's start with the increasing subsequence I'm going to initialize that array to all ones because each of them will at least be a subsequence of length one for computing the value in each position I uh let's use n to compute that position we need to iterate through all positions before that position so for J in range I and only if the element at J the element to the left of I is less than the current element the current element is at index I so if nums of J is strictly less than nums of I not less than or equal but less than I then we can update the subsequence length at index I we want to try to maximize it so either it'll stay as it is or it will become one plus the Lis ending at index J because we already confirmed that they are in increasing order so it looks very easy when I do it like this but if you're new to this algorithm it's definitely not easy but once you practice it enough it does become pretty easy eventually so now let's do the LDS longest decreasing subsequence like this and this time we're going to iterate in reverse order for I in range n and then I'm just going to reverse this like that in Python it's a nice readable way to do it and for this one we're not going to be looking at elements to the left of I but we're actually going to be looking at elements to the right of I so let's say for J in range I + 1 up until n and for this one I want to make sure that the element to the right of I is less than the element at I so it's similar to what we did up above like this and if that's the case then I can update the length of the longest decreasing subsequence at index I and I will set it to the max of what it already is or 1 plus uh the subsequence starting at index J this is the bulk of the problem now we can just do the linear scan down here for I in range 1 up until n minus one we're going through all possible pivots and what we want to do is this we want to update the result so let me actually declare the result up here it'll initially be zero that will be what we're trying to return the minimum number of removals we're trying to minimize this so actually instead of initializing it to zero let me just give it a default value I could do float of infinity like a really large number but in the worst possible case we're never going to have to remove more than n elements they did mention in this problem that it's guaranteed that we will be able to make a mountain array out of the input so I will set it to this and we're trying to minimize that let's do this Min of itself and that calculation I mentioned n minus the Lis ending at index I minus the longest decreasing subsequence starting at index I and then A+ one to negate that middle element that we double counted the reason it's a plus one not a minus one is because we're minusing these this calculation is Computing the removals not the elements that we have left over and the trickiest part which I mentioned earlier is this we only want to do this if both the Lis at I is greater than one and the LDS at I is greater than one then we want to execute this in other words we could say the minimum of both of them is greater than one so this is the entire code let's run it to make sure that it works and as you can see it does and it's pretty efficient if you found found this helpful check out n code. for a lot more thanks for watching and I'll see you soon