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(n²), 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:

// 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;
}

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

# 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)

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