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;
        }
    }
}

All Problems

All Solutions