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:
-
Sorting: The input list
nums
is sorted. This is done with thenums.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 ofO(n log n)
, wheren
is the number of elements in the list. -
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]
andnums[-2]
give us the largest and second-largest numbers, respectively. -
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)
. -
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]
andnums[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)
. -
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)
. -
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.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample 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:
-
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. -
Selecting Elements: The two largest numbers, which are now at the end of the array, are
9
and7
. The two smallest numbers at the beginning of the array are1
and2
. -
Calculating the Product of the Largest Pair: We multiply the largest two numbers to get the maximum product
(a * b) = 9 * 7 = 63
. -
Calculating the Product of the Smallest Pair: Next, we multiply the smallest two numbers to get the minimum product
(c * d) = 1 * 2 = 2
. -
Calculating the Product Difference: The product difference
(a * b) - (c * d)
is thus63 - 2 = 61
. -
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.
What's the relationship between a tree and a graph?
Recommended Readings
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
LeetCode Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way we
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https algomonster s3 us east 2 amazonaws com recursion jpg You first
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.