Maximum Product Difference Between Two Pairs
EasyPrompt
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
Approaches
2 approaches with complexity analysis and trade-offs.
The problem asks to maximize the expression (a * b) - (c * d). To achieve this, we need to maximize the product a * b and minimize the product c * d. Since all numbers in the input array are positive, the product of two numbers is maximized by choosing the two largest numbers available, and minimized by choosing the two smallest numbers.
This insight simplifies the problem to finding the two largest and two smallest elements in the array. A straightforward way to do this is by sorting the array.
Algorithm
- Sort the input array
numsin ascending order. - Let
nbe the length of the array. - The two smallest numbers are
nums[0]andnums[1]. - The two largest numbers are
nums[n-1]andnums[n-2]. - The maximum product difference is calculated as
(nums[n-1] * nums[n-2]) - (nums[0] * nums[1]).
Walkthrough
If we sort the array nums in non-decreasing order, the two smallest elements will be at the beginning of the array, and the two largest elements will be at the end.
import java.util.Arrays; class Solution { public int maxProductDifference(int[] nums) { // Sort the array in ascending order. Arrays.sort(nums); int n = nums.length; // The two largest numbers are at the end of the sorted array. int largestProduct = nums[n - 1] * nums[n - 2]; // The two smallest numbers are at the beginning of the sorted array. int smallestProduct = nums[0] * nums[1]; // Return the difference. return largestProduct - smallestProduct; }}Complexity
Time
O(n log n), where n is the number of elements in the array. The dominant operation is sorting the array, which typically takes O(n log n) time.
Space
O(log n) to O(n). The space complexity depends on the implementation of the sorting algorithm. In Java, `Arrays.sort()` for primitive types uses a variant of Quicksort, which has an average space complexity of O(log n) for the recursion stack.
Trade-offs
Pros
Simple to understand and implement.
Correctly finds the two largest and two smallest elements.
Cons
Not the most efficient solution in terms of time complexity. Sorting the entire array is more work than necessary, as we only need the four extreme values.
Solutions
Solution
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 ]; } }Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.