Maximum Product Difference Between Two Pairs — Solution
Maximum Product Difference Between Two Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.
Maximum Product Difference Between Two Pairs is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.
- Difficulty: Easy
- Topics: Arrays, Sorting, Greedy
- Asked at: Amazon, Adobe
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
The product difference between two pairs (a, b) and (c, d) is (a × b) - (c × d).
Given an integer array nums, choose four distinct indices forming two pairs so that the product difference is maximised, and return it.
Example 1
Input: nums = [5,6,2,7,4]
Output: 34
Explanation: (6 × 7) - (2 × 4) = 42 - 8.
Example 2
Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: (9 × 8) - (2 × 4) = 72 - 8.
Example 3
Input: nums = [1,2,3,4]
Output: 10
Constraints
4 <= nums.length <= 401 <= nums[i] <= 1000
Hints for Maximum Product Difference Between Two Pairs
Hint 1
All values are positive, so the first product is maximised by the two largest and the second minimised by the two smallest.
Hint 2
Sorting makes both pairs immediate — or track the top two and bottom two in one pass.
How to solve Maximum Product Difference Between Two Pairs
Positive values: the largest product comes from the two biggest numbers, the smallest from the two smallest.
Approach
- Sort.
- Return
a[-1] * a[-2] - a[0] * a[1].
Why it works
With all values positive, products are monotone in each factor, so the extremes are attained at the two ends of the sorted order; four distinct indices are guaranteed by n >= 4.
Complexity
- Time —
O(n log n) - Space —
O(n)
Pitfalls
- One pass tracking the top two and bottom two makes it O(n).
Reference solution
Python
def maxProductDifference(nums) -> int:
a = sorted(nums)
return a[-1] * a[-2] - a[0] * a[1]Java
public static int maxProductDifference(int[] nums) {
int[] a = Arrays.copyOf(nums, nums.length);
Arrays.sort(a);
int n = a.length;
return a[n - 1] * a[n - 2] - a[0] * a[1];
}C++
int maxProductDifference(vector<int>& nums) {
vector<int> a = nums;
sort(a.begin(), a.end());
int n = (int) a.size();
return a[n - 1] * a[n - 2] - a[0] * a[1];
}JavaScript
var maxProductDifference = function(nums) {
const a = nums.slice().sort(function(x, y) { return x - y; });
const n = a.length;
return a[n - 1] * a[n - 2] - a[0] * a[1];
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Sorting Algorithms