Leetcode: Maximum Product of Three Numbers

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:

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

Github: code.dennyzhang.com

Credits To: leetcode.com

Leave me comments, if you have better ways to solve.


## Blog link: https://code.dennyzhang.com/maximum-product-of-three-numbers
## Basic Ideas: The biggest number will definitley exists in the target combination.
##              Why? b>c and a>0, then b*a>c*a
##              Let's say (p1, p2, p3) is the target. And the biggest number p4 is not in the combination.
##              1. If there is one positive number inside the target. Let's say p3 is positive. Then p3 must be p4
##                    Otherwise p4*(p1*p2) > p3*(p1*p2)
##              2. If all negative, the max is also negative. Let's say p4 not in the target
##                    p1*p2 > 0 and p4>p3, then p4*(p1*p2) > p3*(p1*p2)
##              3. If there is 0 inside the target. 
##                     If the array has no positive, 0 is the max. p4=0
##                     If the array has only 1 positive, then the array won't have more than 2 negative.
##                                  Otherwise 0 won't be chosen. So the array only have 3 elements. The max will be chosen
##                     If the array has 2 positives. The array won't have more than 2 negative.
##                                  Let's say it has only 0 negative, then the array would be 0 ++. Tha max will be chosen.
##                                  Suppose it has 1 negative, the array would be: - 0 + +
##                                  If we choose: max([1st_min, 2nd_min, 1st_max], [2nd_max, 3rd_max, 1st_max]), 
##                                       we will get the maxmium. 
##                                  This time we don't need to choose the max, but choosing the max will also work.
##                     If the array has 3 positives. 0 won't be chosen. So invalid.
##
##
##              As a conclusion, the max number exists in the target combination.
##
##              Now p3=p4, and the problem drops to choose 2 elements.
##              1. If there are two positive in p1, p2, we can simply choose the next 2 biggest numbers. 
##                                  [2nd_max, 3rd_max]. And they are gurantee to be positive.
##              2. If there are two negative in p1, p2, we should choose the 2 smallest numbers.
##                                  [1st_min, 2nd_min]
##              3. If there are only one neagive and one positive. p3 must be positive. So the result must be negative
##                                Let's say p1<0, p2>0, p3>0. This means the array will only have 2 positive.
##                                So p2 is the next biggest number. 
##                                Then p1 is the biggest negative, so p1 is the 3rd biggest nubmer.
##                                  [2nd_max, 3rd_max]
##              4. If there is 0 in the target. Let's say p3 is 0, it doesn't matter what elements we choose for p1 and p2
##                         Let's say p1 or p2 is 0. Then 0 would be one of these: the 2nd max, or the 3rd max
##                         Why? there would another 2 positive. Then we can get a positive product, instead of 0.
##                         So one of [2nd_max, 3rd_max] is 0. 
##                         If we choose [2nd_max, 3rd_max, 1st_max] as our result, we will get 0. Still the biggest.
##                                   [2nd_max, 3rd_max]
##
##              As a conclusion, [p1, p2] == [1st_min, 2nd_min] or [2nd_max, 3rd_max]
##
##    Watch out: you might have negative or 0  
##
## Complexity: O(n*log(n)), O(1)
class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        length = len(nums)
        if length < 3: return None
        nums.sort()
        return max(nums[-1]*nums[-2]*nums[-3], nums[-1]*nums[0]*nums[1])
linkedin
github
slack

Share It, If You Like It.

Leave a Reply

Your email address will not be published.