#1913

Easy

LeetCode Problem Workspace

Maximum Product Difference Between Two Pairs

Find the maximum product difference between two pairs in an integer array using sorting for optimal selection.

Problem Statement

Given an integer array nums, select four distinct elements to form two pairs. Define the product difference as the first pair product minus the second pair product. Your goal is to maximize this difference.

Return the maximum product difference. Ensure that the chosen elements are distinct and account for array boundaries. Consider sorting to simplify finding the largest and smallest numbers, which directly impacts the result.

Examples

Example 1

Input: nums = [5,6,2,7,4]

Output: 34

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

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 Approach

Sort the Array

Sorting the array ensures that the largest and smallest numbers are easily accessible. Use a built-in sort to arrange numbers in ascending order.

Select Extreme Pairs

Pick the two largest numbers as the first pair and the two smallest numbers as the second pair. This guarantees the maximum product difference without iterating through all combinations.

Compute Product Difference

Calculate the product of both pairs and subtract the smaller product from the larger product. Return this value as the final result, leveraging the sorted positions for efficiency.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(1)

Sorting the array takes O(n log n) time but accessing the first and last two elements is O(1). Space complexity is O(1) if sorting in place or O(n) if a copy is used.

What Interviewers Usually Probe

Consider how to pick elements for maximum product without brute force.
Expect hints about sorting to simplify selecting extreme values.
Watch for questions on handling duplicate numbers or small arrays.

Common Pitfalls or Variants

Common pitfalls

Failing to select distinct indices and accidentally using the same element twice.
Not considering that the smallest numbers may also be needed to minimize the second pair product.
Attempting to check all combinations instead of leveraging sorting for efficiency.

Follow-up variants

Maximize the product difference when array elements can be negative.
Find the maximum product difference for k pairs instead of 2 pairs.
Compute the maximum sum difference between two pairs instead of product.

FAQ

What is the key idea behind Maximum Product Difference Between Two Pairs?

The key is to select two largest numbers for one pair and two smallest numbers for the other, then subtract their products.

Can the array contain negative numbers?

Yes, negative numbers are allowed and may affect which pairs produce the maximum difference.

Do I need to check all combinations of four numbers?

No, sorting the array allows direct access to the extremes, avoiding unnecessary combinations.

What if there are duplicate numbers in the array?

Duplicates are fine as long as distinct indices are used; the product difference formula still applies.

Which LeetCode pattern does this problem use?

This problem follows the Array plus Sorting pattern, focusing on selecting extreme values efficiently.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

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

Continue Practicing

#1921 eliminate maximum number of monsters #1889 minimum space wasted from packaging #1887 reduction operations to make the array elements equal