1913. Maximum Product Difference Between Two Pairs


Problem Description

The problem presents us with the concept of the product difference between two pairs of numbers (a, b) and (c, d), which is calculated as (a * b) - (c * d). The main objective is to find four distinct elements in an integer array nums, such that when you form two pairs with these elements and calculate their product difference, the result is as large as possible.

Consider an integer array nums. The task is to choose four distinct indices w, x, y, and z from this array such that the product difference calculated with elements at these indices (nums[w] * nums[x]) - (nums[y] * nums[z]) is the maximum possible.

For example, if you have the numbers {1,2,3,4}, the maximum product difference would be calculated by using the highest two numbers for multiplication to form the first pair, and the lowest two numbers to form the second pair. The maximum product difference in this case would be (4*3) - (1*2) = 10.

Intuition

To maximize the product difference, we need the first product (a * b) to be as large as possible and the second product (c * d) to be as small as possible. A natural strategy to achieve this is to sort the array first.

When an array is sorted in ascending order:

  • The two largest values, which will be at the end of the array, can be used to form the maximum product pair (a * b).
  • Conversely, the two smallest values, which will be at the beginning of the array, will form the minimum product pair (c * d).

By selecting these pairs, the product difference (a * b) - (c * d) will be maximized. This is because multiplication is a commutative operation (meaning a * b is the same as b * a), and sorting the array gives us direct access to the largest and smallest values without additional comparisons.

Accordingly, by sorting nums, and then calculating the product of the last two elements and subtracting the product of the first two elements, we reach the solution.

The solution approach is direct and efficient, aligning with our intuition of maximizing the first product and minimizing the second.

Learn more about Sorting patterns.

Solution Approach

The method of solving this problem involves just a few straightforward steps but is grounded in understanding how sorting affects the arrangement of numbers and how it can be leveraged to find the maximum product difference. The approach follows these distinct steps:

  1. Sorting: The input list nums is sorted. This is done with the nums.sort() method. Sorting rearranges the elements in the list from the smallest to the largest. In Python, this operation has an average and worst-case time complexity of O(n log n), where n is the number of elements in the list.

  2. Selecting Elements: After sorting, the two largest numbers will be placed at the end of the list. In Python, negative indices can be used to access elements from the end of a list. Thus nums[-1] and nums[-2] give us the largest and second-largest numbers, respectively.

  3. Calculating the Product of the Largest Pair: The largest and second-largest numbers are then multiplied together to form the maximum possible product from the list. This is the first part of the product difference calculation, denoted as (a * b).

  4. Calculating the Product of the Smallest Pair: Similarly, the smallest numbers will now be at the very beginning of the list. By directly accessing nums[0] and nums[1], the first two elements, we get the smallest and second-smallest numbers, which are multiplied together. This product forms the second part of the product difference, denoted as (c * d).

  5. Calculating the Product Difference: Finally, we calculate the product difference by subtracting the product of the smallest pair from the product of the largest pair, i.e., (a * b) - (c * d).

  6. Return the Result: The last step is simply to return the result of the product difference calculation.

The solution utilizes the built-in sorting algorithm and simple list indexing, which make the implementation quite efficient. The only data structure used is the list itself, and no additional space is required. The approach takes advantage of the sorted order of elements to quickly and directly access the values needed to maximize the product difference.

Here is the code snippet that encapsulates our solution approach:

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

This solution strategy provides a quick and elegant way to achieve the desired result, and it's an excellent example of how sorting can simplify certain types of problems.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What is the space complexity of the following code?

1int sum(int n) {
2  if (n <= 0) {
3    return 0;
4  }
5  return n + sum(n - 1);
6}

Example Walkthrough

To help illustrate the solution approach, let's go through a small example using the array nums = [4, 2, 5, 9, 7, 1].

Following the steps outlined in the solution approach:

  1. Sorting: First, we sort the array nums to obtain [1, 2, 4, 5, 7, 9]. After sorting, the smallest numbers are at the start and the largest at the end.

  2. Selecting Elements: The two largest numbers, which are now at the end of the array, are 9 and 7. The two smallest numbers at the beginning of the array are 1 and 2.

  3. Calculating the Product of the Largest Pair: We multiply the largest two numbers to get the maximum product (a * b) = 9 * 7 = 63.

  4. Calculating the Product of the Smallest Pair: Next, we multiply the smallest two numbers to get the minimum product (c * d) = 1 * 2 = 2.

  5. Calculating the Product Difference: The product difference (a * b) - (c * d) is thus 63 - 2 = 61.

  6. Return the Result: We return 61 as the maximum product difference we can get from the array by choosing four distinct elements to form two pairs.

By following these steps, we have maximized the product difference using the numbers 9, 7 (the largest pair), and 1, 2 (the smallest pair) from the given array nums. This approach can be applied to any input array to efficiently find the maximum product difference.

Solution Implementation

1# We are using the typing module for type hints
2from typing import List
3
4class Solution:
5    def maxProductDifference(self, nums: List[int]) -> int:
6        # First, we sort the list of numbers in ascending order.
7        nums.sort()
8      
9        # The largest elements will be at the end of the sorted list, and
10        # the smallest elements will be at the beginning.
11        # Therefore, the product of the two largest elements can be found
12        # by multiplying the last two elements in the sorted list.
13        largest_product = nums[-1] * nums[-2]
14      
15        # Similarly, the product of the two smallest elements can be found
16        # by multiplying the first two elements in the sorted list.
17        smallest_product = nums[0] * nums[1]
18      
19        # The maximum product difference is the difference between the
20        # largest product and the smallest product.
21        max_product_difference = largest_product - smallest_product
22      
23        # Return the computed maximum product difference.
24        return max_product_difference
25
1import java.util.Arrays; // Import Arrays class to use the sort method
2
3public class Solution {
4    // Method to find the maximum product difference between two pairs
5    // The two pairs consist of the product of the two largest numbers
6    // and the product of the two smallest numbers in the given array.
7    public int maxProductDifference(int[] nums) {
8        // Sort the array to easily find the smallest and largest elements
9        Arrays.sort(nums);
10      
11        int length = nums.length; // Store the length of the array
12      
13        // Calculate the product difference:
14        // maxProduct is the product of the two largest numbers
15        int maxProduct = nums[length - 1] * nums[length - 2];
16      
17        // minProduct is the product of the two smallest numbers
18        int minProduct = nums[0] * nums[1];
19      
20        // Return the difference between maxProduct and minProduct
21        return maxProduct - minProduct;
22    }
23}
24
1#include <vector>
2#include <algorithm> // Include algorithm header for std::sort
3
4class Solution {
5public:
6    // Function to calculate the maximum product difference between two pairs (a, b) and (c, d) 
7    // where a and b are elements from nums, and c and d are elements from nums.
8    int maxProductDifference(std::vector<int>& nums) {
9        // Sort the input vector in non-decreasing order.
10        std::sort(nums.begin(), nums.end());
11
12        // Get the size of the nums array.
13        int size = nums.size();
14
15        // The maximum product is the product of the last two elements in the sorted array,
16        // and the minimum product is the product of the first two elements.
17        // Calculate the product difference by subtracting the minimum product from the maximum product.
18        int productDifference = nums[size - 1] * nums[size - 2] - nums[0] * nums[1];
19
20        // Return the calculated product difference.
21        return productDifference;
22    }
23};
24
1/**
2 * Function to calculate the maximum product difference between two pairs of numbers
3 * in an array. The product difference is defined as the product of the two largest
4 * numbers minus the product of the two smallest numbers.
5 * 
6 * @param {number[]} nums - The array of numbers
7 * @return {number} - The maximum product difference
8 */
9function maxProductDifference(nums: number[]): number {
10    // Sort the array in non-decreasing order
11    nums.sort((a, b) => a - b);
12  
13    // Get the length of the array
14    const length = nums.length;
15  
16    // Calculate the product of the two largest numbers
17    const productOfLargest = nums[length - 1] * nums[length - 2];
18  
19    // Calculate the product of the two smallest numbers
20    const productOfSmallest = nums[0] * nums[1];
21  
22    // Calculate the difference between the two products
23    const answer = productOfLargest - productOfSmallest;
24  
25    // Return the maximum product difference
26    return answer;
27}
28
29// Example usage:
30// const result = maxProductDifference([5, 6, 2, 7, 4]);
31// console.log(result); // Output will be the maximum product difference
32

Time and Space Complexity

The time complexity of the given code is O(n log n), where n is the number of elements in the list nums. This time complexity arises from the sorting operation nums.sort(). Sorting is the most computationally intensive part of this code.

Once the list is sorted, accessing the four elements needed to compute the product difference (the first two elements and the last two elements) is done in constant time, O(1).

The space complexity of the code is O(1) if we consider the sort to be in-place, which it is for Python's default sorting algorithm (Timsort). No additional space is proportional to the input size is utilized besides potential negligible temporary variables for holding products and the result of the subtraction.

Learn more about how to find time and space complexity quickly using problem constraints.


Fast Track Your Learning with Our Quick Skills Quiz:

Which of the following shows the order of node visit in a Breadth-first Search?


Recommended Readings


Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.


🪄