Maximum Product of Two Integers in an Array
Maximum Product of Two Integers in an Array
The purpose of this post is to find a maximum product of two integers in a given array. For example, consider array {-10, -2, 4, 5, 3}. The maximum product is the (-10, -2) or (4, 5) pair.
Brute-Force Solution
A brute-force solution or a naive solution is to consider every pair of elements and calculate their product. If the product of the current pair is greater, update the maximum product found so far. Finally, print the elements that give the maximum product. This is demonstrated below in C++, Java, and Python:
In C++
// Program to find maximum product of two integers in an array // Naive-method or Brute-force method #include<iostream> // this header file stores the value of constant INT32_MIIN #include<climits> // function definition void maxProduct(int arr[], int size){ if(size<2){ return; } // let max_product be -inf int max_product=INT32_MIN; int max_i,max_j; // finds out the required pair be comparing max_product with every possible pair for(int i=0;i<size-1;i++){ for(int j=i+1;j<size;j++){ if(max_product<arr[i]*arr[j]){ max_product=arr[i]*arr[j]; max_i=i; max_j=j; } } } std::cout<<"Pair is: "<<arr[max_i]<<","<<arr[max_j]; return; } int main(){ // array of type int int arr[]={-3,-6,2,8,1}; // size of arr int size=sizeof(arr)/sizeof(arr[0]); // function call to maxProduct() maxProduct(arr,size); return 0; }
Output:
Pair is: -3,-6
In Java
// Program to find maximum product of two integers from an array // Naive method or brute-force approach public class pair_max_array_a { // function definition static void maxProduct(int arr[]){ if(arr.length<2){ return; } // let maximum product be -inf int max_product=Integer.MIN_VALUE; int max_i=-1,max_j=-1; for(int i=0;i<arr.length-1;i++){ for(int j=i+1;j<arr.length;j++){ if(max_product<arr[i]*arr[j]){ max_product=arr[i]*arr[j]; max_i=i; max_j=j; } } } System.out.println("Pair is: "+arr[max_i]+","+arr[max_j]); return; } public static void main(String[] args) { int arr[]={3,9,-5,-3,1}; // function call to maxProduct maxProduct(arr); } }
Output:
Pair is: 3,9
In Python
# Program to find maximum product of two integers in an array # Naive-approach or Brute-force method # has data member maxsize import sys # function definition def maxProduct(arr): # if length is less than two, then there is no pair if len(arr)<2: return # let maximum product be - infinity max_product=-sys.maxsize # let indices of the required pair be -1 max_i=max_j=-1 # for every number except last for i in range(len(arr)-1): # for every number after ith for j in range(i+1,len(arr)): if max_product<arr[i]*arr[j]: # executes if max_product is less than arr[i]*arr[j] max_product=arr[i]*arr[j] max_i,max_j=i,j print("Pair is: ",arr[max_i],",",arr[max_j]) arr=[2,6,9,-1,-5,3] maxProduct(arr)
Output:
Pair is: 6 , 9
The time complexity of the above solution is O(n2), where n is the size of the input and doesn’t require any extra space.
Using Sorting
The time complexity obtained in the solution provided above can be improved by sorting the array. Then the result which is the maximum product of two integers, is the maximum of the following:
- The product of the maximum and second maximum integer in the array (i.e., the last two elements in a sorted array).
- The product of minimum and second minimum integers in the array (i.e., the first two elements in the sorted array).
Implementation of the above algorithm in C++, Java, and Python is given below:
In C++
// Program to find maximum product of two integers in an array // Using sorting #include<iostream> // contains the function sort() #include<algorithm> void maxProduct(int arr[], int size){ // sorts arr std::sort(arr,arr+size); if(arr[0]*arr[1]<arr[size-2]*arr[size-1]){ std::cout<<"Pair is: "<<arr[size-1]<<","<<arr[size-1]; }else{ std::cout<<"Pair is: "<<arr[0]<<","<<arr[1]; } return; } int main(){ int arr[]={-3,-6,2,8,1}; // size of arr int size=sizeof(arr)/sizeof(arr[0]); // function call to maxProduct() maxProduct(arr,size); return 0; }
Output:
Pair is: -6,-3
In Java
// Program to find maximum product of two integers from an array // using sorting import java.util.Arrays; public class pair_max_array_b { // function definition static void maxProduct(int arr[]){ int n=arr.length; if(n<2){ return; } // sorts arr Arrays.sort(arr); if(arr[0]*arr[1]<arr[n-2]*arr[n-1]){ System.out.println("Pair is: "+arr[n-2]+","+arr[n-1]); } else{ System.out.println("Pair is: "+arr[0]+","+arr[1]); } } public static void main(String[] args) { int arr[]={3,9,-5,-3,1}; // function call to arr maxProduct(arr); } }
Output:
Pair is: 3,9
In Python
# Program to find maximum product of two integers in an array # Using sorting # function definition def maxProduct(arr): if len(arr)<2: return # sorts arr arr.sort() if(arr[0]*arr[1]<arr[len(arr)-2]*arr[len(arr)-1]): print("Pair is: ",arr[len(arr)-2],",",arr[len(arr)-1]) else: print("Pair is: ",arr[0],",",arr[1]) return arr=[2,6,9,-1,-5,3] maxProduct(arr)
Output:
Pair is: 6 , 9
Time complexity of the above solution is O(n.log(n)), where n is the size of the input, and doesn’t require any extra space.
Using Maximum, Second Maximum, Minimum, and Second Minimum element
We can solve this problem in linear time using only maximum, second maximum, minimum, and second minimum elements. We can compute all these in only a single traversal of the array, which accounts for O(n) time complexity. This approach is demonstrated below in C++, Java, and Python:
In C++
// Program to find maximum product of two integers from a given array // Using maximum, second maximum, minimum, and second maximum element #include<iostream> // contains values of constant INT32_MIN and INT32_MAX #include<climits> // function definition void maxProduct(int arr[], int size){ if(size<2){ return; } // let maximum element be arr[0] int max1=arr[0]; // let second minimum element be -inf int max2=INT32_MIN; // let minimum element be arr[0] int min1=arr[0]; // let second minimum element be +inf int min2=INT32_MAX; for(int i=1;i<size;i++){ if(arr[i]>max1){ // executes if current element is greater than the maximum element max2=max1; max1=arr[i]; } else if(arr[i]>max2){ // exexutes if current element is less than maximum element but greater than second maximum element max2=arr[i]; } if(arr[i]<min1){ // executes if current element is less than the minimum element min2=min1; min1=arr[i]; } else if(arr[i]<min2){ // exexutes if current element is greater than minimum element but less than second minimun element min2=arr[i]; } } if(min1*min2<max1*max2){ std::cout<<"Pair is: "<<max1<<","<<max2; }else{ std::cout<<"Pair is "<<min1<<","<<min2; } return; } int main(){ // array of type int int arr[]={-3,-6,2,8,1}; // size of arr int size=sizeof(arr)/sizeof(arr[0]); // function call to maxProduct() maxProduct(arr,size); return 0; }
Output:
Pair is -6,-3
In Java
// Program to find maximum product of two integers from an array // Using maximum, second maximum, minimum, and second minimum public class pair_max_array_c { // function definition static void maxProduct(int arr[]){ int n=arr.length; if(n<2){ return; } int max1=arr[0]; // let second maximum be -inf int max2=Integer.MIN_VALUE; int min1=arr[0]; // let second minimum be +inf int min2=Integer.MAX_VALUE; for(int i=1;i<n;i++){ if(arr[i]>max1){ // executes if current element is greater tha maximum max2=max1; max1=arr[i]; }else if(arr[i]>max2){ // executes if current element is less than maximum but greater than second maximum element max2=arr[i]; } if(arr[i]<min1){ // executes if current element is less tha minimum min2=min1; min1=arr[i]; } else if(arr[i]<min2){ // executes if current element is greater than minimum but less than second minimum element min2=arr[i]; } } if(min1*min2<max1*max2){ System.out.println("Pair is: "+max1+","+max2); } else{ System.out.println("Pair is: "+min1+","+min2); } } public static void main(String[] args) { int arr[]={3,9,-5,-3,1}; // function call to arr maxProduct(arr); } }
Output:
Pair is: 9,3
In Python
# Program to find maximum product of two integers in a given array # Finding maximum, second maximum, minimum and second minimum in a single traversal import sys # function definition def maxProduct(arr): if len(arr)<2: return # let maximum element be arr[0] max1=arr[0] # let second maximum element be -inf max2=-sys.maxsize # let minimum element be arr[0] min1=arr[0] # let second minimum element be +inf min2=sys.maxsize # for every number from index 1 for i in range(1,len(arr)): if arr[i]>max1: # executes if current element is greater than maximum element max2=max1 max1=arr[i] elif arr[i]>max2: # executes is current element is less than maximum element but greater than second maximum element max2=arr[i] if arr[i]<min1: # executes if current element is less than minimum element min2=min1 min1=arr[i] elif arr[i]<min2: # executes if current element is greater than minimum element byt less than seecond minimum element min2=arr[i] if min1*min2 <max1*max2: print("Pair is: ",max1,",",max2) else: print("Pair is: ",min1,",",min2) # array arr=[2,6,9,-1,-5,3] # function call maxProduct(arr)
Output:
Pair is: 9 , 6