Maximum Product Difference Between Two Pairs

Easy
266.

Maximum Product Difference Between Two Pairs

Maximum Product Difference Between Two Pairs is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.

The product difference between two pairs (a, b) and (c, d) is (a × b) - (c × d).

Given an integer array nums, choose four distinct indices forming two pairs so that the product difference is maximised, and return it.

Example 1

Input
nums = [5,6,2,7,4]
Output
34
Explanation
(6 × 7) - (2 × 4) = 42 - 8.

Example 2

Input
nums = [4,2,5,9,7,4,8]
Output
64
Explanation
(9 × 8) - (2 × 4) = 72 - 8.

Example 3

Input
nums = [1,2,3,4]
Output
10

Constraints

  • 4 <= nums.length <= 40
  • 1 <= nums[i] <= 1000
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var maxProductDifference = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Maximum Product Difference Between Two Pairs — Solution

Maximum Product Difference Between Two Pairs solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript.

Maximum Product Difference Between Two Pairs is an easy coding problem on arrays, sorting and greedy, asked in Amazon and Adobe interviews.

  • Difficulty: Easy
  • Topics: Arrays, Sorting, Greedy
  • Asked at: Amazon, Adobe
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

The product difference between two pairs (a, b) and (c, d) is (a × b) - (c × d).

Given an integer array nums, choose four distinct indices forming two pairs so that the product difference is maximised, and return it.

Example 1

Input: nums = [5,6,2,7,4]
Output: 34
Explanation: (6 × 7) - (2 × 4) = 42 - 8.

Example 2

Input: nums = [4,2,5,9,7,4,8]
Output: 64
Explanation: (9 × 8) - (2 × 4) = 72 - 8.

Example 3

Input: nums = [1,2,3,4]
Output: 10

Constraints

  • 4 <= nums.length <= 40
  • 1 <= nums[i] <= 1000

Hints for Maximum Product Difference Between Two Pairs

  1. Hint 1

    All values are positive, so the first product is maximised by the two largest and the second minimised by the two smallest.

  2. Hint 2

    Sorting makes both pairs immediate — or track the top two and bottom two in one pass.

How to solve Maximum Product Difference Between Two Pairs

Positive values: the largest product comes from the two biggest numbers, the smallest from the two smallest.

Approach

  1. Sort.
  2. Return a[-1] * a[-2] - a[0] * a[1].

Why it works

With all values positive, products are monotone in each factor, so the extremes are attained at the two ends of the sorted order; four distinct indices are guaranteed by n >= 4.

Complexity

  • Time — O(n log n)
  • Space — O(n)

Pitfalls

  • One pass tracking the top two and bottom two makes it O(n).

Reference solution

Python

def maxProductDifference(nums) -> int:
    a = sorted(nums)
    return a[-1] * a[-2] - a[0] * a[1]

Java

public static int maxProductDifference(int[] nums) {
    int[] a = Arrays.copyOf(nums, nums.length);
    Arrays.sort(a);
    int n = a.length;
    return a[n - 1] * a[n - 2] - a[0] * a[1];
}

C++

int maxProductDifference(vector<int>& nums) {
    vector<int> a = nums;
    sort(a.begin(), a.end());
    int n = (int) a.size();
    return a[n - 1] * a[n - 2] - a[0] * a[1];
}

JavaScript

var maxProductDifference = function(nums) {
    const a = nums.slice().sort(function(x, y) { return x - y; });
    const n = a.length;
    return a[n - 1] * a[n - 2] - a[0] * a[1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms