# 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