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
Recommended: What is Algorithm | Introduction to Algorithms
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.