Maximum Product Difference Between Two Pairs

Difficulty: Easy | Acceptance: 83.10% | Paid: No Topics: Array, Sorting

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, 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
• Constraints
• Brute Force
• Sorting
• Linear Scan

Examples

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) = 42 - 8 = 34.

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) = 72 - 8 = 64.

Constraints

4 <= nums.length <= 10⁴
1 <= nums[i] <= 10⁴

Brute Force

Intuition We can check every possible combination of four distinct indices to form two pairs and calculate the product difference for each combination.

Steps

• Initialize a variable maxDiff to store the maximum product difference found.
• Use four nested loops to iterate through all possible combinations of four distinct indices i, j, k, l.
• Calculate the product difference (nums[i] * nums[j]) - (nums[k] * nums[l]).
• Update maxDiff if the current difference is greater.
• Return maxDiff.

class Solution:
    def maxProductDifference(self, nums: list[int]) -> int:
        n = len(nums)
        max_diff = 0
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(n):
                    if k == i or k == j:
                        continue
                    for l in range(k + 1, n):
                        if l == i or l == j:
                            continue
                        prod_diff = (nums[i] * nums[j]) - (nums[k] * nums[l])
                        if prod_diff > max_diff:
                            max_diff = prod_diff
        return max_diff

Complexity

• Time: O(n⁴) - Four nested loops iterate through the array.
• Space: O(1) - Only a few variables are used.
• Notes: This approach is inefficient and will result in a Time Limit Exceeded error for large inputs.

Sorting

Intuition To maximize the value of (a * b) - (c * d), we need to maximize the product (a * b) and minimize the product (c * d). Sorting the array allows us to easily access the largest and smallest elements.

Steps

• Sort the array in ascending order.
• The two largest numbers will be at the end of the array (nums[n-1], nums[n-2]).
• The two smallest numbers will be at the beginning of the array (nums[0], nums[1]).
• Calculate the product difference using these four values and return it.

class Solution:
    def maxProductDifference(self, nums: list[int]) -> int:
        nums.sort()
        n = len(nums)
        return (nums[n - 1] * nums[n - 2]) - (nums[0] * nums[1])

Complexity

• Time: O(n log n) - Due to the sorting step.
• Space: O(1) or O(n) - Depending on the sorting algorithm’s space complexity (e.g., heapsort is O(1), mergesort is O(n)).
• Notes: This is a clean and readable solution, though we can do better in terms of time complexity.

Linear Scan

Intuition We only need the two largest numbers and the two smallest numbers in the array. We can find these in a single pass without sorting the entire array.

Steps

• Initialize variables to track the two largest numbers (max1, max2) and the two smallest numbers (min1, min2).
• Set max1, max2 to 0 (since nums[i] >= 1) and min1, min2 to a very large number (infinity).
• Iterate through the array once:
  • Update max1 and max2 if the current number is greater than the current maximums.
  • Update min1 and min2 if the current number is smaller than the current minimums.
• Calculate the product difference using the found values and return it.

class Solution:
    def maxProductDifference(self, nums: list[int]) -> int:
        max1 = max2 = 0
        min1 = min2 = float('inf')
        
        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)

Complexity

• Time: O(n) - We traverse the array exactly once.
• Space: O(1) - We only use a constant amount of extra space.
• Notes: This is the most optimal approach for this problem.