Maximum Product of Three Numbers

• LeetCode: Maximum Product of Three Numbers

• Problem:

Given an integer array, find three numbers whose product is maximum and output the maximum product.

• Note:

1. The length of the given array will be in range [3,10^4] 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.

• Examples:

Input: [1,2,3]
Output: 6

Input: [1,2,3,4]
Output: 24

• Analysis:

The maximum product of three numbers of a array are two cases.

Case1. 

      nums[+, +, ....., -] or [-, -, ......., -] => nums[len - 1] * nums[len - 2] * nums[len 3]

Case2.

      nums[-, -, ......., +] => nums[0] * nums[1] * nums[len - 1]

Solution1.

      Stored the first, second, and third max number.

      Stored the first, and second min number.

      Then, Max(case1, case2)

Solution2.

      Sorted array and max(case1, case2)

• Solution 1

• Code - Java:

class Solution {
    public int maximumProduct(int[] nums) {
        int m =  nums.length;
        int first_Max = Integer.MIN_VALUE;
        int second_Max = Integer.MIN_VALUE;
        int third_Max = Integer.MIN_VALUE;
        int first_min = Integer.MAX_VALUE;
        int second_min = Integer.MAX_VALUE;
        for (int i = 0; i < m; i++) {
            if (nums[i] > first_Max) {
                third_Max = second_Max;
                second_Max = first_Max;
                first_Max = nums[i];
            } else if (nums[i] > second_Max) {
                third_Max = second_Max;
                second_Max = nums[i];
            } else if (nums[i] > third_Max) {
                third_Max = nums[i];
            }

            if (nums[i] < first_min) {
                second_min = first_min;
                first_min = nums[i];
            } else if (nums[i] < second_min) {
                second_min = nums[i];
            }
        }
        return Math.max(first_Max * second_Max * third_Max, first_min * second_min * first_Max);
    }
}

• Code - C++:

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int m =  nums.size();
        int first_Max = INT_MIN;
        int second_Max = INT_MIN;
        int third_Max = INT_MIN;
        int first_min = INT_MAX;
        int second_min = INT_MAX;
        for (int i = 0; i < m; i++) {
            if (nums[i] > first_Max) {
                third_Max = second_Max;
                second_Max = first_Max;
                first_Max = nums[i];
            } else if (nums[i] > second_Max) {
                third_Max = second_Max;
                second_Max = nums[i];
            } else if (nums[i] > third_Max) {
                third_Max = nums[i];
            }

            if (nums[i] < first_min) {
                second_min = first_min;
                first_min = nums[i];
            } else if (nums[i] < second_min) {
                second_min = nums[i];
            }
        }
        return max(first_Max * second_Max * third_Max, first_min * second_min * first_Max);
    }
};

• Code - Python:

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        INT_MAX = 2 ** 31 - 1
        INT_MIN = (-1) * 2 ** 31
        m =  len(nums)
        first_Max = INT_MIN;
        second_Max = INT_MIN;
        third_Max = INT_MIN;
        first_min = INT_MAX;
        second_min = INT_MAX;

        for i in range (m):
            if nums[i] > first_Max:
                third_Max = second_Max;
                second_Max = first_Max
                first_Max = nums[i];
            elif nums[i] > second_Max:
                third_Max = second_Max
                second_Max = nums[i];
            elif nums[i] > third_Max:
                third_Max = nums[i]
            if nums[i] < first_min:
                second_min = first_min
                first_min = nums[i];
            elif nums[i] < second_min:
                second_min = nums[i]
        return max(first_Max * second_Max * third_Max, first_min * second_min * first_Max)

• Solution 2.

• Code - Java:

class Solution {
    public int maximumProduct(int[] nums) {
        int m =  nums.length;
        Arrays.sort(nums);
        return Math.max(nums[m - 1] * nums[m - 2] * nums[m - 3], nums[m - 1] * nums[0] * nums[1]);
    }
}

• Code - C++:

class Solution {
public:
    int maximumProduct(vector<int>& nums) {
        int m =  nums.size();
        sort(nums.begin(), nums.end());
        return max(nums[m - 1] * nums[m - 2] * nums[m - 3], nums[m - 1] * nums[0] * nums[1]);
    }
};

• Code - Python:

class Solution(object):
    def maximumProduct(self, nums):
        """
        :type nums: List[int]
        :rtype: int
        """
        m = len(nums)
        nums = sorted(nums)
        return max(nums[m - 1] * nums[m - 2] * nums[m - 3], nums[m - 1] * nums[0] * nums[1])

• Solution 1.

• Time Complexity: O(N), N is the length of input array

• Space Complexity: O(1)

• Solution 2.

• Time Complexity: O(NLOGN), N is the length of input array