Maximize Product Difference of Two Pairs in Array

Given an array of positive integers, find the maximum product difference. The product difference between the two pairs is defined as taking the product of two pairs, followed by taking their difference. We have to maximize the product difference.

Examples:

Input: arr[] = {1, 4, 3, 6, 7, 0}  
Output: 39

Input: arr[] = {1, 3, 4, 2, 5, 7} 
Output: 33

Explanation:
The pairs which would return maximum product difference are (0,1) and (6,7).
The product of (0,1) is 0 while that of (6,7) is 42.
Their difference would be 42-0 = 42. It is the maximum product difference.

Simple approach:
The simplest approach is to first sort the array, followed by taking the product of the first and second element and the second last and last element. Then taking their difference.

Below is the implementation of this simple solution.

// A simple C++ program to find 
// the maximum product difference 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Function that will return 
// the maximum product difference
int maxProductDiff(vector<int> arr)
{
    int arr_size = arr.size();

    // First sort the array in increasing order
    sort(arr.begin(), arr.end());

    // The first pair would be the element at first and
    // second index
    int first_pair = arr[0] * arr[1];
    // The second pair would be the element at last  and
    // second-last  index
    int second_pair = arr[arr_size - 2] * arr[arr_size - 1];

    // Since the array consists of positive elements, hence
    // second_pair will greater than first pair
    int difference = second_pair - first_pair;

    return difference;
}

// Driver program to test
int main()
{

    vector<int> arr{ 4, 9, 2, 5, 8, 7, 8 };
    int max_prod_diff = maxProductDiff(arr);
    cout << "The maximum product difference is "
         << max_prod_diff << endl;
    return 0;
}

Output:

The maximum product difference is 64

Time complexity: O(nlogn)
Space complexity: O(1)

Now the question arises, can we do better? Of course, we can!

In the above approach, sorting is done, due to which the time complexity is O(nlogm).
But what if we don’t sort the array? The time complexity can be brought down to O(n).

Better Solution:
So instead of sorting the array, we will find the largest, second largest, smallest and second smallest element in the array.
The difference of such pair will always yield a maximum value, as asked in the question.

//A simple C++ program to find 
// the maximum product difference 
#include <algorithm>
#include <iostream>
#include <vector>
using namespace std;

// Function that will return 
// the maximum product difference
int maxProductDiff(vector<int> arr)
{
    int arr_size = arr.size();

    int first_max, second_max, first_small, second_small;
    // Assigning the value of first element
    first_max = second_max = first_small = second_small
        = arr[0];

    for (int i = 1; i < arr_size; i++) {
        // If the element is greater than the first_max,
        // then assgin the value of first_max to second_max
        // and value of arr[i] to that of first_max
        if (arr[i] > first_max) {
            second_max = first_max;
            first_max = arr[i];
        }

        // if a number is smaller than first_max,
        // but greater than second_max, then assgin
        // the value of it to second_max
        else if (arr[i] > second_max) {
            second_max = arr[i];
        }

        // Same goes with first_small and second_small
        else if (arr[i] < first_small) {
            second_small = first_small;
            first_small = arr[i];
        }

        else if (arr[i] < second_small) {
            second_small = arr[i];
        }
    }

    int second_pair = (first_max * second_max);
    int first_pair = (first_small * second_small);

    // second_pair is greater than first_pair
    int difference = second_pair - first_pair;

    return difference;
}

// Driver program to test
int main()
{

    vector<int> arr{ 4, 9, 2, 5, 8, 7, 8 };
    int max_prod_diff = maxProductDiff(arr);
    cout << "The maximum product difference is "
         << max_prod_diff << endl;
    return 0;
}

Output:

The maximum product difference is 64

Time complexity: O(n)
Space complexity: O(1)

Since the array here is traversed once, the time complexity would be linear time, i.e., O(n).

Please write comments below if you find anything incorrect, or you want to share more information about the topic discussed above. A gentle request to share this topic on your social media profile.