Minimum Difference Between Largest and Smallest Value in Three Moves - Leetcode 1509 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimum difference between largest and smallest values in three moves idea is we're given an input array something like this and we're allowed to actually remove up to three elements from the array so we could remove one two three or we could just do two or just do one or just not remove anything but the idea is that after removing some elements there should be at least one or two elements left left over and those are going to be the minimum and maximum respectively they could be the same element but basically we're going to take the absolute difference between these two values in this case the absolute difference is three and what we're trying to do is minimize this number and then return it so in this input actually if we remove three elements it doesn't really matter which ones we remove because we're only going to have one element left over and so obviously the minimum and the maximum is going to be the same in that case and it's going to be zero so immediately we kind of recognize that if the length of the input is four the result is going to be zero if we only have three elements in the input well we'll just remove two of them and have one left over and then the output is going to be zero same if the input length is two or if it's one so it's not until we get a fifth element that the solution becomes more interesting like the problem becomes more interesting because now I mean I guess I could remove 1 2 and three but at this point the output is going to be 5 - 4 which is 1 and obviously for larger inputs it's going to be even more interesting consider an input that looks something like this as you can see I've actually sorted it this time and that's on purpose because think about it when we're given the input right the minimum is all the way at the left the maximum is all the way at the right if we delete from here or here or here or even here doesn't matter because the result did not change we did not change the Min or the max the result is only going to change when we change the minimum or the maximum but even that is not enough because think about this if I remove all three of the minimums right we change the minimum from one to two then I get rid of two and then I get rid of four so probably should have used a different color for this but you get the idea we were remove all three from here now the result is going to be 12 - 7 that's 5 but if we did the opposite if we instead removed all three from the right side now we're left with one and four and that's going to be 4 - 1 that's going to be three that's smaller than the five that we had earlier but even then what we're kind of realizing is that we remove three elements total at most we can either remove from this end or this end and those are are the only ends that matter removing from anywhere else literally does not matter but the question is now how much do we remove from each side like these are the possibilities we remove Zero from here and we remove three elements from this side that would look like this or we remove one element from this side and remove two elements from this side that's again three total so then we have two over here or we could remove two here and then one here that would be two and then one or we could remove three from this side and then nothing on this side so a zero here so these are the only possibility there's literally only four possibilities so if we can take this input and get it in sorted order the problem becomes really easy because this is the solution now if I remove nothing from here and three from here what we're looking at is this and this value because if three values are removed from here we're only looking at these two otherwise we're looking at the first index here and we removed two from here so we're going to be looking at this Index right we take the difference between these two the other case we are one over we're over here two removed from here one removed from this side that would be something like this and the last case is going to be three removed from the left over here zero removed from the right over here and then take the difference so if you were paying attention this is actually a two-pointer technique it's kind of the sliding window pretty much I don't know if it's technically the sliding window or if it's technically the two-pointer technique but it doesn't really matter because it's pretty easy to code up either way we have a pointer over here we have a pointer over like take the last index and then shift three to the left because we need to have basically three values outside of the window so we look at this window right the fact that this is of size three by the way is a coincidence it might not be size three like consider if the input was like of size 10 then we'd remove three elements and then the window would be of size seven so just keep that in mind but the fact that there are three values outside of the window that's intentional so this would be our first window our second window would be over here just shifting by one the third window would be over here and the fourth window would be over here there's always going to be exactly four Windows that's an important observation to make because it pretty much implies that there's always going to be three values outside of the window those three values are here right now so this is the first solution I'm going to be showing you obviously it seems pretty simple like it's just checking four different windows but remember we do have to sort the input before that that so time complexity is going to be n log n the second solution I'm going to show you is going to be a bit more efficient it's going to be linear time so stay tuned for that one as well what I'm going to do is first of all sort the input that's very very important for this first solution and then I'm going to declare the result and I'm going to return it now since we're trying to minimize this number we should set it to a really large value I'm just going to set it to infinity and then we're going to try to minimize it we want to Loop four times and so so I'm going to use a variable called L and it looks like a one but it's an l and we're going to go four times from the beginning of the array so left is going to be the left pointer of our window and I'm going to have another variable R which is the right pointer of our window it's not super crazy to calculate the last index would be this length of nums minus one now we want to shift three more to the left so we're going to do minus four but at the same time we want to add the left index because the first time the left index is going to be zero so we're going to get the fourth to last index next time left is going to be one so we're going to kind of shift the right pointer by one each time so this is our way of doing that if we just had this portion we'd have the exact same right index every time that's not what we want we want to shift this the same way that we shift the left pointer that's why we have plus L next we want to minimize the result pretty easy to do at this point cuz we've had some pretty readable variable names for once so we're going to minimize result and the right value nums of right minus nums of L you might wonder why am I not taking the absolute value of this well the array is sorted the right value should be greater than or equal to the left value anyway so this solution should work but there actually is one little bug and that has to do with the fact that how are we handling arrays that are less than four or less than three we can't remove three values from an array that's less than three so what would we do well that case is really easy to handle anyway so we're just going to handle it with an if statement so for example if length of nums is less than or equal to four return zero if we don't have this look what's going to happen down here like this Loop will technically execute but left index might be out of bounds for this like we'll try to access index 3 but it might be out of bounds so we don't want to run into that and this might also cause out of bounds issues so let's just get rid of that and have this and you can see that this solution works it's relatively efficient but we can actually do better in terms of time complexity let me show you how so the fact that we realize that there's only four possibilities when it comes to removing elements that's very important to get to the more optimal solution like there's literally only four cases that we have to look at so one possibility would be to okay okay get the three largest values and then from the remaining portion get the minimum and get the maximum and then take the difference right do that once and do that three more times for the other cases right where we remove these values or remove these etc etc right so that's possible but it would be pretty hard to code up let me kind of show you something clever I'll add a couple more values here let's say 13 and 15 they don't really matter too much though so I'm just going to go through like a 30 or 60c visual explanation and then the solution will probably make a lot of sense to you so just to replay what we did earlier remember that like this first row was where we take this value cuz we remove nothing from this side and this one we remove three values from here so we get this value and then we take the difference between them the other case down here I'm trying to like color code them but here was when we take this value cuz we removed one over here and here where we remove two and then take this value I'm just going to go through this a couple more times so here we have this one and then here we have this one and then in the last case we have this one and then we have this one now each color kind of just indicates one case CU there's four different cases obviously and so in each of these cases we're just going to take the absolute difference between these four pairs of values right so nothing crazy is going on and so in this case the input array was of length eight and I did that on purpose so that we'd have at least eight elements to create these four pairs but it's possible that we could have an input that's of length 10 or 20 or 100 and in that case all the elements that don't have like a color associated with them would go in the middle like they'd be in here you can imagine that there's a bunch of numbers in there maybe a bunch of sevens or something like that but that's the idea here so when you look at what we're really doing when you boil it down to the most fundamental level what we're doing is every single operation that we're going to be doing will not touch any of those numbers in the middle I'm just going to leave like this big white spot here in the middle just to kind of indicate that though it is pretty messy I admit but notice literally none of these lines is touching any of those elements so what I'm getting at is we can actually solve this problem by getting the minimum four elements and by getting the maximum four elements and then just do this with those four minimum and maximum elements get the smallest element from the minimum and the smallest element from the maximum and then just take the difference between those two get the second smallest from the minimums get the second smallest from the maximums and just take the difference between those two do that four times for each of those four and then get the minimum absolute difference that's it that's the solution now the old only question is how do you get the minimum four elements and how do you get the maximum four elements without sorting the input that's kind of the hard part but the solution is actually pretty simple because if you recall there is a data structure called a heap we can call a function called heapify which turns all these elements into a heap in linear time we can do that and then we pop from the Heap four times exactly four times to either get the minimum four or the maximum four and so that would be 4 * log n in terms of time complexity so overall this is a linear time operation to get the minimum four and maximum four now if instead we wanted the minimum n or the max n elements then it's not going to be efficient but the fact that it's a small number only four makes it efficient therefore we can get these elements in linear time and that's why we can solve this in linear time so let's code it up now so we're going to have that same condition here but the next thing I want to show you is how to get the minimum four and maximum four and I'm actually not going to use a loop I'm not going to pop from the Heap because there's actually a built in way in Python to do what we're looking to do and I actually learned that today so we can do Heap q.n smallest and then we can pass in the variable n which I'm going to do four and we can pass in nums this will take nums turn it into a heap and then give us the four smallest elements I'm pretty sure it's just doing what I talked about earlier like under underneath the hood it's just going to create a heap and then pop a few elements and this will be returned in the form of an array but we do want that array itself to be sorted but it's just an array of length four so sorting it isn't going to be inefficient so I'm just going to call sorted on this bad boy over here and now I'm going to copy this and I'm going to do n largest so pretty much the same thing except this time we're going to get the four largest elements in sorted order and so once we have have that we're pretty close to solving the problem we'll have kind of the boiler plate down here but now we're going to iterate again exactly four times I'm going to say for I in range four we're going to take the smallest element from min4 so let's say min4 at index I we're also going to take the smallest element in Max 4 Max 4 index I we're going to take the difference between them and we're trying to minimize this so result is equal to minimum of itself and this portion over here and that is the solution code let's see if it works as you can see on the left it does and the leak code Gods blessed us this time and we got a really really good runtime I think I solved this problem a few years ago let's see my solution 3 years ago almost exactly and it looks like I only came up with the Sorting solution but I did have some good variable names so that's pretty nice if you found this helpful check out n code. for more thanks for watching and I'll see you soon