Sorting: Find a pair with maximum product in array of integers

Problem Statement:

You are given an array with +ve and -ve integers, return a pair with highest product

Example:

Input [1, 3, -4, 2, -5]

Output: [-4, -5]

Solution 1

Keep track of max product by considering every pair

Time Complexity: O(n*n)
Space Complexity: O(1)

Solution 2:

Sort the array

if all the elements are +ve, return the product of last two numbers.

else return the max of products of first 2 and last 2 numbers

Time Complexity: O(n logn)
Space Complexity: O(1)

Code Solution

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>
#include <limits.h>

using namespace std;


void solution_1(vector<int> arr, int n) 
{ 
	if (n < 2) 
	{ 
		cout << "No pairs exists\n"; 
		return; 
	} 

	int a = arr[0], b = arr[1]; 

	for (int i=0; i<n; i++) 
	for (int j=i+1; j<n; j++) 
		if (arr[i]*arr[j] > a*b) 
			a = arr[i], b = arr[j]; 

	cout << "Max product pair is = " << a << ", "
		<< b ; 
} 

void solution_2(vector<int>arr, int n) 
{ 
      
    sort(arr.begin(), arr.end()); 

    int num1, num2; 
      
    int sum1 = arr[0] * arr[1]; 
    
    int sum2 = arr[n - 1] * arr[n - 2]; 
    
    if (sum1 > sum2)  
    { 
        num1 = arr[0]; 
        num2 = arr[1]; 
    } 
    else 
    { 
        num1 = arr[n - 2]; 
        num2 = arr[n - 1]; 
    } 
    cout << ("Max product pair = ")  
         << num1 << ", " << num2; 
} 


int main() 
{ 
	vector<int>arr =  {1, 4, 3, 6, 7, 0}; 
	int n = sizeof(arr)/sizeof(arr[0]); 
	solution_1(arr, n); 
	cout<<endl;
	solution_2(arr, n); 
	return 0; 
}

Output

Max product pair = 6, 7
Max product pair = 6, 7