## Maximum Product of Three Numbers Difficulty: Medium

#### 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 non-contiguous.

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

1. Brute Force Approach: Try to find all the triplets in the array while maintaining the maximum value of their products.
2. 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.
3. Single scan: Create 5 variables to maintain the largest, second-largest, third-largest, 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 problem-solving 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

1. Create a variable `maxProduct `and initialize it with `INT_MIN`
2. Find all the triplets of the array, multiply them and update
• `maxProduct `with `max(maxProduct, product(triplet))`

Pseudo Code

``````int maximumProduct(int[] nums) {
n = nums.size
maxProduct = INT_MIN
for(int i = 0 to i < n-2) {
for(int j = i + 1 to j < n-1) {
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 `with `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 `nums` array.

The reason why the maximum product of any triplet could have two smallest numbers because there could be negative numbers in the `nums` 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.

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

1. Sort the `nums` array in ascending order
2. Create a `maxProduct` variable and initialize it with `INT_MIN`.
3. Update the `maxProduct` with
• `max(maxProduct, nums*nums*nums[n-1])`
• `max(maxProduct, nums[n-1]*nums[n-2]*nums[n-3])`

Pseudo Code

``````int maximumProduct(int[] nums) {
n = nums.size
maxProduct = INT_MIN
sort(nums)
maxProduct = max(maxProduct, nums*nums*nums[n-1))
maxProduct = max(maxProduct, nums[n-3]*nums[n-2]*nums[n-1))
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`?(comment down below)

#### 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 `nums` array.

So, we can find the largest three values and the smallest two values of the array in a single pass of the `nums` array by using five variables.

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 sub-array 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!