# Compute the Maximum Product of Three Numbers in an Array

Given an array of integers – find out the maximum product of the tree numbers in the array. For example, [1, 2, 3] output: [6] and [1, 2, 4, 3], output 24. We can easily write a O(n^3) algorithm that loops over three numbers and find the maximum product, however it is slow.

### Sorting

If we sort the array with the complexity O(nlogn) – we know the minimal two numbers and maximum three numbers in the array. So the answer would be the maximum between min1*min2*max1 or max3*max2*max1.

 ```1 2 3 4 5 6 7 8 ``` ```class Solution { public:     int maximumProduct(vector& nums) {         sort(nums.begin(), nums.end());         int sz = nums.size();         return max(nums[0] * nums[1] * nums[sz - 1], nums[sz - 1] * nums[sz - 2] * nums[sz - 3]);         } };```
```class Solution {
public:
int maximumProduct(vector<int>& nums) {
sort(nums.begin(), nums.end());
int sz = nums.size();
return max(nums[0] * nums[1] * nums[sz - 1], nums[sz - 1] * nums[sz - 2] * nums[sz - 3]);
}
};```

### Single Scan

We can iterative the array once and keep tracking the min1, min2, max1, max2 and max3.

 ```1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 ``` ```class Solution { public:     int maximumProduct(vector& nums) {         int min1 = INT_MAX, min2 = INT_MAX;         int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;         for (int n: nums) {             if (n <= min1) {                 min2 = min1;                 min1 = n;             } else if (n <= min2) {     // n lies between min1 and min2                 min2 = n;             }             if (n >= max1) {            // n is greater than max1, max2 and max3                 max3 = max2;                 max2 = max1;                 max1 = n;             } else if (n >= max2) {     // n lies betweeen max1 and max2                 max3 = max2;                 max2 = n;             } else if (n >= max3) {     // n lies betwen max2 and max3                 max3 = n;             }         }         return max(min1 * min2 * max1, max1 * max2 * max3);             } };```
```class Solution {
public:
int maximumProduct(vector<int>& nums) {
int min1 = INT_MAX, min2 = INT_MAX;
int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;
for (int n: nums) {
if (n <= min1) {
min2 = min1;
min1 = n;
} else if (n <= min2) {     // n lies between min1 and min2
min2 = n;
}
if (n >= max1) {            // n is greater than max1, max2 and max3
max3 = max2;
max2 = max1;
max1 = n;
} else if (n >= max2) {     // n lies betweeen max1 and max2
max3 = max2;
max2 = n;
} else if (n >= max3) {     // n lies betwen max2 and max3
max3 = n;
}
}
return max(min1 * min2 * max1, max1 * max2 * max3);
}
};```

Max product of either two numbers or three numbers:

GD Star Rating