# 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: