628. Maximum Product of Three Numbers

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

Example 1:

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

Example 2:

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

Note:

The length of the given array will be in range [3,104] and all elements are in the range [-1000, 1000].
Multiplication of any three numbers in the input won't exceed the range of 32-bit signed integer.

Solution

Approach 1: brute force with O(N^3), or hashtable with O(N^2).

Approach 2: note that the largest product should come from either 2 negative + 1 positive, or 3 positives/largests, therefore keep 3 largests and 2 smallests.

Code (Python)

Approach 2:

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        # either 2 negative + 1 positive, or 3 positives/largests
        first_largest, second_largest, third_largest = - float('inf'), - float('inf'), - float('inf')
        first_smallest, second_smallest = float('inf'), float('inf')
        for num in nums:
            if num >= first_largest:
                third_largest = second_largest
                second_largest = first_largest
                first_largest = num
            elif num >= second_largest:
                third_largest = second_largest
                second_largest = num
            elif num > third_largest:
                third_largest = num
            if num <= first_smallest:
                second_smallest = first_smallest
                first_smallest = num
            elif num < second_smallest:
                second_smallest = num
        return max(first_largest * second_largest * third_largest, first_smallest * second_smallest * first_largest)

Code (C++)

Approach 1:

Approach 2: