Find two elements whose sum is closest to zero

Objective: Given an array of positive and negative integers, write a algorithm to find the two elements such their sum is closest to zero.

Example:

int a [] = {1, 4, -5, 3, -2, 10, -6, 20};
Output: Sum close to zero in the given array is : 1

int a [] = {-5, 5, 8};
Output: Sum close to zero in the given array is : 0

int a [] = {5, 8};
Output: Sum close to zero in the given array is : 13

int a [] = {-5,-5,-8};
Sum close to zero in the given array is : -10

Approach:

Naive approach: Use 2 loops. For each element in the array, find the sum with every other element and keep track of the minimum sum found.

Time Complexity : O(n^2) Space Complexity: O(1)

Sorting approach:

  1. Sort the array.
  2. This will bring all the negative elements at the front and positive elements at the end of the array.
  3. Track 2 numbers, one positive number close to 0, let’s call it as positiveClose  and one negative number close to 0, let’s call it as negativeClose.
  4. take 2 pointers, one from the beginning of the array and another one from the end of the array. say pointers are i and j.
  5. Add A[i] + A[j], if sum > 0 then reduce j, j– and if sum < 0 then increase i ++.
  6. If sum > 0 compare it with positiveClose, if positiveClose>sum, do positiveClose = sum.
  7. If sum < 0 compare it with negativeClose, if negativeClose<sum, do negativeClose = sum.
  8. Repeat the step 5, 6, 7 till i<j.
  9. Return the minimum of absolute values of positiveClose and negativeClose, this will be the answer.
  10. At any point if sum = 0 then return 0 since this will be the closest to the 0 is possible.
  11. We can easily modify the code given below to track the two indexes as well for which the closest sum is possible.

Time Complexity : O(nlogn) Space Complexity: O(n) by using merge sort.

Complete Code:

Output:
Sum close to zero in the given array is : 1

__________________________________________________
Top Companies Interview Questions..-

Google Microsoft Amazon Facebook more..

If you find anything incorrect or you feel that there is any better approach to solve the above problem, please write comment.
__________________________________________________

You may also like...

  • lipsa patel

    The solution does not return negative closest sum.

    Arrays.sort(array);

    int i = 0;
    int j = array.length – 1;

    int leftIndex = 0;
    int rightIndex = array.length – 1;

    int minimumSum = Integer.MAX_VALUE;
    int sum;

    if (array.length < 2) { //For one element return that element
    return array[0];
    }

    while(i < j) {

    sum = array[i] + array[j];

    if (Math.abs(sum) < Math.abs(minimumSum)) {
    minimumSum = sum;
    leftIndex = i;
    rightIndex = j;
    }

    if (sum < 0) {
    i++;
    } else {
    j–;
    }
    }

    System.out.println("The two elements whose sum is mimimum is " + array[leftIndex] + ", " + array[rightIndex]);
    return minimumSum;

  • Kumji Park

    It should return two elements, not closest sum.

%d bloggers like this: