Find the maximum product of two integers in an array

By | October 6, 2021

We have given an Integer array, and we need to find two numbers from the array whose product is the maximum.

For example

Vamware

Input 

arr = [-10, -10, 3, 4, -2, 25]
output  = [-10, -10] or [25,4]

Explanation

In the above array, we have 6 integer elements, and out of those 6 elements two pairs (-10, -10) and (25, 4) has the maximum product value i.e. 100.

Approach 1

Naive Algorithm 

In the Naive algorithm, we will go for the brute force technique, where we will multiple every subarray pair present in the array. And look for the maximum product value pair, and print it.

Algorithm

  1. Initialize a max_product with a minimal initial value.
  2.  Also, initialize two variables val1, and val2 that will represent two elements with the maximum product.
  3. Create a nested for loop for every pair present in the array.
  4. Inside the nested loop check for the maximum product, and store the element values in the val1 , and val2 and update max_product value.

C++ Programming

#include <iostream>
using namespace std;
 
// function to find the maximum product pair
//using naive approch
void find_maximum_product(int arr[], int n)
{
	// initialize a max product variable
	// with a minimal value 
    int max_product = -999999999;
    int val1, val2;
 
    // find out every pair present in the array
    for (int i = 0; i < n - 1; i++)
    {
        for (int j = i + 1; j < n; j++)
        {
            //check for the max product pairs
            if (max_product < arr[i] * arr[j])
            {	
            	//update max_product value
                max_product = arr[i] * arr[j];
                val1 = arr[i]; 
				val2 = arr[j];
            }
        }
    }
 
    cout<<"Max Product Pair is ("<<val1 <<", "<<val2<<")";
int main()
{ 
    //given array
    int arr[] = { -10, -10, 3, 4, -2, 25 };
    
    //length of the array
    int n = sizeof(arr) / sizeof(arr[0]);

    find_maximum_product(arr, n);
    return 0;
}

Output

Python Programing

#function to find the maximum product pair
# using naive approch
def find_maximum_product(arr, n):

    # initialize a max product variable
    max_product = -999999999

    #find out every pair present in the array
    for i in range(n):
        for j in range(i+1, n):

            # check for the max product pairs
            if max_product < arr[i]* arr[j]:
                #update max_product value
                max_product = arr[i]*arr[j]
                val1 = arr[i]
                val2 = arr[j]
    print(f"Max Product Pair is ({val1}, {val2})")

if __name__=="__main__":
    #given array
    arr= [-10, -10, 3, 4, -2, 25 ]

    #len of array
    n = len(arr)

    find_maximum_product(arr,n)

Output

Complexity Analysis

Time Complexity: The time complexity of the above algorithm is O(N^2) where N is the total number of elements present in the array.

Space Complexity: O(1), because we did not use any extra space.

 

Approach 2

Sort the array and product the largest and second-largest pair

The idea behind this approach is very straightforward. First, we gonna sort the array using quicksort or an optimized sorting algorithm. Then check the product of the last & second last elements and first &second elements (in case of negative values). Then print the first two pairs or the last two pairs, based on their maximum value.

Algorithm

  1. Sort the array.
  2. Find the product of the first two elements.
  3. Find the product of the last two elements.
  4. Check if the product of the first two elements is greater than the last two elements, and print the max product pairs.

C++ Programming

#include 
#include 

using namespace std;
 
// function to find the maximum product pair
//using naive approch
void find_maximum_product(int arr[], int n)
{	//sort the array
	 sort(arr, arr + n);
	 
	 // first 2 elements 
	 int min1 = arr[0];
	 int min2 = arr[1];
	 
	 // last 2 elements
	 int max1= arr[n-1];
	 int max2 = arr[n-2];
	 
	 if((min1*min2)>= (max1*max2))
	 	cout<<"Max Product Pair is ("<<min1 <<", "<<min2<<")";
         else
                cout<<"Max Product Pair is ("<<max1 <<", "<<max2<<")";
}

int main()
{ 
    //given array
    int arr[] = { -10, -10, 3, 4, -2, 25 };

    //length of the array
    int n = sizeof(arr) / sizeof(arr[0]);

    find_maximum_product(arr, n);
    return 0;
}

Output

Python Programming

#function to find the maximum product pair
# using sorting approch
def find_maximum_product(arr, n):

    arr.sort()

    #first 2 elements
    min1, min2 = arr[0], arr[1]

    # last 2 elements
    max1, max2 = arr[n-1], arr[n-2]

    if (min1*min2) >= (max1*max2):
        print(f"Max Product Pair is ({min1}, {min2})")
    else:
        print(f"Max Product Pair is ({max1}, {max2})")

if __name__=="__main__":
    #given array
    arr= [-10, -10, 3, 4, -2, 25 ]

    #length of array
    n = len(arr)

    find_maximum_product(arr,n)

Output

Complexity Analysis

Time Complexity: The time complexity of the above program is O(Nlog(N)) , because because of sorting.

Space Complexity: O(1), because we did not use any extra array or space to store array values.

Approach 3

Optimize algorithm with linear time complexity

In the above program, we generally pick the minimum & second minimum and maximum, and second maximum elements by sorting the array.

If we only need 4 elements from the array, then we do not need to sort it we can find these 4 elements using a single traversal or loop. In this optimize algorithm we will use logic to find out the maximum, second maximum, minimum, and second minimum elements from the array. And find out which pair has the largest product value.

Algorithm

  1. Set maximum and second maximum initial values by array[0] and -999999999 (smallest value).
  2. Set minimum and second minimum initial values by array[0] and 999999999 (largest value).
  3. Create a loop that will traverse through the complete array.
  4. Inside the loop check if the element is greater than the maximum value, then update the maximum value and set the second maximum by maximum.
  5. Also, check if the array element is smaller than the maximum value but greater than the second maximum value in that case only update the second maximum value by the array element.
  6. The same steps 4 and 5 go for the minimum values.
  7. At last, check whether the product of the minimum and second minimum is greater than the maximum and second maximum.

C++ Programming

#include 
#include 

using namespace std;
 
// function to find the maximum product pair
//using naive approch
void find_maximum_product(int arr[],int n)
{	//initialize maximum and second maximum values
	int max1 = arr[0];
	int max2 = -999999999999;    //as small as possible
	
	// initialize minimum and second minimum values 
	int min1 = arr[0];
	int min2 = 9999999999; //as large as possible
	
	for(int i=1; i<n; i++) 
        { 
               // check if the current element is greater than maximum value 
                if(arr[i]>max1)
		{
			//update the maximum and second maximum values
			max2 = max1;
			max1= arr[i];
		 } 
		 //check if the current element is greater than 
		 //second maximum number but smaller than maximum number
		 //only update second maximum number
		 else if(arr[i]> max2)
		 {
		 	max2 = arr[i];
		 }
		
		
		// check if the current element is smaller than maximum value
		if(arr[i]<min1)
		{
			//update the minimum and second minimum values
			min2 = min1;
			min1= arr[i];
		 } 
		 //check if the current element is smaller than 
		 //second minimum number but greater than minimum number
		 //only update second minimum number
		 else if(arr[i]< min2) 
                 { 
                         min2 = arr[i]; 
                  } 
        } 
        if((min1*min2)>= (max1*max2)) 
		cout<<"Max Product Pair is ("<<min1 <<", "<<min2<<")"; 
        else
                cout<<"Max Product Pair is ("<<max1 <<", "<<max2<<")";
}
int main()
{ 
//given array
int arr[] = { -10, -10, 3, 4, -2, 25 };

//length of the array
int n = sizeof(arr) / sizeof(arr[0]);

find_maximum_product(arr, n);

return 0;
}

Python Programming

#function to find the maximum product pair
# using sorting approch
def find_maximum_product(arr, n):
    # initialize maximum and second maximum values
    max1, max2 = arr[0], -999999999999

    #initialize minimum and second minimum values
    min1, min2 = arr[0], 99999999999

    for i in range(1, n):
        # check if the current element is greater than maximum value
        if arr[i]> max1:
            # update the maximum and second maximum values
            max2 = max1
            max1 = arr[i]
        # check if the current element is greater than
        #  second maximum number but smaller than maximum number
        #  only update second maximum number
        elif arr[i]>max2:
            max2 = arr[i]

        # check if the current element is smaller than maximum value
        if arr[i]= (max1*max2):
        print(f"Max Product Pair is ({min1}, {min2})")
    else:
        print(f"Max Product Pair is ({max1}, {max2})")

if __name__=="__main__":
    #given array
    arr= [-10, -10, 3, 4, -2, 25 ]

    #length of array
    n = len(arr)

    find_maximum_product(arr,n)

Output

Complexity Analysis

  • Time Complexity: O(N), where N is the total number of elements present in the array.
  • Space Complexity: O(1), because we did not use any extra space to store array elements.

Wrapping Up!

In this tutorial, we learned three different algorithms to Find the maximum product of two integers in an array. And implement all three algorithms using C++ and Python programming languages.

In the first approach, we used the Brute force technique, where we calculate the product of every possible pair and find out the maximum product pairs. The time complexity of this approach is O(N^2).

In the second approach, we optimized the algorithm and find out the max product pairs by sorting the array. In this approach we able to solve the problem with O(Nlog(N)) time complexity.

To optimize the solution, in the third approach we solved the problem with the linear time complexity of O(N).

People are also reading:

Leave a Reply

Your email address will not be published. Required fields are marked *