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:
The simplest solution is to consider every triplet out of the given array and check their product and find out the maximum product out of them.
Complexity Analysis
Time complexity : . We need to consider every triplet from array of length .
Space complexity : . Constant extra space is used.
Algorithm
Another solution could be to sort the given array(in ascending order) and find out the product of the last three numbers.
But, we can note that this product will be maximum only if all the numbers in array are positive. But, in the given problem statement, negative elements could exist as well.
Thus, it could also be possible that two negative numbers lying at the left extreme end could also contribute to lead to a larger product if the third number in the triplet being considered is the largest positive number in the array.
Thus, either the product xx or xx will give the required result. Thus, we need to find the larger one from out of these values.
Complexity Analysis
Time complexity : . Sorting the array takes time.
Space complexity : . Sorting takes O(logn) space.
Algorithm
We need not necessarily sort the given array to find the maximum product. Instead, we can only find the required 2 smallest values( and ) and the three largest values() in the array, by iterating over the array only once.
At the end, again we can find out the larger value out of xx and xx to find the required maximum product.
Complexity Analysis
Time complexity : . Only one iteration over the array of length is required.
Space complexity : . Constant extra space is used.
Analysis written by: @vinod23