Maximum Product Difference Between Two Pairs

How it works

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.

Steps

1. Initialize max1, max2 to 0 (or the smallest possible values) and min1, min2 to infinity (or the largest possible values).
2. 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.
3. Return (max1 * max2) - (min1 * min2).

Complexity

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

Things to watch for

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').

from typing import List

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)

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);
    }
};