💬 Discord
Sign In
NeetCode #73LC-1913EasyArrays & Hashing
← Back to All Problems

#73 · #1913 · Maximum Product Difference Between Two Pairs(两个数对之间的最大乘积差)

📌 Problem Statement & Constraints

The product difference between two pairs (a, b) and (c, d) is (a * b) - (c * d). Given an array nums of distinct integers, return the maximum product difference over all choices of four distinct indices. Constraints: 4 <= nums.length <= 10^4, 1 <= nums[i] <= 10^4.

💡 Core Algorithmic Approaches

  1. The maximum is achieved by taking the two largest values for the positive product and the two smallest for the subtracted one.
  2. Sort the array, then the answer is nums[-1] * nums[-2] - nums[0] * nums[1].
  3. Since all values are positive, the sign logic is unambiguous -- no need to consider negative products.
  4. A single pass tracking the two largest and two smallest values avoids the sort entirely.

💻 Benchmark Python3 Implementation

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


# One-pass variant: O(n) time, O(1) space
class Solution2:
    def maxProductDifference(self, nums: List[int]) -> int:
        mx1 = mx2 = -1                 # two largest
        mn1 = mn2 = float("inf")       # two smallest
        for x in nums:
            if x > mx1:
                mx1, mx2 = x, mx1
            elif x > mx2:
                mx2 = x
            if x < mn1:
                mn1, mn2 = x, mn1
            elif x < mn2:
                mn2 = x
        return mx1 * mx2 - mn1 * mn2

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n log n) for the sort-based version, O(n) for the one-pass version.
💾 Space Complexity
O(1) for both (the sort is in place).

⚠️ Interview Pitfalls & Follow-ups

  • Subtracting the two largest from the two smallest in the wrong order: the large product must come first.
  • Assuming negative values exist: the constraints guarantee nums[i] >= 1, which is what makes the simple formula valid. With negatives you would have to consider min * min for the positive term.
  • Using the same index twice: the four indices must be distinct, which is automatic since the two largest and two smallest come from disjoint positions when n >= 4.