The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).
(5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.Given an integer array nums, choose four distinct indices w, x, y, and 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.
Example 1:
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) = 34.
Example 2:
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) = 64.
Constraints:
4 <= nums.length <= 1041 <= nums[i] <= 104This approach involves sorting the array and then selecting the appropriate numbers to form two pairs. The largest two numbers should form one pair to maximize the product, and the smallest two numbers should form the other pair to minimize the product. This ensures that the product difference is as large as possible:
1. Sort the array nums.
2. Select the two largest numbers for (a, b) and the two smallest numbers for (c, d).
3. Compute the product difference as (a * b) - (c * d).
The given C solution sorts the array using qsort() and calculates the maximum product difference by multiplying the two largest and two smallest numbers. It prints the result after computing.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting the array, where n is the length of the array.
Space Complexity: O(1) as we sort the array in place and use a constant amount of extra space.
Instead of sorting, we can solve the problem in linear time by keeping track of the four numbers we need: the two largest numbers and the two smallest numbers:
1. Initialize variables to hold the minimum two and maximum two values seen so far.
2. Iterate through the array, updating these variables accordingly.
3. Calculate the product difference with the two largest and two smallest values obtained.
In this C implementation, we use four variables to retain the largest and smallest elements while iterating through nums, thereby avoiding sorting and achieving linear time complexity.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n) since we traverse the array only once.
Space Complexity: O(1) because we use a constant amount of space.
| Approach | Complexity |
|---|---|
| Sort and Pick Extremes | Time Complexity: O(n log n) due to sorting the array, where Space Complexity: O(1) as we sort the array in place and use a constant amount of extra space. |
| Linear Pass with Four Variables | Time Complexity: O(n) since we traverse the array only once. Space Complexity: O(1) because we use a constant amount of space. |
Maximum Product Difference Between Two - Leetcode 1913 - Python • NeetCodeIO • 6,162 views views
Watch 9 more video solutions →Practice Maximum Product Difference Between Two Pairs with our built-in code editor and test cases.
Practice on FleetCode