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 themaximum such product difference.

Examples

Example 1

1
2
3
4
5
6
7
8


    
    
    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

1
2
3
4
5
6
7
8


    
    
    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 <= 10^4
  • 1 <= nums[i] <= 10^4

Solution

Method 1 – Sorting and Greedy

Intuition

To maximize the product difference, we want the largest two numbers for one pair and the smallest two for the other. Sorting the array makes it easy to pick these values directly.

Approach

  1. Sort the array nums in ascending order.
  2. The two largest numbers are at the end, and the two smallest at the start.
  3. Compute the product difference: (nums[-1] * nums[-2]) - (nums[0] * nums[1]).
  4. Return the result.

Code

1
2
3
4
5
6
7
8

class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        int n = nums.size();
        return nums[n-1] * nums[n-2] - nums[0] * nums[1];
    }
};
1
2
3
4
5
6

import "sort"
func maxProductDifference(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    return nums[n-1]*nums[n-2] - nums[0]*nums[1]
}
1
2
3
4
5
6
7
8

import java.util.*;
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];
    }
}
1
2
3
4
5
6
7

class Solution {
    fun maxProductDifference(nums: IntArray): Int {
        nums.sort()
        val n = nums.size
        return nums[n-1] * nums[n-2] - nums[0] * nums[1]
    }
}
1
2
3
4

class Solution:
    def maxProductDifference(self, nums: list[int]) -> int:
        nums.sort()
        return nums[-1] * nums[-2] - nums[0] * nums[1]
1
2
3
4
5
6
7

impl Solution {
    pub fn max_product_difference(mut nums: Vec<i32>) -> i32 {
        nums.sort();
        let n = nums.len();
        nums[n-1] * nums[n-2] - nums[0] * nums[1]
    }
}
1
2
3
4
5
6
7

class Solution {
    maxProductDifference(nums: number[]): number {
        nums.sort((a, b) => a - b);
        const n = nums.length;
        return nums[n-1] * nums[n-2] - nums[0] * nums[1];
    }
}

Complexity

  • ⏰ Time complexity: O(n log n), for sorting the array.
  • 🧺 Space complexity: O(1), if sorting in-place.