Formatted question description: https://leetcode.ca/all/1913.html

1913. Maximum Product Difference Between Two Pairs

Level

Easy

Description

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

Solution

Since all elements in nums are positive, to maximize the product difference, the two pairs should be the two maximum elements and the two minimum elements, respectively. Therefore, sort the array, get the two maximum elements and the two minimum elements, and return the product difference between the two pairs.

class Solution {
    public int maxProductDifference(int[] nums) {
        Arrays.sort(nums);
        int length = nums.length;
        return nums[length - 2] * nums[length - 1] - nums[0] * nums[1];
    }
}

All Problems

All Solutions