1913. Maximum Product Difference Between Two - Explanation

1. Brute Force

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

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

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