Two numbers with sum closest to zero

Problem: Given an integer array, you need to find the two elements such that their sum is closest to zero.

For example:

Input: arr[] =  {-21, -67, -37, -18, 4, -65}
Output:-18 4

-18 + 4 = -12 is the closet sum pair to zero.

Method 1: Find the sum of every pair of numbers in the array. Finally, return the minimum sum.

class InterviewDesk
{
  static void minSumPair(int arr[], int len)
  {    
    /* handling base case i.e array should have 
       at least two elements*/
    if(len < 2)
    {
      System.out.println("Invalid Input");
      return;
    }
    
    /* Initialize the values */
    int pos1 = 0, pos2 = 1, min_sum, sum;
    min_sum = arr[pos1] + arr[pos2];
    
    /* calculating for each pair of numbers */
    for(int i = 0; i < len - 1; i++)
    {
      for(int j = i + 1; j < len; j++)
      {
        sum = arr[i] + arr[j];
        if(Math.abs(min_sum) > Math.abs(sum))
        {
          min_sum = sum;
          pos1 = i;
          pos2 = j;
        }
      }
    }
    
    System.out.println(arr[pos1]+ " and "+arr[pos2]);
  }
   
  /* driver function */
  public static void main (String[] args) 
  {
      int arr[] = {1, 60, -10, 70, -80, 85};
      minSumPair(arr, 6);
  }
     
}

Output:

-80 and 85

Time Complexity: O(n²)

Method 2: Below is the algorithm to decrease the time complexity:

1. Sort the array in non-decreasing order. 
2. Initialize two index variables to find the candidate elements in the sorted array.
• Initialize first to the leftmost index: l = 0
• Initialize second the rightmost index: r = len - 1
3. Loop while l < r. 
• sum = Arr[l] + Arr[r]
• if sum is -ve l++
• else r--
4. Keep track of abs min sum

import java.util.Arrays;

class Main
{
  static void minSumPair(int arr[], int len)
  {
    /* keeping track of current sum and minimum sum */
    int sum, min_sum = 999999;
    
    /* left and right index variables */
    int l = 0, r = len - 1;
    
    /* variables to keep track of position of pair with min sum */
    int pos1 = l, pos2 = len - 1;
    
    /* handling base case i.e array should have 
       at least two elements*/
    if(len < 2)
    {
      System.out.println("Invalid Input");
      return;
    }
   
    /* sort the elements */
    Arrays.sort(arr);
    
    while(l < r)
    {
      sum = arr[l] + arr[r];
    
      /*If abs(sum) is less then update the result items*/
      if(Math.abs(sum) < Math.abs(min_sum))
      {
        min_sum = sum;
        pos1 = l;
        pos2 = r;
      }
      if(sum < 0)
        l++;
      else
        r--;
    }
    System.out.println(arr[pos1] + " and " + arr[pos2]);
  }
    
  /* driver function */
  public static void main (String[] args) 
  {
      int arr[] = {1, 60, -10, 70, -80, 85};
      int len = arr.length;
      minSumPair(arr, len);
  }
}

Output:

-80 and 85

Time Complexity: O(n)