Problem Description

You are given an integer array nums. Your task is to find three numbers in the array whose product gives the maximum possible value, and return that maximum product.

The problem asks you to select any three numbers from the array (not necessarily consecutive) and multiply them together. Among all possible combinations of three numbers, you need to find the combination that produces the largest product.

For example:

• If nums = [1, 2, 3], the maximum product would be 1 × 2 × 3 = 6
• If nums = [1, 2, 3, 4], the maximum product would be 2 × 3 × 4 = 24
• If nums = [-1, -2, -3], the maximum product would be -1 × -2 × -3 = -6

The key insight is that the maximum product doesn't always come from the three largest numbers. When negative numbers are present, multiplying two negative numbers gives a positive result, which could potentially create a larger product when combined with a large positive number.

The solution sorts the array first, then considers two scenarios:

1. The product of the three largest numbers: nums[n-1] × nums[n-2] × nums[n-3]
2. The product of the two smallest numbers (which might be negative) and the largest number: nums[0] × nums[1] × nums[n-1]

The maximum of these two products gives the answer, covering all cases whether the array contains all positive numbers, all negative numbers, or a mix of both.

Intuition

To find the maximum product of three numbers, let's think about what makes a product large. A product becomes large when we multiply large positive numbers together. The straightforward approach would be to pick the three largest numbers in the array.

However, there's a catch when negative numbers are involved. Remember that multiplying two negative numbers gives a positive result. If we have two very large negative numbers (like -100 and -99), their product becomes a large positive number (9900). When we multiply this with the largest positive number in the array, we might get a product larger than just using the three largest positive numbers.

Let's visualize this with an example: if nums = [-100, -99, 1, 2, 3], we have two choices:

• Three largest numbers: 1 × 2 × 3 = 6
• Two smallest (most negative) and one largest: (-100) × (-99) × 3 = 29700

Clearly, the second option gives us a much larger product!

After sorting the array, we know:

• The largest numbers are at the end: nums[n-1], nums[n-2], nums[n-3]
• The smallest (most negative) numbers are at the beginning: nums[0], nums[1]

This leads us to realize we only need to check two possibilities:

1. The product of the three largest numbers (all at the end of the sorted array)
2. The product of the two smallest numbers and the largest number (two from the beginning, one from the end)

We don't need to check other combinations because:

• Using just one negative number would give a negative product
• Using three or more negative numbers either gives a negative product or a smaller positive product than our two cases
• Any other combination of indices would involve smaller magnitude numbers, resulting in a smaller product

Therefore, the maximum of these two products will always give us the answer.

Learn more about Math and Sorting patterns.

Solution Approach

The implementation follows a sorting-based approach with case analysis:

Step 1: Sort the Array

First, we sort the array in ascending order using nums.sort(). After sorting, we have:

• Smallest (most negative) values at the beginning: nums[0], nums[1], ...
• Largest values at the end: ..., nums[n-2], nums[n-1]

Step 2: Calculate Two Possible Products

Based on our analysis, we need to consider two scenarios:

1. Product of three largest numbers: a = nums[-1] × nums[-2] × nums[-3]

   • This handles cases where all numbers are positive or when the three largest positive numbers give the maximum product
   • Using negative indexing in Python: -1 is the last element, -2 is second to last, -3 is third to last

2. Product of two smallest and one largest: b = nums[-1] × nums[0] × nums[1]

   • This handles cases where two large negative numbers multiplied together (giving a large positive) and then multiplied by the largest positive number yields the maximum
   • nums[0] and nums[1] are the two smallest values (potentially large negative numbers)
   • nums[-1] is the largest value in the array

Step 3: Return the Maximum

Finally, we return max(a, b) to get the maximum product among the two possibilities.

Time and Space Complexity:

• Time Complexity: O(n log n) due to sorting, where n is the length of the array
• Space Complexity: O(1) if we don't count the space used by the sorting algorithm (in-place sorting), or O(log n) for the sorting recursion stack

This solution elegantly handles all edge cases:

• All positive numbers: a will be the maximum
• All negative numbers: a will be the maximum (product of three negatives)
• Mixed positive and negative: The maximum of a and b covers both possibilities

Example Walkthrough

Let's walk through the solution with the array nums = [-4, -3, -2, 1, 5].

Step 1: Sort the array After sorting: nums = [-4, -3, -2, 1, 5]

• Smallest values (most negative): -4, -3 at positions 0 and 1
• Largest values: 1, 5 at positions 3 and 4

Step 2: Calculate both possible products

Option A - Three largest numbers:

• We take the three rightmost elements: -2, 1, 5
• Product: (-2) × 1 × 5 = -10

Option B - Two smallest and one largest:

• We take the two leftmost elements and the rightmost: -4, -3, 5
• Product: (-4) × (-3) × 5 = 12 × 5 = 60

Step 3: Return the maximum

• Compare: max(-10, 60) = 60
• Return 60

Notice how the two negative numbers -4 and -3 multiply to give positive 12, which when combined with the largest number 5 gives us 60. This is much larger than using the three "largest" numbers which included a negative value, resulting in a negative product.

Let's verify with another example where all numbers are positive: nums = [1, 2, 3, 4]

After sorting: nums = [1, 2, 3, 4]

Option A: 2 × 3 × 4 = 24 Option B: 1 × 2 × 4 = 8

Maximum: max(24, 8) = 24

In this case, the three largest numbers give the maximum product, as expected when all values are positive.

Solution Implementation

Time and Space Complexity

The time complexity is O(n × log n), where n is the length of the array nums. This is because the code uses Python's built-in sort() method, which implements Timsort algorithm with a worst-case time complexity of O(n × log n).

The space complexity is O(log n). While the sorting is done in-place (modifying the original list), Python's Timsort algorithm requires O(log n) space for the recursion stack and temporary storage during the merge operations. This auxiliary space is needed to maintain the recursive calls and perform the merging steps in the hybrid sorting algorithm.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Assuming Three Largest Numbers Always Give Maximum Product

A natural instinct is to simply pick the three largest numbers from the array, but this fails when negative numbers are present.

Incorrect Approach:

def maximumProduct(self, nums: List[int]) -> int:
    nums.sort()
    # Wrong: Only considering three largest numbers
    return nums[-1] * nums[-2] * nums[-3]

Why it fails: For nums = [-100, -99, 1, 2, 3], this would return 1 × 2 × 3 = 6, but the correct answer is (-100) × (-99) × 3 = 29,700.

2. Not Handling Arrays with All Negative Numbers

Some might think we need special handling for arrays containing only negative numbers.

Overcomplicated Approach:

def maximumProduct(self, nums: List[int]) -> int:
    nums.sort()
    # Unnecessary: Checking if all numbers are negative
    if nums[-1] < 0:
        # Special case for all negatives
        return nums[-1] * nums[-2] * nums[-3]
    else:
        # Regular case
        return max(nums[-1] * nums[-2] * nums[-3], 
                   nums[0] * nums[1] * nums[-1])

Why it's unnecessary: The original solution already handles this case correctly. When all numbers are negative, nums[-1] is still negative, so nums[0] * nums[1] * nums[-1] would give a negative product (two negatives × one negative), while nums[-1] * nums[-2] * nums[-3] gives the least negative (maximum) product.

3. Using O(n³) Brute Force Without Optimization

Checking all possible triplets without thinking about the mathematical properties.

Inefficient Approach:

def maximumProduct(self, nums: List[int]) -> int:
    n = len(nums)
    max_product = float('-inf')
    # O(n³) time complexity - very inefficient
    for i in range(n):
        for j in range(i+1, n):
            for k in range(j+1, n):
                max_product = max(max_product, nums[i] * nums[j] * nums[k])
    return max_product

Solution: Recognize that after sorting, the maximum product must come from either the three largest values or two smallest (potentially negative) values with the largest value. This reduces the problem to O(n log n) time complexity.

4. Forgetting Edge Cases in Linear Time Solution

Attempting to optimize to O(n) by finding the required values in a single pass but missing edge cases.

Incomplete Linear Approach:

def maximumProduct(self, nums: List[int]) -> int:
    # Finding max3, max2, max1 and min2, min1 in single pass
    max1 = max2 = max3 = float('-inf')
    min1 = min2 = float('inf')
  
    for num in nums:
        # Bug: Order of updates matters!
        if num > max1:
            max3 = max2
            max2 = max1
            max1 = num
        elif num > max2:
            max3 = max2
            max2 = num
        elif num > max3:
            max3 = num
          
        # Similar logic for minimums...

Common mistakes in this approach:

• Not handling the cascade updates correctly when finding top 3 maximum and top 2 minimum values
• Edge cases when array has duplicate values
• Initialization values can cause issues with arrays containing very large negative numbers

Correct Linear Solution:

def maximumProduct(self, nums: List[int]) -> int:
    # Properly track the required values
    max1 = max2 = max3 = float('-inf')
    min1 = min2 = float('inf')
  
    for num in nums:
        # Update maximums (order matters!)
        if num > max1:
            max3, max2, max1 = max2, 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)

The sorting approach in the original solution is cleaner and less error-prone, making it a better choice unless the O(n) time complexity is absolutely necessary.