Watch 10 video solutions for Maximum Product Difference Between Two Pairs, a easy level problem involving Array, Sorting. This walkthrough by NeetCodeIO has 6,629 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
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] <= 104Problem Overview: You receive an integer array nums. The task is to choose four distinct elements and compute the maximum value of (a * b) - (c * d). To maximize this expression, you want the product of the two largest numbers and subtract the product of the two smallest numbers.
Approach 1: Sort and Pick Extremes (Time: O(n log n), Space: O(1) or O(log n) depending on sort)
Sorting the array makes the structure obvious. After sorting, the two largest values sit at the end of the array and the two smallest values at the beginning. Compute (nums[n-1] * nums[n-2]) - (nums[0] * nums[1]). This works because any other pair would reduce the first product or increase the second one, lowering the final difference. The implementation is short and reliable, which makes it a good baseline solution when using sorting utilities already available in your language.
The algorithm performs a full sort of the array, which costs O(n log n) time. Space usage depends on the sorting implementation but is typically O(1) for in-place sorts or O(log n) due to recursion. If the array is already sorted or you are solving multiple queries on the same sorted data, this approach becomes even more convenient.
Approach 2: Linear Pass with Four Variables (Time: O(n), Space: O(1))
A more optimal solution avoids sorting entirely. Instead, track the two largest and two smallest numbers while scanning the array once. Maintain variables such as max1, max2, min1, and min2. During each iteration, update these values based on comparisons with the current element.
At the end of the scan, compute the result using (max1 * max2) - (min1 * min2). The key insight is that only four numbers influence the final answer: the top two and bottom two values in the array. Everything else is irrelevant. This approach leverages a single pass over the array, making it strictly faster than sorting for large inputs.
This method runs in O(n) time and uses constant O(1) extra space. It’s also straightforward to implement in languages like C++, Java, or Python with simple conditional checks.
Recommended for interviews: The linear pass with four variables is the solution interviewers typically expect. Sorting demonstrates the correct observation about extremes, but the O(n) scan shows stronger algorithmic thinking and better control over array traversal. Mention the sorting approach first if discussing tradeoffs, then implement the linear scan as the optimal answer.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Pick Extremes | O(n log n) | O(1) to O(log n) | When simplicity matters or the array is already sorted |
| Linear Pass with Four Variables | O(n) | O(1) | Best general solution when you want optimal time without sorting |