Largest product made by multiplying any three integers

Given a list of integers, return the largest product that can be made by multiplying any three integers.

For example, if the list is [-10, -10, 5, 2], we should return 500, since that's -10 * -10 * 5.

You can assume the list has at least three integers.

Example:

Input:  arr[]={-10,-10,5,2}
Output: 500

Approach 1: Using Sorting

Result = max(product of maximum three elements, the product of minimum three elements, and one maximum element)

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the maximum product
//of three numbers in the array
//array must contains at least 3 elements
int maximumProduct(int arr[], int n)
{

    sort(arr, arr + n);

    int max1 = arr[n - 1];
    int max2 = arr[n - 2];
    int max3 = arr[n - 3];

    int min1 = arr[0];
    int min2 = arr[1];
    //case 1: maximum=max1*max2*max3
    //case 2: maximum =min1*min2*max1
    return max(min1 * min2 * max1, max1 * max2 * max3);
}

int main()
{
    //array must contains 3 elements
    int arr[] = {-10, -10, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    //i.e (-10)*(-10)*5
    int maximum = maximumProduct(arr, n);
    cout << maximum << "\n";
    return 0;
}

//Time Complexity: O(nlogn)

Approach 2: Efficient

By finding the minimum 2 elements and the maximum 3 elements in the array

Result = max(product of maximum three elements, the product of minimum three elements, and one maximum element)

C++

#include <bits/stdc++.h>
using namespace std;

//function to find the maximum product
//of three numbers in the array
//array must contains at least 3 elements
int maximumProduct(int arr[], int n)
{
    int max1 = INT_MIN, max2 = INT_MIN, max3 = INT_MIN;

    //find the maximum three elements
    for (int i = 0; i < n; i++)
    {

        //update max1,max2 and man3
        if (arr[i] > max1)
        {
            max3 = max(max2, max3);
            max2 = max(max2, max1);
            max1 = arr[i];
        }

        //update max2 and  max3
        else if (arr[i] > max2)
        {
            max3 = max(max2, max3);
            max2 = arr[i];
        }

        //update max3
        else if (arr[i] > max3)
            max3 = arr[i];
    }
    int min1 = INT_MAX, min2 = INT_MAX;

    //find the minimum two elements
    for (int i = 0; i < n; i++)
    {

        //update min1 and min2
        if (arr[i] < min1)
        {
            min2 = min(min1, min2);
            min1 = arr[i];
        }

        //update min2
        else if (arr[i] < min2)
            min2 = arr[i];
    }
    //case 1: maximum=max1*max2*max3
    //case 2: maximum =min1*min2*max1
    return max(min1 * min2 * max1, max1 * max2 * max3);
}

int main()
{
    //array must contains 3 elements
    int arr[] = {-10, -10, 5, 2};
    int n = sizeof(arr) / sizeof(arr[0]);

    //i.e (-10)*(-10)*5
    int maximum = maximumProduct(arr, n);
    cout << maximum << "\n";
    return 0;
}

//Time Complexity: O(n)