Skip to content

LeetCode: 1913-Maximum Product Difference Between Two Pairs Solution

Last Updated on 2023-12-18 by Clay

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 wxy, 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 <= 104
  • 1 <= nums[i] <= 104

Solution

The easiest way is use sort and get the head and tail, but the time complexity is O(n*log(n)), be honestly, it is not good.

Another intuited method is claim four variables, largest, secondLargest, smallest, secondSmallest... and update them when traversing the array.

Be careful, if the largest number is replaced, the original largest number will be assign to secondLargest. The small case is the same.

And now, we can think our time complexity is O(n) and space complexity is O(1).


C++ Sample Code

class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        // Init
        int max1 = INT_MIN;
        int max2 = INT_MIN;
        int min1 = INT_MAX;
        int min2 = INT_MAX;

        // Traversal
        for (int& num: nums) {
            if (num >= max1) {
                max2 = max1;
                max1 = num;
            }
            else if (num >= max2) {
                max2 = num;
            }
            
            if (num <= min1) {
                min2 = min1;
                min1 = num;
            }
            else if (num <= min2) {
                min2 = num;
            }
        }

        return max1 * max2 - min1 * min2;
    }
};





Python Sample Code

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        # Init
        max1 = -1
        max2 = -1
        min1 = 10000
        min2 = 10000

        # Traversal
        for num in nums:
            if num >= max1:
                max2 = max1
                max1 = num
            elif num >= max2:
                max2 = num
            
            if num <= min1:
                min2 = min1
                min1 = num
            elif num <= min2:
                min2 = num

        return max1 * max2 - min1 * min2





References


Read More

Leave a Reply