Maximum Product of Three Numbers
Difficulty: Medium
Asked in: Amazon
Understanding the Problem
Given an integer array
nums[]
, write a program to find three numbers from the array whose product is maximum and output the result.
Problem Note
 The array contains both +ve and ve numbers.
 The elements on the array can be noncontiguous.
Example 1
Input: nums[] = [5, 7, 4, 2, 1, 9]
Output: 315
Explanation: Max Product of 3 numbers = 5 * 7 * 9 = 315
Example 2
Input: nums[]= [4, 5, 19, 3]
Output: 60
Explanation: Max Product of 3 numbers = 4 * 5 * 3 = 60
Solutions
We will be discussing three different solutions for this problem
 Brute Force Approach: Try to find all the triplets in the array while maintaining the maximum value of their products.
 Using sorting: Sort the input array. The maximum product would be the product of the last three elements or the starting two elements with the last element.
 Single scan: Create 5 variables to maintain the largest, secondlargest, thirdlargest, smallest, and second smallest. The combination of three would be the maximum product.
You may try to solve this problem here Maximum Product of Three Numbers . Learning via problemsolving is the best way to crack any coding interview. So, just visit the link and try to solve using the above methods. If stuck, then you can find the solution below.
1. Brute Force Approach
To find the maximum product of three numbers, we can find all the triplets of the array and multiply them to get the maximum result.
Solution steps

Create a variable
maxProduct
INT_MIN
 Find all the triplets of the array, multiply them and update

maxProduct
max(maxProduct, product(triplet))
Pseudo Code
int maximumProduct(int[] nums) {
n = nums.size
maxProduct = INT_MIN
for(int i = 0 to i < n2) {
for(int j = i + 1 to j < n1) {
for(int k = j + 1 to k < n) {
tripletProduct = nums[i] * nums[j] * nums[k]
maxProduct = max(maxProduct, tripletProduct)
}
}
}
return maxProduct
}
Complexity Analysis
Time Complexity: O(n³)
Space Complexity: O(1)
Critical Ideas to Think

Why did we initialize
maxProduct
INT_MIN
?  Is it necessary to find all the triplets to find the maximum product?
 Can you think of a more optimal approach?
2. Using Sorting
If you will think for a second, you may realize that the maximum product of any three numbers would be the product of the greatest three numbers or the smallest two numbers with the greatest number from the
array.
nums
The reason why the maximum product of any triplet could have two smallest numbers because there could be negative numbers in the
array and the product of the two smallest numbers could be largely positive if the numbers are greater than the 2nd and 3rd largest number of the array.
nums
So if we will sort the array in ascending order, then the largest three numbers will be available at the end of the array. Also, the smallest two numbers will be available at the beginning of the array.
Solution Step

Sort the
nums

Create a
maxProduct
INT_MIN
. 
Update the
maxProduct

max(maxProduct, nums[0]*nums[1]*nums[n1])

max(maxProduct, nums[n1]*nums[n2]*nums[n3])
Pseudo Code
int maximumProduct(int[] nums) {
n = nums.size
maxProduct = INT_MIN
sort(nums)
maxProduct = max(maxProduct, nums[0]*nums[1]*nums[n1))
maxProduct = max(maxProduct, nums[n3]*nums[n2]*nums[n1))
return maxProduct
}
Complexity Analysis
Time Complexity: O(n log n), due to sorting.
Space Complexity: O(log n), Sorting stack space using merge sort or quicksort.
Critical Ideas To Think

Why did we only check for the product of the last three elements for
maxProduct

How can the smallest two values participate for
maxProduct
3. In Single Scan
If you have understood the second approach, then by this time you would have realized that only the three maximum values and two smallest values participate in finding the maximum product of three numbers in the
array.
nums
So, we can find the largest three values and the smallest two values of the array in a single pass of the
array by using five variables.
nums
Solution Step
 Create 5 variables to store the largest three integers and the smallest two integers of the nums array.

Initialize three of them
INT_MIN
that be used to store the maximum three values of the array. 
Initialize the rest two with
INT_MAX
, that can be used to store the minimum two values of the array.  In a single pass, maintain all the five variables such that at the end, they would have stored maximum, 2nd maximum, 3rd maximum, minimum, 2nd minimum.
Pseudo Code
int maximumProduct(int[] nums) {
min1 = INT_MAX
min2 = INT_MAX
max1 = INT_MIN
max2 = INT_MIN
max3 = INT_MIN
for (int i = 0 to i < nums.size) {
if (nums[i] <= min1) {
min2 = min1
min1 = nums[i]
} else if (nums[i] <= min2) { // n lies between min1 and min2
min2 = nums[i]
}
if (nums[i] >= max1) { // n is greater than max1, max2 and max3
max3 = max2
max2 = max1
max1 = nums[i]
} else if (nums[i] >= max2) { // n lies betweeen max1 and max2
max3 = max2
max2 = nums[i]
} else if (nums[i] >= max3) { // n lies betwen max2 and max3
max3 = nums[i]
}
}
return max(min1 * min2 * max1, max1 * max2 * max3)
}
Complexity Analysis
Time Complexity: O(n)
Space Complexity: O(1)
Critical Ideas to Think
 Why did we maintain five variables?
 Can you track that how does the maximum three have been maintained in a single pass?
Comparison of Approaches
Suggested Problems to Solve
 Maximum product of subsequence of size K
 Find Maximum XOR value of a subarray of size K
 Largest triplet product in a stream
 Maximum Product Quadruple in an array
If you have any more approaches or you find an error/bug in the above solutions, please comment down below.
Happy Coding! Enjoy Algorithms!