Problem Description

You are given an array of integers nums of length at least 4. Your task is to find the maximum product difference between two pairs of numbers in the array.

Specifically, you must select two pairs of numbers: (a, b) and (c, d), where all four elements are distinct (i.e., you cannot reuse the same element in both pairs). The product difference is calculated as:

(a * b) - (c * d)

Your goal is to maximize this difference. The problem guarantees that there is always at least one valid solution, and you must not reuse any array element in both pairs.

Thought Process

At first glance, you might think about checking all possible pairs of numbers and calculating their products, then finding the two pairs with the largest product difference. However, this would require checking every combination, which is inefficient for large arrays.

Instead, let's reason about what would make (a * b) - (c * d) as large as possible:

• To maximize the difference, a * b should be as large as possible.
• Simultaneously, c * d should be as small as possible.

So, the problem reduces to simply finding the two largest and two smallest numbers in the array, and computing the difference of their products.

Solution Approach

Let's break down the steps to solve the problem efficiently:

1. Sort the Array:
   • Sorting the array puts the smallest numbers at the start and the largest at the end.
   • This makes it easy to pick out the two smallest and two largest numbers.
2. Select Pairs:
   • Pick the first two elements as c and d (smallest numbers).
   • Pick the last two elements as a and b (largest numbers).
3. Calculate Product Difference:
   • Compute (a * b) - (c * d).

This approach is both simple and efficient. Sorting takes O(n \log n) time, and picking out the numbers and calculating the result is constant time.

Alternative: If you want to avoid sorting, you can scan through the array once to find the two largest and two smallest numbers, which is also O(n) time.

Example Walkthrough

Let's walk through an example with nums = [5, 6, 2, 7, 4]:

1. Sort the array: [2, 4, 5, 6, 7]
2. Pick pairs:
   • Smallest two: 2 and 4
   • Largest two: 6 and 7
3. Calculate products:
   • 6 * 7 = 42
   • 2 * 4 = 8
4. Product difference: 42 - 8 = 34

So, the maximum product difference is 34.

Time and Space Complexity

Brute-Force Approach:

• You would check every possible combination of four distinct numbers, which leads to O(n^4) time complexity (very slow for large arrays).
• Space complexity is O(1) (not counting input).

• Sorting the array takes O(n \log n) time.
• Picking the numbers and calculating the result is O(1).
• Space complexity is O(1) if sorting in-place, otherwise O(n) if the language creates a new array when sorting.

• Scan the array once to find the two largest and two smallest numbers: O(n) time.
• Space complexity is O(1).

Summary

The problem asks for the maximum product difference between two pairs of distinct numbers in an array. The key insight is that this is achieved by multiplying the two largest numbers and subtracting the product of the two smallest numbers. By sorting the array or scanning for these values, we can solve the problem efficiently in linear or log-linear time. The solution is elegant because it reduces a seemingly complex problem to a simple observation about maximizing and minimizing products.

Code Implementation

class Solution:
    def maxProductDifference(self, nums):
        nums.sort()
        return nums[-1] * nums[-2] - nums[0] * nums[1]
      

class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return nums[n-1] * nums[n-2] - nums[0] * nums[1];
    }
};
      

class Solution {
    public int maxProductDifference(int[] nums) {
        Arrays.sort(nums);
        int n = nums.length;
        return nums[n-1] * nums[n-2] - nums[0] * nums[1];
    }
}
      

var maxProductDifference = function(nums) {
    nums.sort((a, b) => a - b);
    return nums[nums.length - 1] * nums[nums.length - 2] - nums[0] * nums[1];
};