problemeasyalgorithmsleetcode-1913leetcode 1913leetcode1913

Maximum Product Difference Between Two Pairs

EasyUpdated: Aug 2, 2025
Practice on:
LeetCode

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


    
    
    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 <= 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

C++
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];
    }
};
Go
import "sort"
func maxProductDifference(nums []int) int {
    sort.Ints(nums)
    n := len(nums)
    return nums[n-1]*nums[n-2] - nums[0]*nums[1]
}
Java
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];
    }
}
Kotlin
class Solution {
    fun maxProductDifference(nums: IntArray): Int {
        nums.sort()
        val n = nums.size
        return nums[n-1] * nums[n-2] - nums[0] * nums[1]
    }
}
Python
class Solution:
    def maxProductDifference(self, nums: list[int]) -> int:
        nums.sort()
        return nums[-1] * nums[-2] - nums[0] * nums[1]
Rust
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]
    }
}
TypeScript
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.

Comments