1913. Maximum Product Difference Between Two Pairs - Explanation

Description

The product difference between two pairs (a, b) and (c, d) is defined as (a * b) - (c * d).

For example, the product difference between (5, 6) and (2, 7) is (5 * 6) - (2 * 7) = 16.

You are given an integer array nums, choose four distinct indices w, x, y, and zsuch 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 <= 10,000
1 <= nums[i] <= 10,000

Topics

Company Tags

Please upgrade to NeetCode Pro to view company tags.

Prerequisites

Before attempting this problem, you should be comfortable with:

Sorting - One approach sorts the array to easily access the two largest and two smallest elements
Single-Pass Min/Max Tracking - The optimal solution tracks the top 2 maximum and minimum values in one pass
Basic Array Manipulation - Understanding how to iterate and compare elements efficiently

1. Brute Force

Intuition

The product difference is (nums[a] * nums[b]) - (nums[c] * nums[d]) where all four indices are distinct. To maximize this, we want the first product as large as possible and the second product as small as possible. The brute force approach tries all valid combinations of four distinct indices.

Algorithm

Use four nested loops to select indices a, b, c, d.
Skip any iteration where indices overlap.
For each valid combination, compute the product difference.
Track and return the maximum difference found.

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        n, res = len(nums), 0
        for a in range(n):
            for b in range(n):
                if a == b: continue
                for c in range(n):
                    if a == c or b == c: continue
                    for d in range(n):
                        if a == d or b == d or c == d: continue
                        res = max(res, nums[a] * nums[b] - nums[c] * nums[d])
        return res

public class Solution {
    public int maxProductDifference(int[] nums) {
        int n = nums.length, res = 0;
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                if (a == b) continue;
                for (int c = 0; c < n; c++) {
                    if (a == c || b == c) continue;
                    for (int d = 0; d < n; d++) {
                        if (a == d || b == d || c == d) continue;
                        res = Math.max(res, nums[a] * nums[b] - nums[c] * nums[d]);
                    }
                }
            }
        }
        return res;
    }
}

class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        int n = nums.size(), res = 0;
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                if (a == b) continue;
                for (int c = 0; c < n; c++) {
                    if (a == c || b == c) continue;
                    for (int d = 0; d < n; d++) {
                        if (a == d || b == d || c == d) continue;
                        res = max(res, nums[a] * nums[b] - nums[c] * nums[d]);
                    }
                }
            }
        }
        return res;
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    maxProductDifference(nums) {
        const n = nums.length;
        let res = 0;
        for (let a = 0; a < n; a++) {
            for (let b = 0; b < n; b++) {
                if (a === b) continue;
                for (let c = 0; c < n; c++) {
                    if (a === c || b === c) continue;
                    for (let d = 0; d < n; d++) {
                        if (a === d || b === d || c === d) continue;
                        res = Math.max(
                            res,
                            nums[a] * nums[b] - nums[c] * nums[d],
                        );
                    }
                }
            }
        }
        return res;
    }
}

public class Solution {
    public int MaxProductDifference(int[] nums) {
        int n = nums.Length, res = 0;
        for (int a = 0; a < n; a++) {
            for (int b = 0; b < n; b++) {
                if (a == b) continue;
                for (int c = 0; c < n; c++) {
                    if (a == c || b == c) continue;
                    for (int d = 0; d < n; d++) {
                        if (a == d || b == d || c == d) continue;
                        res = Math.Max(res, nums[a] * nums[b] - nums[c] * nums[d]);
                    }
                }
            }
        }
        return res;
    }
}

func maxProductDifference(nums []int) int {
    n := len(nums)
    res := 0
    for a := 0; a < n; a++ {
        for b := 0; b < n; b++ {
            if a == b {
                continue
            }
            for c := 0; c < n; c++ {
                if a == c || b == c {
                    continue
                }
                for d := 0; d < n; d++ {
                    if a == d || b == d || c == d {
                        continue
                    }
                    if nums[a]*nums[b]-nums[c]*nums[d] > res {
                        res = nums[a]*nums[b] - nums[c]*nums[d]
                    }
                }
            }
        }
    }
    return res
}

class Solution {
    fun maxProductDifference(nums: IntArray): Int {
        val n = nums.size
        var res = 0
        for (a in 0 until n) {
            for (b in 0 until n) {
                if (a == b) continue
                for (c in 0 until n) {
                    if (a == c || b == c) continue
                    for (d in 0 until n) {
                        if (a == d || b == d || c == d) continue
                        res = maxOf(res, nums[a] * nums[b] - nums[c] * nums[d])
                    }
                }
            }
        }
        return res
    }
}

class Solution {
    func maxProductDifference(_ nums: [Int]) -> Int {
        let n = nums.count
        var res = 0
        for a in 0..<n {
            for b in 0..<n {
                if a == b { continue }
                for c in 0..<n {
                    if a == c || b == c { continue }
                    for d in 0..<n {
                        if a == d || b == d || c == d { continue }
                        res = max(res, nums[a] * nums[b] - nums[c] * nums[d])
                    }
                }
            }
        }
        return res
    }
}

impl Solution {
    pub fn max_product_difference(nums: Vec<i32>) -> i32 {
        let n = nums.len();
        let mut res = 0;
        for a in 0..n {
            for b in 0..n {
                if a == b { continue; }
                for c in 0..n {
                    if a == c || b == c { continue; }
                    for d in 0..n {
                        if a == d || b == d || c == d { continue; }
                        res = res.max(nums[a] * nums[b] - nums[c] * nums[d]);
                    }
                }
            }
        }
        res
    }
}

Time & Space Complexity

Time complexity: $O(n ^ 4)$
Space complexity: $O(1)$

2. Sorting

Intuition

To maximize the product difference, we need the two largest numbers for the first product and the two smallest numbers for the second product. After sorting, these are simply the last two and first two elements.

Algorithm

Sort the array in ascending order.
The maximum product is nums[n-1] * nums[n-2] (two largest).
The minimum product is nums[0] * nums[1] (two smallest).
Return their difference.

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

class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        sort(nums.begin(), nums.end());
        return nums[nums.size() - 1] * nums[nums.size() - 2] - nums[0] * nums[1];
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    maxProductDifference(nums) {
        nums.sort((a, b) => a - b);
        return (
            nums[nums.length - 1] * nums[nums.length - 2] - nums[0] * nums[1]
        );
    }
}

class Solution {
    func maxProductDifference(_ nums: [Int]) -> Int {
        let sorted = nums.sorted()
        let n = sorted.count
        return sorted[n - 1] * sorted[n - 2] - sorted[0] * sorted[1]
    }
}

Time & Space Complexity

Time complexity: $O(n \log n)$
Space complexity: $O(1)$ or $O(n)$ depending on the sorting algorithm.

3. Two Maximums and Two Minimums

Intuition

We only need the two largest and two smallest values, so we can find them in a single pass without sorting the entire array. By tracking these four values as we iterate, we achieve linear time complexity.

Algorithm

Initialize max1, max2 to 0 (or the smallest possible values) and min1, min2 to infinity (or the largest possible values).
For each number in the array:
- Update max1 and max2 if the current number is among the two largest seen so far.
- Update min1 and min2 if the current number is among the two smallest seen so far.
Return (max1 * max2) - (min1 * min2).

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        max1 = max2 = 0
        min1 = min2 = float('inf')

        for num in nums:
            if num > max1:
                max1, max2 = num, max1
            elif num > max2:
                max2 = num
            if num < min1:
                min1, min2 = num, min1
            elif num < min2:
                min2 = num

        return (max1 * max2) - (min1 * min2)

public class Solution {
    public int maxProductDifference(int[] nums) {
        int max1 = 0, max2 = 0;
        int min1 = Integer.MAX_VALUE, min2 = Integer.MAX_VALUE;
        for (int num : nums) {
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return (max1 * max2) - (min1 * min2);
    }
}

class Solution {
public:
    int maxProductDifference(vector<int>& nums) {
        int max1 = 0, max2 = 0;
        int min1 = INT_MAX, min2 = INT_MAX;
        for (int num : nums) {
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return (max1 * max2) - (min1 * min2);
    }
};

class Solution {
    /**
     * @param {number[]} nums
     * @return {number}
     */
    maxProductDifference(nums) {
        let max1 = 0,
            max2 = 0;
        let min1 = Infinity,
            min2 = Infinity;
        for (const num of nums) {
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return max1 * max2 - min1 * min2;
    }
}

public class Solution {
    public int MaxProductDifference(int[] nums) {
        int max1 = 0, max2 = 0;
        int min1 = int.MaxValue, min2 = int.MaxValue;
        foreach (int num in nums) {
            if (num > max1) {
                max2 = max1;
                max1 = num;
            } else if (num > max2) {
                max2 = num;
            }
            if (num < min1) {
                min2 = min1;
                min1 = num;
            } else if (num < min2) {
                min2 = num;
            }
        }
        return (max1 * max2) - (min1 * min2);
    }
}

func maxProductDifference(nums []int) int {
    max1, max2 := 0, 0
    min1, min2 := math.MaxInt32, math.MaxInt32
    for _, num := range nums {
        if num > max1 {
            max2 = max1
            max1 = num
        } else if num > max2 {
            max2 = num
        }
        if num < min1 {
            min2 = min1
            min1 = num
        } else if num < min2 {
            min2 = num
        }
    }
    return (max1 * max2) - (min1 * min2)
}

class Solution {
    fun maxProductDifference(nums: IntArray): Int {
        var max1 = 0
        var max2 = 0
        var min1 = Int.MAX_VALUE
        var min2 = Int.MAX_VALUE
        for (num in nums) {
            if (num > max1) {
                max2 = max1
                max1 = num
            } else if (num > max2) {
                max2 = num
            }
            if (num < min1) {
                min2 = min1
                min1 = num
            } else if (num < min2) {
                min2 = num
            }
        }
        return (max1 * max2) - (min1 * min2)
    }
}

class Solution {
    func maxProductDifference(_ nums: [Int]) -> Int {
        var max1 = 0, max2 = 0
        var min1 = Int.max, min2 = Int.max
        for num in nums {
            if num > max1 {
                max2 = max1
                max1 = num
            } else if num > max2 {
                max2 = num
            }
            if num < min1 {
                min2 = min1
                min1 = num
            } else if num < min2 {
                min2 = num
            }
        }
        return (max1 * max2) - (min1 * min2)
    }
}

Time & Space Complexity

Time complexity: $O(n)$
Space complexity: $O(1)$

Common Pitfalls

Forgetting to Track Both Maximums and Minimums Separately

When updating the two largest values, failing to properly shift max1 to max2 before assigning the new max1 causes the second maximum to be lost. Similarly for minimums. Always save the old value before overwriting.

Using Incorrect Initial Values

Initializing min1 and min2 to 0 instead of infinity (or the maximum possible value) leads to incorrect results when all array elements are positive. Since the problem guarantees positive integers, initialize minimums to a large value like INT_MAX or float('inf').