Maximum Product Difference Between Two Pairs - Leetcode Solution

Problem Statement:

The Maximum Product Difference Between Two Pairs problem on LeetCode states that you are given an integer array nums of length n. You need to find the maximum possible product difference between any two pairs of the array.

In simpler terms, you have to find the product of the largest and second-largest element in the array and then find the product of the smallest and second-smallest element in the array. Finally, you have to subtract the two products and return the result.

Solution:

One simple solution to this problem is to sort the array in ascending order and then find the product difference between the two largest and two smallest elements respectively.

The time complexity of this approach is O(n log n) due to the sorting operation. Here's the pseudocode for the same:

• Sort the array nums in ascending order
• Return (nums[n-1] * nums[n-2]) - (nums[0] * nums[1])

Another approach to solve this problem is by using two variables - max1, max2, min1, and min2 to store the largest and second-largest and smallest and second-smallest elements of the array respectively.

We iterate through the array and update the variables accordingly. Finally, we return the product difference between the largest and second-largest element and the smallest and second-smallest element.

Here's the pseudocode for the same:

• Let max1 = max2 = -inf and min1 = min2 = +inf
• Traverse the array nums and update the variables as follows:
  • If nums[i] > max1, set max2 = max1 and max1 = nums[i]
  • Else if nums[i] > max2, set max2 = nums[i]
  • If nums[i] < min1, set min2 = min1 and min1 = nums[i]
  • Else if nums[i] < min2, set min2 = nums[i]
• Return (max1 * max2) - (min1 * min2)

The time complexity of this approach is O(n) since we traverse the array only once to update the variables.

Here's the Python code for the same:

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        max1, max2, min1, min2 = -float('inf'), -float('inf'), float('inf'), float('inf')
        for num in nums:
            if num > max1:
                max2 = max1
                max1 = num
            elif num > max2:
                max2 = num
                
            if num < min1:
                min2 = min1
                min1 = num
            elif num < min2:
                min2 = num
        
        return (max1 * max2) - (min1 * min2)

Time Complexity:

The time complexity of the above solution is O(n) as we have linearly traversed through the array only once.

1