Problem

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

Examples

Example 1:

1
2
3

Input: arr = [1, 4, -5, 3, -2, 10, -6, 20]
Output: 1
Explanation: The closest sum to zero is achieved by 4 and -5, which sum to -1.

Example 2:

1
2
3

Input: arr = [-5, 5, 8]
Output: 1
Explanation: The closest sum to zero is achieved by -5 and 5, which sum to 0.

Example 3:

1
2
3

Input: arr = [5, 8]
Output: 13
Explanation: The closest sum to zero is achieved by 5 and 8, which sum to 13.

Example 3:

1
2
3

Input: arr = [-5, -5, -8]
Output: -10
Explanation: The closest sum to zero is achieved by -5 and -5, which sum to -10.

Solution

Method 1 - Use Nested Loops

For each array element, compute its sum with every other element and record the smallest sum obtained. Time Complexity: O(n^2) Space Complexity: O(1)

Method 2 - Sorting

Here is the approach:

  1. Sort the input array.
  2. Use two pointers, one at the beginning (left) and one at the end (right) of the array, and find the pair with the sum closest to zero.
  3. Move the pointers towards each other to check other potential pairs.
  4. Record and return the closest sum found.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39

public class Solution {
    public int closestSumToZero(int[] arr) {
        Arrays.sort(arr);
        int left = 0;
        int right = arr.length - 1;
        int closestSum = Integer.MAX_VALUE;

        while (left < right) {
            int currentSum = arr[left] + arr[right];
            if (Math.abs(currentSum) < Math.abs(closestSum)) {
                closestSum = currentSum;
            }

            if (currentSum < 0) {
                left++;
            } else {
                right--;
            }
        }

        return closestSum;
    }

    public static void main(String[] args) {
        Solution solution = new Solution();

        int[] a1 = {1, 4, -5, 3, -2, 10, -6, 20};
        System.out.println("Sum close to zero in the given array is: " + solution.closestSumToZero(a1));  // Output: 1

        int[] a2 = {-5, 5, 8};
        System.out.println("Sum close to zero in the given array is: " + solution.closestSumToZero(a2));  // Output: 0

        int[] a3 = {5, 8};
        System.out.println("Sum close to zero in the given array is: " + solution.closestSumToZero(a3));  // Output: 13

        int[] a4 = {-5, -5, -8};
        System.out.println("Sum close to zero in the given array is: " + solution.closestSumToZero(a4));  // Output: -10
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35

class Solution:
    def closestSumToZero(self, arr):
        arr.sort()
        left = 0
        right = len(arr) - 1
        closest_sum = float('inf')
        closest_pair = (None, None)

        while left < right:
            current_sum = arr[left] + arr[right]
            if abs(current_sum) < abs(closest_sum):
                closest_sum = current_sum
                closest_pair = (arr[left], arr[right])

            if current_sum < 0:
                left += 1
            else:
                right -= 1

        return closest_sum

# Example usage
solution = Solution()

a1 = [1, 4, -5, 3, -2, 10, -6, 20]
print(f"Sum close to zero in the given array is : {solution.closestSumToZero(a1)}")  # Output: 1

a2 = [-5, 5, 8]
print(f"Sum close to zero in the given array is : {solution.closestSumToZero(a2)}")  # Output: 0

a3 = [5, 8]
print(f"Sum close to zero in the given array is : {solution.closestSumToZero(a3)}")  # Output: 13

a4 = [-5, -5, -8]
print(f"Sum close to zero in the given array is : {solution.closestSumToZero(a4)}")  # Output: -10

Complexity

  • ⏰ Time complexity: O(n log n) - O(n log n) for sorting the array, and O(n) for the two-pointer traversal, resulting in an overall complexity of O(n log n).
  • 🧺 Space complexity: O(1), as the algorithm uses a constant amount of extra space.