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.

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.

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:

• Teaching Kids Programming – Max Product of Two Numbers
• Teaching Kids Programming – Compute the Max Product of 3 Numbers in the Array
• Compute the Maximum Product of Three Numbers in an Array
• Algorithm to Compute the Largest Triple Products from Array

–EOF (The Ultimate Computing & Technology Blog) —