Find two elements in an array such that their sum is closest to 0 (ZERO). (Method 2)

Question: Given an array with both positive and negative numbers, find the two elements such that their sum is closest to zero. ?

Input: arr [] = {1, 60, -10, 70, -80, 85}
Output: -80, 85 (Their sum is -5 that is closest to 0(zero))

What we discussed was the most naive approach by using two for loops. However, this method is not optimized and will take a lot of time if the data is very large. We need to improve the complexity of the program.

One such method is discussed below.

• Sort all the elements of the given input array.
• Maintain two indexes one at the beginning (i=0) and one at the end (j=n-1). Also maintain two variables to keep track of smallest positive sum closest to zero and smallest negative sum closest to zero.
• While (i<j)
  ->If the current pair sum > zero and < positiveClosest, then update the positiveClosest. Decrement j;
  ->If the current pair sum < zero and > negativeClosest, then update the negativeClosest. Increment i.
  ->Else print the pair.

Here is an implementation of the above algorithm.

int twoElementsWithMinSum(int arr[],int size)
{
	//starting index and last index
	int i=0, j=n-1;
	int temp,;
	
	//set the positiveClosest and negativeClosest to
	//maximum and minimum integer values
	int positiveClosest = INT_MAX;
	int negativeClosest = INT_MIN;
	
	//to store the pair of numbers
	int p1=0,p2=0;
	int n1=0,n2=0;
	
	//sort the array
	quickSort(arr,size);
	
	//loop between start index and last index
	while(i<j)
	{
		//sum the pair
		temp = arr[i] + arr[j];
		
		//check for positive sum
		if(temp>0)
		{
			if(temp < positiveClosest)
				positiveClosest = temp;
			
			p1=arr[i];
			p2=arr[j];
			
			//decrement last index
			j--;
		}
		
		//check for negative sum
		else if(temp<0)
		{
			if(temp > negativeClosest)
				negativeClosest = temp;
			
			n1=arr[i];
			n2=arr[j];
			
			//increment first index
			i++;
		}
		else
		{
			printf("The Closest sum is by numbers = %d",(arr[i]+arr[j]));
			return;
		}
	}
	
	if((negativeClosest*-1)<positiveClosest)
		printf("%d %d",n1,n2);
	else
		printf("%d %d",p1,p2);	
}

Time Complexity:- O(n*log(n)), for sorting the array
Space Complexity:- O(1)