Formatted question description: https://leetcode.ca/all/628.html

628. Maximum Product of Three Numbers (Easy)

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.

 

Related Topics:
Array, Math

Similar Questions:

Solution 1.

// OJ: https://leetcode.com/problems/maximum-product-of-three-numbers/
// Time: O(NlogN)
// Space: O(1)
class Solution {
public:
    int maximumProduct(vector<int>& A) {
        sort(begin(A), end(A));
        return A.back() * max(A[A.size() - 2] * A[A.size() - 3], A[0] * A[1]);
    }
};

Solution 2.

// OJ: https://leetcode.com/problems/maximum-product-of-three-numbers/
// Time: O(N)
// Space: O(1)
class Solution {
public:
    int maximumProduct(vector<int>& A) {
        vector<int> maxVals(3, INT_MIN), minVals(2, INT_MAX);
        for (int n : A) {
            for (int i = 0; i < 3; ++i) {
                if (n <= maxVals[i]) continue;
                for (int j = 2; j > i; --j) maxVals[j] = maxVals[j - 1];
                maxVals[i] = n;
                break;
            }
            for (int i = 0; i < 2; ++i) {
                if (n >= minVals[i]) continue;
                for (int j = 1; j > i; --j) minVals[j] = minVals[j - 1];
                minVals[i] = n;
                break;
            }
        }
        return maxVals[0] * max(maxVals[1] * maxVals[2], minVals[0] * minVals[1]);
    }
};

Java

  • class Solution {
        public int maximumProduct(int[] nums) {
            int length = nums.length;
            Integer[] array = new Integer[length];
            for (int i = 0; i < length; i++)
                array[i] = nums[i];
            Arrays.sort(array, new Comparator<Integer>() {
                public int compare(Integer num1, Integer num2) {
                    if (Math.abs(num1) != Math.abs(num2))
                        return Math.abs(num2) - Math.abs(num1);
                    else
                        return num2 - num1;
                }
            });
            List<Integer> zeroList = new ArrayList<Integer>();
            List<Integer> positiveList = new ArrayList<Integer>();
            List<Integer> negativeList = new ArrayList<Integer>();
            for (int i = 0; i < length; i++) {
                int num = array[i];
                if (num > 0)
                    positiveList.add(num);
                else if (num < 0)
                    negativeList.add(num);
                else
                    zeroList.add(num);
            }
            int zeroCount = zeroList.size(), positiveCount = positiveList.size(), negativeCount = negativeList.size();
            if (negativeCount == 0) {
                if (positiveCount >= 3)
                    return positiveList.get(0) * positiveList.get(1) * positiveList.get(2);
                else
                    return 0;
            } else if (negativeCount == 1) {
                if (positiveCount >= 3)
                    return positiveList.get(0) * positiveList.get(1) * positiveList.get(2);
                else {
                    if (zeroCount > 0)
                        return 0;
                    else if (positiveCount >= 2)
                        return positiveList.get(positiveCount - 1) * positiveList.get(positiveCount - 2) * negativeList.get(negativeCount - 1);
                    else
                        return 0;
                }
            } else {
                int max = 0;
                if (positiveCount >= 3)
                    max = Math.max(max, positiveList.get(0) * positiveList.get(1) * positiveList.get(2));
                if (positiveCount >= 1) {
                    max = Math.max(max, positiveList.get(0) * negativeList.get(0) * negativeList.get(1));
                } else {
                    if (zeroCount > 0)
                        return 0;
                    else
                        return negativeList.get(negativeCount - 1) * negativeList.get(negativeCount - 2) * negativeList.get(negativeCount - 3);
                }
                return max;
            }
        }
    }
    
  • // OJ: https://leetcode.com/problems/maximum-product-of-three-numbers/
    // Time: O(NlogN)
    // Space: O(1)
    class Solution {
    public:
        int maximumProduct(vector<int>& A) {
            sort(begin(A), end(A));
            return A.back() * max(A[A.size() - 2] * A[A.size() - 3], A[0] * A[1]);
        }
    };
    
  • class Solution(object):
      def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        nums.sort()
        return max(nums[0] * nums[1] * nums[-1], nums[-1] * nums[-2] * nums[-3])
    
    

All Problems

All Solutions