Maximum Product Difference Between Two - Leetcode 1913 - Python

Key Takeaways

hey everyone welcome back and let's write some more neat code today so today let's solve the problem maximum product difference between two pairs a pair is defined as two numbers and the product difference between two different pairs is defined as the product of the first pair a * B subtracted by the product of the second pair which is C * D so this is just the definition now in terms of like the example given an input array like this which is guaranteed to only contain positive integers and is going to have at least four elements in it we want to choose four distinct elements from the array such that we maximize this formula initially you might think let's just brute force it but actually this is math and we can try to notice some patterns which there are here what do you think is going to lead us to maximize this formula we probably want to maximize this left side and we probably want to minimize this right side because we're adding this amount and we're subtracting this amount okay how do we do that well when you're just taking the product of two numbers you probably want to maximize each individual number cuz the product of those then is also going to be maximized when you want to minimize the product of two numbers you probably just want to minimize the those individual numbers once you understand all of that you realize what this problem is really asking for is find the two maximum elements from the array they have to be distinct and also find the two minimum elements from the array and they also have to be distinct once you've done that you can pretty much just apply this formula and then return the result because that's what we're trying to do here return the product difference between these two pairs so so how exactly do we do that your mind might jump to just iterating over the two arrays and try to find the two Max and two minimum elements but there's actually an easier way to do this we can rearrange the array if we want the maximum elements and the minimum elements it probably makes sense to take the input array and sort it because when you do that we have pretty much solve the problem because think of it if you had four numbers and you sort them they look like this 1 2 3 four what do you do these are the two maximum elements these are the two minimum elements we can apply the formula we just solved the problem the downside of this solution is the time complexity is going to come from the Sorting which is going to be n log n no extra memory needed though depending on how the Sorting is implemented I assume you're not going to implement that from scratch you're probably just going to use like a library method now can we do better yes we can because as I talked about the solution where we just iterate over the the array and try to find the two Max and two minimum elements if we can implement it correctly is going to be Big O of N and also no extra space needed so that is the target solution before I explain this solution I do want to mention you might forget that there is another way to sort numbers with a data structure called a heap and you might forget that because the Sorting solution is just so simple but actually we can solve this problem with a heap and I think we'll actually need two heaps that can actually also be done in Big O of end time now the downside is since we are using a heap we're going to need extra space I'll briefly explain the solution for that what we would do is first create a Max Heap from all these elements we would do that with a method called heapify which actually runs in Big O of end time and once we've done that we created the max Heap we can easily get the two maximum elements just by popping from that Max Heap twice each pop is going to be log n so the overall time complexity of getting the two Max elements is going to be n plus log n and of course n is bigger than login so we can just forget this term and we would do pretty much the exact same thing to find the minimum elements only difference is we would also create a Min Heap to do that then we pretty much have solved the problem once we found these elements we can apply this formula okay so that's the Heap solution I won't code it up because there is a more efficient solution that doesn't take extra memory it is finding these two elements now the question is how do we do it well for the most part I think it's just going to be easier if I explain it within the code but I want to give you a bit of the intuition so let's say these are our numbers we're going to keep track of the max element I'm going to call that Max one and we're going to keep track of the second largest element I'm going to call that Max 2 and we're going to do the same thing with the minimum elements the most minimum is going to be Min one and I'm going to call the second smallest element Min 2 we're going to keep track of these in these variables since we're trying to maximize these elements let's initialize them to small numbers they will be initialized to zero both of them since we're trying to minimize these let's initialize them to large numbers they will be initialized to Infinity initially what we're going to do here and I guess I should add the second one for each of these two at a high level we're going to iterate over every element in the input array by the time we've gone through this entire array we should have picked out the two large lest numbers in this case six and seven and assign them to these two variables seven will be first because Max one is the largest Six will be second cuz it's uh the second largest and we're going to do the same thing with the minimum elements so two and four are the smallest two is going to go here and four is going to go here the smallest is going to be two and second smallest is four then we found our solution and you notice something as long as we put the two largest numbers here and the two smallest numbers here we actually guarantee that there won't be overlaps between these because how could it be possible that we did not choose four distinct integers if we do that the only way that would be theoretically possible is if the two largest numbers also happen to be the same as the two smallest numbers how would that be possible if we have four integers in the input it would only be possible if all four of the integers happen to be the exact same they could be all fours or it could be all like threes for example and that would be fine because that would mean two of these threes belong to this group and the other two threes belong here they technically are distinct numbers the numbers aren't distinct but the index of each number is technically distinct we're not reusing any of these individuals so that's why this solution will work now in terms of implementing it I will mostly save that for the code but at a high level I'll quickly go over it for each number the way I'm going to code it I'm going to ask myself is this number larger than the second smallest number and in this case it is next I'm going to ask myself is it larger than the largest number yes it's larger than the largest so what I would do is put the five in this spot and I would take whatever number happened to be here and then move that to the second smallest and in verely I would kind of do the same thing with the minimums as well like for example with five I'd say is this smaller than Min 2 yes it is so before we now replace this with five we're going to ask ourselves is it also smaller than the smallest number and if it is then we actually put that five over here and we would take whatever we have here and move it over there that's the idea now I'm going to code it up so here I have just initialized those two variables as we kind of talked about in the drawing explanation I don't think you want to see me type all that out now we're going to implement the algorithm go through every number in the input array like I said we're going to first ask is this number larger than the second largest number that we have okay it is so now the question we need to know is should we put n in this spot or should we put it in this spot so let's find out now is n also larger than Max one if it is then we say Max one is going to be equal to n and we would also say Max 2 is going to be equal to the original value of Max one in Python you can do this double assignment both of these will pretty much be executed in parallel at least that's how you can think about it now if this wasn't the case then we can't do that then we can only replace Max 2 with n so that's how we do this part now the next part is with replacing the minimums you might be thinking should we put an else if here should we say n is smaller than min2 and you'd actually be wrong we don't need an else and that will make the solution incorrect you don't put the else here because as we're going through an input array for example it might be 1 2 3 four initially when we get to the first one this if statement is going to execute because we initialize these to zeros so we would end up setting like Max one equal to 1 if we had an else if here then this part would not execute but that would lead to the wrong solution because we know that one actually is the minimum it's not the maximum it might temporarily be set to Max one but it's not the largest in this array what we're saying here by having both of these just be if statements is that sometimes at some point they might overlap like Min one might have the same value as Max one that's okay because we know for sure by the end of this array they will be set to distinct integers at least integers at distinct indices so that's why we don't need the else over here to finish this up if n is smaller than min2 now we need to ask ourselves is it also smaller than min1 if it is we do pretty much what we did up above Min one is going to be set to N and min2 is going to be set to the original value of min1 otherwise we just replace Min 2 and set it equal to n so that's pretty much the entire code only thing left for us to do is return the result which they pretty much gave us the formula to do that Max one multiplied by Max 2 subtracted by min1 * min2 so now let's run this to make sure that it works and as you can see on the left yes it does and it's pretty efficient if you found this helpful please like And subscribe if you're preparing for coding interviews check out NE code. thanks for watching and I'll see you soon