Problem
The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).
- For example, the product difference between
(5, 6)and(2, 7)is(5 * 6) - (2 * 7) = 16.
Given an integer array nums, choose four distinct indices w, x, y, and z such that the product difference between pairs (nums[w], nums[x]) and (nums[y], nums[z]) is maximized.
Return the maximum such product difference.
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 <= 1041 <= nums[i] <= 104
Solution
The easiest way is use sort and get the head and tail, but the time complexity is O(n*log(n)), be honestly, it is not good.
Another intuited method is claim four variables, largest, secondLargest, smallest, secondSmallest… and update them when traversing the array.
Be careful, if the largest number is replaced, the original largest number will be assign to secondLargest. The small case is the same.
And now, we can think our time complexity is O(n) and space complexity is O(1).
C++ Sample Code
class Solution {
public:
int maxProductDifference(vector<int>& nums) {
// Init
int max1 = INT_MIN;
int max2 = INT_MIN;
int min1 = INT_MAX;
int min2 = INT_MAX;
// Traversal
for (int& num: nums) {
if (num >= max1) {
max2 = max1;
max1 = num;
}
else if (num >= max2) {
max2 = num;
}
if (num <= min1) {
min2 = min1;
min1 = num;
}
else if (num <= min2) {
min2 = num;
}
}
return max1 * max2 - min1 * min2;
}
};Python Sample Code
class Solution:
def maxProductDifference(self, nums: List[int]) -> int:
# Init
max1 = -1
max2 = -1
min1 = 10000
min2 = 10000
# Traversal
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