# 628. Maximum Product of Three Numbers
Given an integer array, find three numbers whose product is maximum and output the maximum product.
Input: [1,2,3] Output: 6
Input: [1,2,3,4] Output: 24
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.
Approach 1: brute force with
O(N^3), or hashtable with
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)
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++)