Maximum Product of Three Numbers

Difficulty: Easy | Acceptance: 45.90% | Paid: No Topics: Array, Math, Sorting

Given an integer array nums, find three numbers whose product is maximum and return the maximum product.

• Examples
• Constraints
• Approach 1: Brute Force
• Approach 2: Sorting
• Approach 3: Single Pass (Linear Scan)

Examples

Example 1:

Input: nums = [1,2,3]
Output: 6

Example 2:

Input: nums = [1,2,3,4]
Output: 24

Example 3:

Input: nums = [-1,-2,-3]
Output: -6

Constraints

3 <= nums.length <= 10⁴
-1000 <= nums[i] <= 1000

Approach 1: Brute Force

Intuition The most straightforward way to find the maximum product is to calculate the product of every possible triplet of numbers in the array and keep track of the maximum value found.

Steps

• Initialize a variable maxProduct to a very small number (e.g., negative infinity).
• Use three nested loops to iterate through all possible combinations of three distinct indices i, j, and k in the array.
• Calculate the product of the elements at these indices.
• Update maxProduct if the current product is greater.
• Return maxProduct after all iterations.

from typing import List

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        n = len(nums)
        max_prod = -float('inf')
        for i in range(n):
            for j in range(i + 1, n):
                for k in range(j + 1, n):
                    current_prod = nums[i] * nums[j] * nums[k]
                    if current_prod > max_prod:
                        max_prod = current_prod
        return max_prod

Complexity

• Time: O(n³) - We use three nested loops to traverse the array.
• Space: O(1) - We only use a few extra variables.
• Notes: This approach is inefficient for large arrays and will likely result in a Time Limit Exceeded error on LeetCode.

Approach 2: Sorting

Intuition If we sort the array, the largest numbers will be at the end. However, if there are negative numbers, the product of two large negative numbers (which become positive) multiplied by the largest positive number could yield the maximum product. Thus, the answer is either the product of the three largest numbers or the product of the two smallest (most negative) numbers and the largest number.

Steps

• Sort the array in ascending order.
• Calculate product1 as the product of the last three elements (the three largest numbers).
• Calculate product2 as the product of the first two elements (two smallest numbers) and the last element (largest number).
• Return the maximum of product1 and product2.

from typing import List

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        nums.sort()
        n = len(nums)
        # The maximum product is either the product of the three largest numbers
        # or the product of the two smallest (negative) numbers and the largest number.
        return max(nums[n-1] * nums[n-2] * nums[n-3], nums[0] * nums[1] * nums[n-1])

Complexity

• Time: O(n log n) - Sorting the array dominates the time complexity.
• Space: O(1) or O(n) - Depending on the sorting algorithm used (e.g., heapsort uses O(1), Timsort uses O(n)).
• Notes: This is a clean solution but sorting is not strictly necessary since we only need a few specific values.

Approach 3: Single Pass (Linear Scan)

Intuition We can find the required values without sorting the entire array. We simply need to track the three largest numbers (max1, max2, max3) and the two smallest numbers (min1, min2) as we iterate through the array once.

Steps

• Initialize max1, max2, max3 to negative infinity (or the smallest possible integer).
• Initialize min1, min2 to positive infinity (or the largest possible integer).
• Iterate through each number num in the array:
  • Update the maximums: If num is greater than max1, shift values down (max3 = max2, max2 = max1, max1 = num). Else if num is greater than max2, shift max3 = max2, max2 = num. Else if num is greater than max3, max3 = num.
  • Update the minimums: If num is smaller than min1, shift min2 = min1, min1 = num. Else if num is smaller than min2, min2 = num.
• The result is the maximum of (max1 * max2 * max3) and (max1 * min1 * min2).

from typing import List

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        # Initialize maxs to -infinity and mins to +infinity
        max1 = max2 = max3 = -float('inf')
        min1 = min2 = float('inf')
        
        for num in nums:
            # Update maximums
            if num > max1:
                max3 = max2
                max2 = max1
                max1 = num
            elif num > max2:
                max3 = max2
                max2 = num
            elif num > max3:
                max3 = num
            
            # Update minimums
            if num < min1:
                min2 = min1
                min1 = num
            elif num < min2:
                min2 = num
                
        return max(max1 * max2 * max3, max1 * min1 * min2)

Complexity

• Time: O(n) - We traverse the array exactly once.
• Space: O(1) - We only use a constant amount of extra space for variables.
• Notes: This is the optimal solution for this problem, offering the best time complexity without the overhead of sorting.