Maximum Product of Three Numbers

January 19, 2024

Problem #

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

Example:

1. Input: nums = [-1, -2, -3, 4] Output: 24 Explanation: The maximum product is obtained by multiplying -3 * -2 * 4 = 24.

Solution Approach #

The solution involves finding the three largest numbers and the two smallest numbers in the array. The maximum product can be obtained either by multiplying the three largest numbers or by multiplying the two smallest numbers (which could be negative and thus make a positive product when multiplied together) with the largest number.

Algorithm Steps #

1. Initialize three variables to track the largest, second-largest, and third-largest numbers. Also, initialize two variables to track the smallest and second smallest numbers.
2. Iterate through the array, updating these five variables as necessary.
3. The maximum product can be either the product of the top three largest numbers or the product of the largest number and the two smallest numbers.
4. Return the maximum of these two products.

Code (Python) #

def maximumProduct(nums):
    max1 = max2 = max3 = float('-inf')
    min1 = min2 = float('inf')

    for n in nums:
        if n > max1:
            max3 = max2
            max2 = max1
            max1 = n
        elif n > max2:
            max3 = max2
            max2 = n
        elif n > max3:
            max3 = n

        if n < min1:
            min2 = min1
            min1 = n
        elif n < min2:
            min2 = n

    return max(max1 * max2 * max3, max1 * min1 * min2)

# Test the function
print(maximumProduct([-1, -2, -3, 4]))  # Output: 24

Time Complexity #

O(n), where n is the number of elements in the array. The array is traversed once.

Space Complexity #

O(1), as the solution uses a constant amount of space.