Maximum Product Difference Between Two Pairs
Problem
Pick four distinct indices a,b,c,d in nums and return the largest (nums[a]·nums[b]) − (nums[c]·nums[d]).
nums = [5,6,2,7,4]34def max_product_difference(nums):
a = b = 0 # top 2
c = d = float('inf') # bottom 2
for x in nums:
if x >= a: b, a = a, x
elif x > b: b = x
if x <= c: d, c = c, x
elif x < d: d = x
return a * b - c * dfunction maxProductDifference(nums) {
let a = 0, b = 0, c = Infinity, d = Infinity;
for (const x of nums) {
if (x >= a) { b = a; a = x; }
else if (x > b) b = x;
if (x <= c) { d = c; c = x; }
else if (x < d) d = x;
}
return a * b - c * d;
}class Solution {
public int maxProductDifference(int[] nums) {
int a = 0, b = 0, c = Integer.MAX_VALUE, d = Integer.MAX_VALUE;
for (int x : nums) {
if (x >= a) { b = a; a = x; } else if (x > b) b = x;
if (x <= c) { d = c; c = x; } else if (x < d) d = x;
}
return a * b - c * d;
}
}int maxProductDifference(vector<int>& nums) {
int a = 0, b = 0, c = INT_MAX, d = INT_MAX;
for (int x : nums) {
if (x >= a) { b = a; a = x; } else if (x > b) b = x;
if (x <= c) { d = c; c = x; } else if (x < d) d = x;
}
return a * b - c * d;
}Explanation
To make (first pair) - (second pair) as large as possible, we want the first product to be as big as we can and the second to be as small as we can. With non-negative numbers that means multiply the two largest values and subtract the two smallest.
You could sort and read off the ends, but this solution does it in a single pass. It keeps four running values: a and b for the top two, and c and d for the bottom two.
For every number x, if it beats the current biggest a, the old a slides down to b and x becomes the new a. The same bumping logic, mirrored, tracks the two smallest into c and d.
Example: nums = [5,6,2,7,4]. The two largest end up as a=7, b=6, and the two smallest as c=2, d=4.
The answer is a*b - c*d = 42 - 8 = 34. One walk through the list gives everything we need.