Maximum Product Difference Between Two Pairs

Problem Statement

The concept of "product difference" is defined for two pairs of numbers (a, b) and (c, d) as (a * b) - (c * d). Given an integer array nums, the goal is to find four distinct indices such that the product difference between the two pairs formed by these indices is maximized. In simpler terms, you need to select indices w, x, y, and z from the array such that the difference between the product of nums[w] and nums[x], and that of nums[y] and nums[z] is the largest possible. The function should return this maximum product difference.

Examples

Example 1

Input:

nums = [5,6,2,7,4]

Output:

34

Explanation:

We can choose indices 1 and 3 for the first pair (6, 7) and indices 2 and 4 for the second pair (2, 4).
The product difference is (6 * 7) - (2 * 4) = 34.

Example 2

Input:

nums = [4,2,5,9,7,4,8]

Output:

64

Explanation:

We can choose indices 3 and 6 for the first pair (9, 8) and indices 1 and 5 for the second pair (2, 4).
The product difference is (9 * 8) - (2 * 4) = 64.

Constraints

• 4 <= nums.length <= 104
• 1 <= nums[i] <= 104

Approach and Intuition

1. To maximize the product difference (a * b) - (c * d), aim for (a * b) to be as large as possible and (c * d) to be as small as possible. This observation is foundational for our strategy.

2. Extract the two largest and the two smallest elements from nums. This is because the product of the two largest numbers will yield the highest possible product from the array, and similarly, the product of the two smallest numbers will tend to be the smallest (or most negative if negatives were possible, but constraints forbid negatives).

3. How do we efficiently find these numbers?

   • Sort the array: Once nums is sorted, the two largest elements will be the last two elements of the sorted array, and the two smallest will be the first two elements.
   • Calculate based on the sorted positions: If we denote sorted nums as nums_sorted, then:
     • The two largest numbers can be accessed as nums_sorted[-1] and nums_sorted[-2].
     • The two smallest numbers can be accessed as nums_sorted[0] and nums_sorted[1].
   • Compute the product difference: Using the four identified numbers, compute (nums_sorted[-1] * nums_sorted[-2]) - (nums_sorted[0] * nums_sorted[1]).

4. Given the constraints (4 <= nums.length <= 104 and 1 <= nums[i] <= 104), this method is efficient. Sorting the array will take O(n log n), which is reasonable for the input size limit. This approach ensures that we automatically respect the condition of choosing four distinct indices since the largest and smallest pairs are distinct by definition in sorted order.

By focusing on maximizing the primary product and minimizing the secondary product via sorting and strategic selection, we can robustly determine the maximum product difference achievable.

Solutions

class Solution {
public:
    int maximumProductDifference(vector<int>& nums) {
        int largest = 0;
        int secondLargest = 0;
        int tiniest = INT_MAX;
        int secondTiniest = INT_MAX;
            
        for (int value : nums) {
            if (value > largest) {
                secondLargest = largest;
                largest = value;
            } else {
                secondLargest = max(secondLargest, value);
            }
                
            if (value < tiniest) {
                secondTiniest = tiniest;
                tiniest = value;
            } else {
                secondTiniest = min(secondTiniest, value);
            }
        }
            
        return largest * secondLargest - tiniest * secondTiniest;
    }
};