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.

Difficulty: introductory

Starter code:

class Solution:
    def maximumProduct(self, nums: List[int]) -> int:
        

Solutions:
class Solution:
     def maximumProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         import heapq
         a, b = heapq.nlargest(3, nums), heapq.nsmallest(2, nums)
         return max(a[0]*a[1]*a[2], a[0]*b[0]*b[1])

class Solution:
     def maximumProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         a, b = heapq.nlargest(3, nums), heapq.nsmallest(2, nums)
         return max(a[0]*a[1]*a[2], a[0]*b[0]*b[1])

class Solution:
     def maximumProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         h, m, l = -float('inf'), -float('inf'), -float('inf')
         lowest, second_lowest = float('inf'), float('inf')
         
         for num in nums:
             if num > h:
                 l = m
                 m = h
                 h= num
             elif num > m:
                 l = m
                 m = num
             elif num > l:
                 l = num
                 
             if num < lowest:
                 second_lowest = lowest
                 lowest = num
             elif num < second_lowest:
                 second_lowest = num
                 
         return max(h*m*l, h*lowest*second_lowest)

class Solution:
     def maximumProduct1(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         #Easy way to do it: sort them, take top 3 product
         #But have to think about negative numbers, lowest
         #2 could be 2 giant negatives.. * biggest positive
         #which could still be biggest product
         
         nums.sort()
         top = nums[~0] * nums[~1] * nums[~2]
         bottom = nums[0] * nums[1] * nums[~0]
         return max(top, bottom)
         #Time O(nlogn) due to sorting
         #Space O(1)
         
     
     def maximumProduct(self, nums):
         #Other approach is keep track of min1/2
         #and max1/2/3 while we iterate through the array
         min1 = min2 = float('inf')
         max1 = max2 = max3 = -float('inf')
         
         for n in nums:
             if n <= min1:
                 min1, min2 = n, min1
             elif n <= min2:
                 min2 = n
             
             if n >= max1:
                 max1, max2, max3 = n, max1, max2
             elif n >= max2:
                 max2, max3 = n, max2
             elif n >= max3:
                 max3 = n
             
         return max(min1*min2*max1, max1*max2*max3)


class Solution:
     def maximumProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max1,max2,max3,min1,min2 = float('-Inf'),float('-Inf'),float('-Inf'),float('Inf'),float('Inf')
         for num in nums:
             if num >= max1:
                 max3,max2,max1 = max2,max1,num
             elif num >= max2:
                 max3,max2 = max2,num
             elif num > max3:
                 max3 = num
             if num <= min1:
                 min2,min1 = min1,num
             elif num < min2:
                 min2 = num
         return max(max1*max2*max3,min1*min2*max1)
         
         


class Solution:
     def maximumProduct(self, nums):
         a = b = c = -1001
         d = e = 1001
         for num in nums:
             if num >= a:
                 c = b
                 b = a
                 a = num
             elif num >= b:
                 c = b
                 b = num
             elif num >= c:
                 c = num
                 
             if num <= d:
                 e = d
                 d = num
             elif num <= e:
                 e = num
         return max(a * b * c, a * d * e)


class Solution:
     def maximumProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max_num = -1000
         s_max = -1000
         t_max = -1000
         min_num = 1000
         s_min = 1000
         
         for i in range(len(nums)):
             if nums[i] > max_num:
                 t_max = s_max
                 s_max = max_num
                 max_num = nums[i]
             elif nums[i] > s_max:
                 t_max = s_max
                 s_max = nums[i]
             elif nums[i] > t_max:
                 t_max = nums[i]
             if nums[i] < min_num:
                 s_min = min_num
                 min_num = nums[i]
             elif nums[i] < s_min:
                 s_min = nums[i]
 
         print (max_num, s_max, t_max, min_num, s_min)
         a = max_num * s_max * t_max  
         b = min_num * s_min * max_num       
         if a > b:
             return(a)
         else:
             return(b)

class Solution:
     def maximumProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         max_num = -1000
         s_max = -1000
         t_max = -1000
         min_num = 1000
         s_min = 1000
         
         for i in range(len(nums)):
             if nums[i] > max_num:
                 t_max = s_max
                 s_max = max_num
                 max_num = nums[i]
             elif nums[i] > s_max:
                 t_max = s_max
                 s_max = nums[i]
             elif nums[i] > t_max:
                 t_max = nums[i]
             if nums[i] < min_num:
                 s_min = min_num
                 min_num = nums[i]
             elif nums[i] < s_min:
                 s_min = nums[i]
 
         print (max_num, s_max, t_max, min_num, s_min)
         a = max_num * s_max * t_max  
         b = min_num * s_min * max_num       
         if a > b:
             return(a)
         else:
             return(b)

class Solution:
     def maximumProduct(self, nums):
         """
         :type nums: List[int]
         :rtype: int
         """
         new=[0 for i in range(2001)]
         for i in range(len(nums)):
             new[1000+nums[i]]=new[1000+nums[i]]+1
         count=0
         product=1
         digit=[]
         for i in range(2000,-1,-1):
             while(new[i]>0):
                 digit.append(i-1000)
                 count=count+1
                 new[i]=new[i]-1
                 if count==3:
                     break
             if count==3:
                 break
         for i in range(2001):
             while(new[i]>0):
                 digit.append(i-1000)
                 count=count+1
                 new[i]=new[i]-1
                 if count==5:
                     break
             if count==5:
                 break
         if len(digit)==3:
             return digit[0]*digit[1]*digit[2]
         elif len(digit)==4:
             return max(digit[0]*digit[1]*digit[2],digit[3]*digit[1]*digit[2])
         else:
             p1=digit[0]*digit[3]*digit[4]
             p2=digit[0]*digit[1]*digit[2]
             return max(p1,p2)