Maximum Product of Three Numbers

DevSniper
Published : 30 July 2024

118 Views

Integer Array Coding Problems DSA Challange

Given an integer array arr, find maximum product of three numbers.

Example 1 :-

[2 6,7,8,9,2,10]

Output : 720

Example 2 :-

[2 6,7,8,-9,2,10]

Output : 560

Example : -

[2 6,-7,8,-9,2,10]

Output : 630

Constraints :

3 <= arr.length <= 10^4
-1000 <= arr[i] <= 1000

Brute Force (Naive) Approach

The brute force approach involves using nested loops to check every possible combination of three numbers from the array, and for each combination, calculate the product and keep track of the max product of the array.

Steps :

Create a variable maxProduct to keep track of the maximum product of three numbers
Iterate over loop to get every possible combinations.
Calculate the product for each combination.
if product is greater than maximum product reset maximum product with product.
At the end of iterations maximum product will contains maximum product of three numbers.

C++

Java

Python

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

int maximumProduct(int arr[],int n)
{
    int maxProduct=INT_MIN;
    for(int i=0; i<n; i++) {
        for(int j=i+1; j<n; j++) {
            for(int k=j+1; k<n; k++) {
                if(arr[i]*arr[j]*arr[k]>maxProduct) {
                    maxProduct=arr[i]*arr[j]*arr[k];
                }
            }
        }
    }
    return maxProduct;
}
int main()
{
    int arr[] = {2,6,-7,8,-9,2,10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<maximumProduct(arr,n)<<endl;
    return 0;
}

Time Complexity : O(N^3)

Space Complexity : O(1)

Using Sorting

By sorting the array, We can easily identify the potential elements that could give the maximum product without evaluating every possible combination.

For array with all positive numbers, the product of the three largest numbers will be our answer. As we know that multiplying two negative numbers gives a positive result so If the array has negative numbers, we should also consider the product of the two smallest negative numbers(highest in magnitude) with the largest positive number. Therefore, the final answer will be the maximum of the product of the three largest numbers and the product of the two smallest negatives and the largest positive number.

Steps :

Sort the array in ascending order.
Calculate Product of the Three Largest Numbers.
Calculate Product of Two Smallest and One Largest Number.
The maximum product will be the highest value of above two products.

C++

Java

Python

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

int maximumProduct(int arr[],int n)
{
    sort(arr,arr+n);
    return max(arr[n-1]*arr[n-2]*arr[n-3] , arr[0]*arr[1]*arr[n-1]);
}
int main()
{
    int arr[] = {2,6,-7,8,-9,2,10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<maximumProduct(arr,n)<<endl;
    return 0;
}

Time Complexity : O(NlogN)

Space Complexity : O(1)

Optimal Solution O(N)

In the above approach, we can see that only five elements are critical for finding the maximum product of three numbers, the three largest and the two smallest numbers in the array. focusing on these points we can write more efficient solution. Approach is to find the three largest numbers and the two smallest numbers in efficient way. The final answer will be the maximum of the product of the three largest numbers and the product of the two smallest numbers and the one largest number.

Steps :

Declare and initialize 5 variables : min1 and min2 initialize with MAX VALUE and max1, max2 and max3 with MIN VALUE.
Iterate over loop and for each element, compare it with the minimum (min1 and min2) and maximum ( max1, max2 and max3) and update accordingly minimum and maximum values.
Calculate Product of the Three Largest Numbers ( max1*max2*max3).
Calculate Product of Two Smallest and One Largest Number (min1*min2*max1)
The maximum product will be the highest value of above two products.

C++

Java

Python

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

int maximumProduct(int arr[],int n)
{
    int min1 = INT_MAX, min2 = INT_MAX;
    int max1 = INT_MIN , max2 = INT_MIN, max3 = INT_MIN;
    for(int i = 0; i < n; i++) {
        if(min1 > arr[i]) {
            min2 = min1;
            min1 = arr[i];
        } else if(min2 > arr[i]) {
            min2 = arr[i];
        }

        if(max1 < arr[i]) {
            max3 = max2;
            max2 = max1;
            max1 = arr[i];
        } else if(max2 < arr[i]) {
            max3 = max2;
            max2 = arr[i];
        } else if(max3 < arr[i]) {
            max3 = arr[i];
        }
    }
    return max(max1 * max2 * max3, min1 * min2 * max1);
}
int main()
{
    int arr[] = {2,6,-7,8,-9,2,10};
    int n = sizeof(arr) / sizeof(arr[0]);
    cout<<maximumProduct(arr,n)<<endl;
    return 0;
}

Time Complexity : O(N)

Space Complexity : O(1)