Maximum Width Ramp - Leetcode 962 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today I'll solve the problem maximum with ramp and before I even get into this problem I want to quickly say something imagine that this is like the normal distribution of people watching these videos from what I know about half of you guys only care about knowing what the solution is and then I would say the next like 40% actually want to know why the solution works and lastly we have the 10% the top 10% who actually care about the intuition to be able to come up with Solutions like this in the future and so of course I'm going to be covering like these two but I'm really going to try to focus on that last 10% mostly because I enjoy it and I hope you guys find it helpful so let's get into it suppose we're given an array like this we want to find the maximum subarray pretty much and I'll kind of describe what I mean by that but we want to find the maximum that satisfies two particular condition one is that these two pointers I and J have to be different and this pointer has to be less than the other one and second the value at that pointer that is less than the other pointer has to be less than or equal to the value at the other pointer so those are the only two conditions now when I said subray that's not entirely correct like if this is that subarray we actually just want to return the end minus the beginning so in this case that would be three which is the index here - 1 so we'd get 2 which technically is not the length but it's the length minus one so I think it's fine to think of it in those terms so of course to this solution there is a Brute Force solution you just go with nested Loops so starting here we want to find the longest subray we can create starting here so we have that I pointer there J pointer over here and just keep going compare the values this doesn't obviously form a valid subarray so go here it does like the values are less than or equal so we're good so we found one that's of length two so J minus I in this case is two we'll keep going and we'll find that now there aren't any other values greater than or equal to six so very important observation to make even though this is the Brute Force solution we're looking only for values greater than or equal to 6 if only there was a way we could early determine that there are no more values greater than or equal to six if only that was the case we might be able to optimize this solution but we can't so now we go to the next position and do the same thing so I here keep looking for values that are greater than or equal to zero this one is this one is this one is and this one is as well so the longest that we could create I think in this case is four and at this point like our Brute Force solution is going to keep running it's going to try the same thing from here here here and here but can't you kind of tell that I mean the longest we could create from here was this and the longest we can create from here is that we went up until the end of the array so there's never going to be a subarray from anywhere in here that's going to end up being longer than that so if you're a seasoned leak coder you probably have heard of the sliding window algorithm this Brute Force Solution by the way was an N squ solution and it's a pretty simple one so for a medium problem we should probably expect that we want to do better and the sliding window algorithm the way we're going to kind of do it like I don't know if this is technically the sliding window because like we don't actually care about the window itself we care more about like the end values I prefer to think of it in terms of sliding window Some people prefer to call this the two-pointer approach I mean technically sliding window is a two-pointer algorithm but anyways by the way I'm probably going to gloss over some of the basics so in case like you want to learn more about like these fundamental algorithms sliding window TW pointer prefix sums you might find some of the courses on N code iio helpful now the sliding window algorithm is one that generally runs in linear time it's a two-pointer algorithm this intuition is making me think that perhaps we can apply the sliding window here so it doesn't cost us much to see if like that's valid maybe it'll take 30 seconds just to see if there's a very naive sliding window solution to this so let's try that we have our pointers here and here with the sliding window we generally want to increase the window as much as we possibly can like shift that right pointer as much as we possibly can now if we can't shift the right pointer any further then we shrink the window we take the left pointer and then shift it and it can sometimes be in the same position as the right pointer but the left pointer will never pass the right pointer so I'll just start drawing these as left and right now we're here this is our window but this window is not valid so what should we do because the value zero is less than the value here well the naive sliding window would say well take the left pointer and shift it until that's not the case so then now we're here and this this is fine like for this example it actually will work because now we're going to take our right pointer and shift it by one where here we're going to try this window it's valid we're going to try this window it's valid this is valid and this is valid so it works for this example but it's not always going to be the case and this example we can change it very simply I'm just going to take this five and turn it into a six by drawing over it very badly but now this is a six and now our previous naive sliding window it won't work we just broke it with this simple example cuz now this solution will find this as the longest window but that's not the correct solution the correct solution is actually this and so we made a mistake a bad judgment call when we were back here when you take the left pointer and shift it to the right you're basically saying that we cannot create a window bigger than this that starts at this left pointer the sliding window basically does that that it computes the longest window you can create starting from here here here eventually and when you can't create one from here then we shift the pointer to the right and sometimes we don't shift it at all if we're trying to look for like the maximum subarray which in this case that's exactly what we're doing but specifically when we take this left pointer we're saying that there is not a value to the right of this that is greater than or equal to that but that's clearly not the case here so how would we even determine that how would we know that there actually is a value to the right of six that is greater than or equal to 6 I mean we could scan through every value to the right of it but that's just the Brute Force N squared solution so instead how about we do something called preprocessing the way to eliminate a left candidate is to know what is the max value to the right of that and if the max value to the right of that the max is less than this value then we can safely eliminate this value so that's what I'm going to do I'm going to create a new array down here so I have this new array down here it's called Max right it's going to be the same length as the array up above we're going to fill it in by just for every value Computing the maximum value to the right of it and if we do that obviously going left to right it's going to be n^2 so how about we try doing it right to left and then we just maintain what the max value is that we've seen so far so the max value to the right of this we're actually going to include that value itself so when we do like the two-pointer approach and we want to know like what's the max value to the right of this we're actually going to be using the right pointer so it's fine that we include the value itself because from here we're going to say what's the max value in this whole portion if it's less than six well then this is not a valid subarray so that's why we would shift the left pointer but anyway so this is six we'll put a six here this is one what's the max we've seen so far it's six so we'll put a six over here same thing over here over here we finally see an eight a different number that's bigger than six so we will say eight is the max we've seen so far and it's also going to be the max here and here so with these values I'm going to show you how the solution is going to work for now I think it's fine if you just memorize this and just kind of focus on what the solution is then understand why it works and once you know that then try to focus on how you could come up with it yourself in the future so now starting here with our two pointers our window is this we don't care about this window itself we just want to know does there exist a window whether it's this one or maybe further to the right where this can be the starting point because we're trying to be greedy we're trying to find the maximum window so of course we'd start right at the beginning ideally we can create this window and in this example we can so we're going to see what's the max value at this right pointer it's eight that tells us that in here somewhere in here there is an eight so this is a valid subarray so we can take right minus left that's going to be one and that's going to be the max we've seen so far I'm going to call that the result and now we're going to take the right poter and shift it we're going to do the same thing take the value that's at this index it's eight that tells us that there is an eight somewhere in here so thus there does exist at least a window of this length either it's this window itself or maybe there's a bigger window so it's safe to say that the result is at least going to be two and then we'll take the right pointer here do the same thing even though this value is less than six we know that the max value to the right of here possibly including that value is a six and thus we can say that this window is valid because either it is valid or there is a larger window that's valid so now we'll update the result to three and just keep going we're going to get here same thing we're going to get here same thing so we would get a total of five in this example now let's change the example let's change it back to what it was I'm just going to draw over this just to make it quick let's assume that that's a five so now let's populate this let's put a five here and the max we've seen so far here is five here is five and then I think this will be eight and these will be eight as well well so quickly going through this example we'll get the left pointer here right pointer here we want to know if this window is valid and we don't do that by checking this value we look at the max value here so there's an eight here so that tells us either this is valid or there is another value somewhere over here where we can create a valid window so we'll set the result to one right now we'll shift this pointer over here we're at eight still valid so now we'll increment the result to two now the right pointer will be shifted over here I'm going to clean this up a little bit right pointer is over over here we take a look at the max value in this portion of the array it's five five is less than the left value so now we shift our left pointer we take the left pointer and we shift it over here right pointer is still here and now we kind of do the same check we compare this value with the max right at this pointer which is five this five tells us that there is a five somewhere over here so 0 and five 5 is greater than zero so this is valid and from here we just take this right pointer and then shift it here and then eventually shift it whoops over here where we would get this window so that's the intuition behind this algorithm I know it's not easy to come up with it's not even easy to understand but I hope this does make it at least a little bit easier you can see why this solution would be a linear time algorithm again the key points are with the sliding window when you shift that left pointer you want to eliminate that completely and the only way to do that is to know what's the max value to the right of it and due to this array are going to need extra space as well typically with sliding window you actually don't need extra space so this is a very interesting variation of that so the first thing I'm going to do is that pre-processing I talked about I'm going to create an array called Max right initially I'm going to fill it with all zeros because we know that the smallest value in our input is actually zero so this is perfectly fine and I'm going to multiply it by the length of the input array because in Python that will create an array of the same size filled with all zeros then I want to start start iterating through the input in Reverse I'm going to do that like this for n in reversed nums I believe that just creates an iterator over nums and then we'll go in reverse order so I don't think that actually creates extra space but maybe I'm wrong and what we want to do is the max value at the last position let's call that index I we want to set it to the max of the current value n and whatever the previous Max was which would be Max right of I + one now there's a few things wrong here there's a few issues one we don't have like the ey pointer so that's an easy fix let's set I equal to whoops some all caps I equal length of nums minus one so we're starting at the last index but if we're starting at the last index I +1 is going to be out of bounds in that case there's multiple ways we could deal with this I'm going to deal with it just by having a variable which I'm going to call the previous Max and initially I'll set it to zero and then here we'll replace that with previous Max and then down here we'll update the previous Max every single time to the value that we just populated here and don't forget to update that pointer I so let's decrement it by one each time this is just doing that pre-processing building Max right array now for the two-pointer or sliding window solution we're going to initially set the result to zero we're going to return the result and we're going to try to maximize it so I'm going to have one pointer left it's going to be zero I'm going to have the pointer right which is going to go through the length of the input every time we want to update the result by maximizing it and we're going to assume our current window is valid we're going to add the validation here but just assume that eventually we validated the window and so this is the current length of the window right minus left and we want to try to maximize it so set it to the result of the max of these two okay so now to actually validate the window how do we know if the window is invalid well while the number at index left is greater than the maximum number to the right of it so max right at pointer R while this is the case if they were equal that's actually fine then it's valid but if this is strictly greater than the max value to the right of it well that window is no good we can safely eliminate the left pointer from the solution set so left will be incremented by one so this is the entire solution it doesn't look very complicated but it's definitely harder than it looks I'll run it and you can see that it works I promise you that it is more efficient than leak code indicates right now I believe this is the optimal solution in terms of time and space if you found this helpful or if you're a beginner looking to learn more and improve your problem solving skills definitely check out n cod. whether you just want to use the free resources or you want to buy the courses I genuinely think you'll find it useful