Table of Contents
Problem Statement
Maximum Product of Three Numbers LeetCode Solution – We are given an array, the question asks us to calculate the maximum product of any 3 numbers.
Examples
Example 1:
Input: nums = [1,2,3] Output: 6
Example 2:
Input: nums = [1,2,3,4] Output: 24
Example 3:
Input: nums = [-1,-2,-3] Output: -6
Approach
If all the numbers are greater than 0, then the maximum product of 3 numbers will obviously be the product of the largest 3 numbers. The problem arises in the case of negative numbers.
Let us observe some cases first and then think about the solution. For these cases, let us assume the nums sorted in non-decreasing order.
Case 1:
nums = [2, 3, 4, 7, 9, 100]
output = 7 *9 *100
Explanation: 3 max numbers are 100, 9 & 7
Case 2:
nums = [-13, -12, -1, 0, 1, 3, 14, 16, 17]
output = 14 *16 *17
Explanation: 3 max numbers are 17, 16 & 14
Case 3:
nums = [-13, -12, -11, -1, 0, 2, 3, 4, 5]
output = -13*(-12)*5
Explanation: even though the max numbers 3, 4 & 5, we can generate a much larger positive product from two negative numbers, in this case (-13)(-12) > 4 *5. After including the 2 negative numbers, we can not include any negative numbers as it will make the product negative hence small. Therefore, we have to include the 3rd number as the largest positive only.
In a sorted array, the maximum product will be either the last three largest elements or the first two (negative elements) multiplied by the last (largest) element.
Code
C++ code for Maximum Product of Three Numbers
class Solution {
public:
int maximumProduct(vector<int>& nums) {
int n = nums.size();
sort(nums.begin(), nums.end());
if(nums[n-1] <= 0) {
return nums[n-1]*nums[n-2]*nums[n-3];
}
int res = nums[n-1];
if(nums[0]*nums[1] >= nums[n-2]*nums[n-3]) {
res *= nums[0]*nums[1];
}
else {
res *= nums[n-2]*nums[n-3];
}
return res;
}
};Java code for Maximum Product of Three Numbers
public class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int option1 = nums[0] * nums[1] * nums[nums.length - 1];
int option2 = nums[nums.length - 1] * nums[nums.length - 2] * nums[nums.length - 3];
return Math.max(option1, option2);
}
}Complexity Analysis for Maximum Product of Three Numbers LeetCode Solution
- Time complexity: O(N log N)
- Sorting the nums array takes (N * log N) time.
- Space complexity: O(1)
- No extra space is required
Reference: https://en.wikipedia.org/wiki/Array_data_structure