Minimize the Maximum Difference of Pairs - Leetcode 2616 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem minimize the maximum difference of pairs we're given a zero indexed array which is pretty meaningless in this problem we're just given an array of numbers and we're given an integer P we want to find P pairs of indices of numbers such that the maximum difference amongst the pairs and when they say pairs they actually mean the numbers not the indices I think it's kind of worded a bit confusingly but among those pairs of elements and let me actually draw it out so these are our elements and we want to break them up into P pairs there's a bit of a restriction we're not allowed to repeat the same index that basically means that we're not allowed to repeat the same element so suppose that we break them up into these types of pairs just for Simplicity they're adjacent to each other now among all of these pairs we want to find the difference for each of them and when we say difference we mean the absolute difference so for this it would be 10 minus 1 that's going to give us 9 this is going to be 2 minus 7 which would give us negative 5 but like I said we want the absolute difference so we take negative we take positive 5 here and then here we say 1 minus 3 and that's going to be an absolute value of 2. so these are all of the differences now we kind of understand what they're asking us among all of them we choose the maximum difference so it's going to be 9. this is the value that we're trying to minimize so we constructed our pairs like this but there are other ways to construct the pairs and I'll show you the way that they do so in the solution because the solution is actually one we are going to use this as the return value this is the return value and we want to minimize it and then return it so 9 is not not the solution the solution is one how do we break these up into that way such that we get that one difference and there's actually one last part to the problem we don't necessarily need each element we can only use each value at most a single time so that's the Restriction now how many pairs do we need well if you're paying attention you realize that we can't possibly have more than n divided by two pairs let's say n is the number of elements that were given in the entire array we can't possibly have more than this many pairs the number of pairs is actually specified in a separate variable called P so this is how many pairs we need and like I said this value is never going to be greater than n divided by 2. if you scroll at the bottom of the problem description it will state the exact same thing but like I said just intuitively based on the description this is implied and in a real interview it would be worth mentioning that to your interviewer because then they'll probably realize you actually understand what they're asking the good thing here is we only need to find two pairs of elements now if we want to minimize the absolute difference don't you think it would be helpful to sort the array because let me just show it to you if I want to for any particular element whether it's this guy this guy this guy or this guy why would I ever choose a non-nabor element if I want to minimize the difference for three if I want to minimize the difference I'm either going to take the difference between 2 or 7. I would never do that with any of these or these because that's never going to lead to a smaller difference I think this is pretty intuitive isn't it the difference as we go farther to the left is only going to get bigger from three and if we go farther to the right it's only going to get bigger as well so this is the hint that that there's an element of this problem that is greedy in my opinion the easier solution to arrive at is the greedy dynamic programming one where you start at the beginning of the array after you have sorted it of course so we definitely want to sort the array but once you've done that you're going to start at the beginning and you're going to kind of build a subsequence of P pairs so for every value you kind of have a choice we can either choose the one or we can skip the one and then here we can choose the one the second one or we can skip it and then here we can choose the two or we can skip it etc etc and then here we can make those decisions basically and what you're going to realize is that this solution will lead to a Time complexity of Big O of n times P it's not a bad solution at all but it just happens to not get accepted on leak code at least in my case it led to a memory issue I think I got memory limit exceeded because with caching we're going to need all of this this in memory as well and by the way since our p is sort of bounded by n this can kind of be comparable to an N squared solution so these are more or less equivalent because that's like the upper bound of P or at the very least this is bounded by N squared but the interesting thing is that there actually is a better solution now in a real interview I would honestly think that this would be good enough like the dynamic programming solution isn't easy either but there is a better solution that is also greedy and involves binary search believe it or not it's not super intuitive at least in my opinion because the DP solution is just so much more obvious but let's get into it you wouldn't know to arrive at the binary search solution unless you take a look at the constraints which in a real interview they usually don't like mention this to you another reason why this solution is not intuitive but the noteworthy constraint here is the value each value in the array is going to be between 0 to 10 to the power of 9. now that constraint is much bigger than the length of the array which again we found the DP solution was N squared where n is going to be the length of the array so this is another reason why the binary search solution is not intuitive but I'm going to show you why it actually is more optimal we are going to use this this range I don't know what to call it let's call it m where this is like 10 to the power of 9 let's say we're going to use this as a variable this is going to be our binary search range before I get into that let me explain the intuition suppose our return value which again is the minimum difference among all of the pairs suppose we guess our guess is that that value happens to be zero how can we confirm whether our guess is true or not well we would have to look at the array and ask ourselves can we find find P pairs such that the difference the maximum difference is less than or equal to zero how do we do that well it's pretty easy after you've sorted the array isn't it that's the greedy part here we start at the beginning and we just do a very basic linear scan I look at the first element and like I said I'm not going to compare it to the last element or the other one I'm going to compare it to its neighbor over here and I'm going to ask is the difference between these less than or equal to zero it is in this case so we found one pair we're being greedy here we can't reuse the same element so we're going to take our I pointer not shift it by one but shift it by two so over here our eye pointer is at two now we're gonna look at its neighbor 2 minus three the absolute difference is one that's definitely not less than or equal to zero so we can't include two in any of the pairs as we now increment our eye pointer by one because we kind of eliminated this guy so now we're going to compare three with its neighbor seven and the difference is going to be four that's definitely not less than or equal to zero and then lastly we're going to see that seven compared with ten the difference is three definitely not less than or equal to zero so we were trying to find two pairs such that the difference the maximum difference for those pairs was going to be less than or equal to zero we were not able to do that so our guess was incorrect the answer is not equal to zero that's not the case here so a naive way to do this would be basically be greedy we try zero next try one next try two next try three all the way up until 10 to the power of nine and the time complexity of that would not be great it would be n times M where again m is bigger then and our previous DP solution was N squared but there is an optimization we can make and that is going to be of course binary search like I mentioned because we have a very clear search range for the return value the return value is going to be somewhere between 0 all the way up until 10 to the power of 9. we want to find the smallest value such that we're able to make p pairs with the maximum difference being whatever value we have selected so instead of going from 0 1 2 3 we're going to run binary search on this range so we're first going to take the middle value which I think would be something like well I'm not even going to guess what it is now what's the time complexity of this approach because 10 to the power of 9 that's quite a big number but if we run binary search we know we're going to take the log of that term so we're taking log of M is that really going to be more efficient like let's take a look is n log M and the way the N term comes from is because we are going to have to linearly scan through this and compare that to our dynamic programming solution which was N squared is this really more efficient m is such a bigger number than the upper bound of n well think about it this way if you had something like a value like a million and you took the square root of that you would get a thousand that's pretty good like square root will take a big number and make it small very quickly now you might not know this I'm pretty decent at math so I kind of remember this but log is even more than square root log is square root on steroids it will take a big number and turn it small very very quickly another way to put it would be that log which is blue over here and square root which is red log grows so much more slowly than square root and if you need a quick refresher you can check out my Big O notation lesson it's available on neat code IO I'm just mentioning it because it's relevant here but my point is if you took a big number like 10 to the power of 9 and took the square root it would be much smaller than 10 to the power of 5. so if you take the log of this number which is basically what we're doing here it's going to be way smaller than N squared log m is going to be way smaller than n in this case with these numbers that we're working with now theoretically this number could be so big that that's not the case but generally it is going to be the case now enough math let's get into the solution so the first thing I'm going to do is sort our numbers array because that's the like whole Crux of the problem and then we're going to set up our binary search our range is going to be from 0 all the way up until 10 to the power of 9 and you can do that in Python like this and I'm also going to initialize the result we're trying to minimize it so I'm going to set it to the max possible value which is this and then we're going to start running the binary search and it's pretty standard binary search stuff we're going to take the middle point of our range as we usually do I'm going to do it like this to prevent any overflow if you don't understand this line it's not actually necessary well let me fix it this is pretty much equivalent to left plus right and then dividing that by two so you can write it like this if you want to this is just a way of writing the same thing without having it ever overflow if you don't understand it feel free to comment below and I'll try to explain it but next we want to know if this is a valid middle value like is the maximum difference of the pairs that we can construct less than or equal to this threshold so that's what we're going to pass into our helper function is valid that I'm going to declare up above over here I'm not going to implement it quite yet but I'm going to show you how we're going to use it so if there the range is valid then we possibly found a result so we're going to set the middle value to our current result which is ultimately what we're going to return out here we're trying to minimize the maximum difference now if the range is not valid then we're going to do something else but if we do find a valid maximum difference then we want to try to find an even smaller one next so what we do is set right equal to left or mid minus one we're going to try to find an even smaller one if it's possible otherwise we found that we were not able to find P pairs where the maximum difference was less than or equal to this so now we want to loosen the restriction and say that left is actually going to be M plus one let's try maybe a bigger difference and see if we can find P pairs using that so that's the reasoning behind this now for our help upper function like I mentioned it's basically going to be a linear scan and so this is sort of the greedy part this is why we sorted the array we didn't sort the array for the binary search portion so make sure that that's clear with you we're not running binary search on the array that's confusing and it's definitely unintuitive so make sure you recognize that so here we're going to use an eye pointer and we're going to keep track of the count of pairs where the difference is below this threshold so both of these are going to be initialized to zero and then we're going to start scanning we're going to make sure our I pointer is less than the length of the array but actually we're going to say less than the length of the array minus one because the way we're going to compare the values we're always going to compare nums of I with nums of I plus 1 like this so we can take the difference like that numbers of I minus numbers of I plus 1 and of course we want the absolute difference of this part a if this is less than or equal to the threshold that was supplied to us then we can say we found a new valid pair so let's increment the count of our valid Pairs and then let's increment our eye pointer by two because we used both of these values we can't use them again so we increment this by two whoops I forgot about that or I wasn't reading my screen I guess but next if that was not the case perhaps the difference was actually greater than the threshold in that case we definitely don't increment the count and we take our I pointer and only increment it by one because we're going to skip this but it's possible that this guy compared to its right neighbor might be valid now lastly we have to return true or false from this function so what I'm going to do here is if we ever get to the point where the number of pairs is equal to P we can immediately return true we don't need to do anything else but if that's not the case over here we will return false so this is the entire code I'm just going to quickly get rid of this comment so all the code fits on the screen but this is the entire code now let's run it to make sure that it works whoops and there was one Edge case that we actually missed maybe you're able to figure it out but it's when p is equal to zero I think that's kind of stupid if we don't need to find any pairs at all then I guess the return value is zero because the maximum difference is going to be zero so I'm just going to handle that with an if statement at the beginning of our code so basically if p is equal to zero return zero so now let's run it again and as you can see it works and it's pretty efficient if you found this helpful please like And subscribe if you're praying for coding interviews check out neatcode.io it has a ton of free resources to help you prepare thanks for watching and I'll see you soon