193.md

1913. Maximum Product Difference Between Two Pairs

Difficulty: 🟢 Easy

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.

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

Solutions

O(n) solution

Python3

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        min_1, min_2 = float("inf"), float("inf")
        max_1, max_2 = float("-inf"), float("-inf")

        for num in nums:
            if num > max_1:
                max_2 = max_1
                max_1 = num
            elif num > max_2:
                max_2 = num

            if num < min_1:
                min_2 = min_1
                min_1 = num
            elif num < min_2:
                min_2 = num

        return max_1 * max_2 - min_1 * min_2

The solution aims to find the maximum product difference by identifying the four largest and two smallest elements in the nums array. To do this, we maintain four variables to keep track of the two largest (max_1 and max_2) and two smallest (min_1 and min_2) elements as we iterate through the array.

Here's a step-by-step explanation of the solution:

1. Initialize min_1, min_2, max_1, and max_2 to positive and negative infinity, respectively. These variables will be used to track the two smallest and two largest elements in the nums array.

2. Iterate through each element num in the nums array.

   • Check if num is greater than max_1. If it is, update max_2 to max_1 and max_1 to num.
   • If num is not greater than max_1 but is greater than max_2, update max_2 to num.
   • Check if num is less than min_1. If it is, update min_2 to min_1 and min_1 to num.
   • If num is not less than min_1 but is less than min_2, update min_2 to num.

3. After iterating through the entire array, calculate the maximum product difference using the two largest and two smallest elements:

   • max_product_difference = (max_1 * max_2) - (min_1 * min_2)

4. Return max_product_difference as the result.

Complexity Analysis

• Time Complexity: The solution iterates through the nums array once, resulting in a time complexity of O(n), where n is the length of the array.

• Space Complexity: The space complexity is O(1) because the solution uses a fixed number of variables to track the two largest and two smallest elements.

Summary

The solution efficiently finds the maximum product difference between two pairs of distinct elements in the nums array by identifying the two largest and two smallest elements. It then calculates the product difference using these values and returns the result. The time complexity of the solution is linear in the size of the array, making it an efficient solution.

NB: If you want to get community points please suggest solutions in other languages as merge requests.