Given an integer array nums, find three numbers whose product is maximum and return the maximum product.
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
Constraints:
- 3 <= nums.length <= 104
- -1000 <= nums[i] <= 1000
My Solution
This is a tricky problem because we have to deal with negative numbers. The key is realizing that the largest product could only be a toss up between two products. It could either be the product of the two smallest numbers and the largest number or the product of the three largest numbers. Consider you have negative numbers. If you have two or more negative numbers in the array, the smallest two negative numbers will give you the largest product using negative numbers and then we just multiply that by the largest positive number. The other possibility is taking the three largest positive numbers. If there is only one negative number, the largest product obviously cannot include the negative number, so it will be the product of the three largest numbers in the array. If there are no negative numbers, obviously the largest product will be the product of the three largest numbers. Using this intuition, we can just sort the array and then return the maximum product between the two smallest numbers in the array and the largest number, and the three largest numbers.
Time complexity is O(n * log n) because we have to sort the array. Space complexity is O(1), since we only require constant extra space.
class Solution {
public int maximumProduct(int[] nums) {
Arrays.sort(nums);
int n = nums.length;
return Math.max(nums[0]*nums[1]*nums[n-1], nums[n-1]*nums[n-2]*nums[n-3]);
}
}