1913. Maximum Product Difference Between Two - Explanation

Problem Link

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

1. Use four nested loops to select indices a, b, c, d.
2. Skip any iteration where indices overlap.
3. For each valid combination, compute the product difference.
4. 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

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

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

class Solution:
    def maxProductDifference(self, nums: List[int]) -> int:
        nums.sort()
        return nums[-1] * nums[-2] - nums[0] * nums[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

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

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)

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