2 Sum - Pair Sum Closest to 0
Given an integer array of N elements. You need to find the maximum sum of two elements such that sum is closest to zero.
Note : In case if we have two of more ways to form sum of two elements closest to zero return the maximum sum.
Input:
N = 3
arr[] = {-8 -66 -60}
Output: -68
Explanation: Sum of two elements closest to
zero is -68 using numbers -60 and -8.Input: N = 4 arr[] = [0, -8, -6, 3] Output: 3 Explanation: We have a tie between (0, 3) and (-6, 3). We pick the max sum in this case which is 0+3
- 1 ≤ arr.size ≤ 10^5
- 1 ≤ arr[i] ≤ 10^5
- 1 ≤ target ≤ 2*10^5
Approach 1 : Brute Force Approach Using Nested Loop
The brute force approach is the most straightforward way to solve this problem. It uses two nested loops to check every possible pair in the array. For each pair, we calculate the sum and keep track of the one with the smallest absolute value. If multiple pairs have the same absolute sum, we choose the pair with the larger actual sum.
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int closestToZero(int arr[], int n) {
int res = arr[0] + arr[1];
for (int i = 0; i < n - 1; i++) {
for (int j = i + 1; j <n; j++) {
int sum = arr[i] + arr[j];
if (abs(sum) < abs(res)) {
res = sum;
}
else if(abs(sum) == abs(res)) {
res = max(res, sum);
}
}
}
return res;
}
int main() {
int arr1[] = {-8, 5, 2, -6};
int arr2[] = {-21, -67, -37, -18, 4, -65};
int arr3[]= {0, -8, -6, 3};
cout << "Example 1: " << closestToZero(arr1, 4) << endl;
cout << "Example 2: " << closestToZero(arr2, 6) << endl;
cout << "Example 3: " << closestToZero(arr3, 4) << endl;
return 0;
}Example 1: -1 Example 2: -14 Example 3: 3
Time Complexity : O(N^2)
Space Complexity : O(1)
Approach 2 : Sorting and Binary Search – O(n*log(n)) time and O(1) space
In this approach, we aim to find the pair with a sum closest to zero by combining sorting with binary search. First, we sort the array to make binary search possible. Then, for each element, we use binary search to find the closest complement (the number that would bring the total sum closer to zero). If we encounter a pair whose sum is exactly zero, we return immediately since that’s the best case. Otherwise, we keep updating the best (closest-to-zero) sum found so far.
- Sort the array to enable binary search.
- Iterate through the array, treating each number as the first element of a potential pair.
- Use binary search to find the closest second element.
- Update the closest sum if the current pair gives a smaller absolute sum.
- Return 0 if an exact zero sum pair is found.
- Return the closest sum after checking all pairs.
#include <bits/stdc++.h>
using namespace std;
int closestToZero(int arr[], int n) {
sort(arr, arr + n);
int closestSum = INT_MAX;
for (int i = 0; i < n; i++) {
int x = arr[i];
int left = i + 1, right = n - 1;
while (left <= right) {
int mid = (left + right) / 2;
int curr = arr[mid] + x;
if (curr == 0) {
return 0;
}
if (abs(curr) < abs(closestSum)) {
closestSum = curr;
}
else if(abs(curr) == abs(closestSum)) {
closestSum = max(closestSum, curr);
}
if (curr < 0) {
left = mid + 1;
} else {
right = mid - 1;
}
}
}
return closestSum;
}
int main() {
int arr1[] = {-8, 5, 2, -6};
int arr2[] = {-21, -67, -37, -18, 4, -65};
int arr3[]= {0, -8, -6, 3};
cout << "Example 1: " << closestToZero(arr1, 4) << endl;
cout << "Example 2: " << closestToZero(arr2, 6) << endl;
cout << "Example 3: " << closestToZero(arr3, 4) << endl;
return 0;
}Example 1: -1 Example 2: -14 Example 3: 3
Time Complexity : O(N log N)
Space Complexity : O(1)
Approach 3 : Sorting + Two Pointer Approach (O(n log n) Time, O(1) Space)
This approach combines sorting with the two-pointer technique to efficiently find the pair whose sum is closest to zero. First, we sort the array in ascending order. Then, we place one pointer at the beginning (smallest value) and another at the end (largest value). We calculate the sum of the elements at these two pointers and compare it to the best (closest-to-zero) sum.
Step-by-step implementation
- Sort the array in ascending order.
- Initialize two pointers — one at the start (left) and one at the end (right) of the array.
- Create variables to keep track of the closest sum and the smallest absolute sum.
- While the left pointer is less than the right pointer:
- Calculate the current sum of the two elements.
- If this sum is closer to zero than the previous best, update the closest sum.
- If the sum is negative, move the left pointer right.
- If the sum is positive, move the right pointer left.
- After the loop, return the closest sum found.
#include <iostream>
#include <algorithm>
#include <climits>
using namespace std;
int closestToZero(int arr[], int n) {
sort(arr, arr + n);
int left = 0, right = n - 1;
int minAbsSum = INT_MAX;
int closestSum = 0;
while (left < right) {
int sum = arr[left] + arr[right];
int absSum = abs(sum);
if (absSum < minAbsSum || (absSum == minAbsSum && sum > closestSum)) {
minAbsSum = absSum;
closestSum = sum;
}
if (sum < 0)
left++;
else
right--;
}
return closestSum;
}
int main() {
int arr1[] = {-8, 5, 2, -6};
int arr2[] = {-21, -67, -37, -18, 4, -65};
int arr3[]= {0, -8, -6, 3};
cout << "Example 1: " << closestToZero(arr1, 4) << endl;
cout << "Example 2: " << closestToZero(arr2, 6) << endl;
cout << "Example 3: " << closestToZero(arr3, 4) << endl;
return 0;
}Example 1: -1 Example 2: -14 Example 3: 3
Time Complexity : O(NlogN)
Space Complexity : O(1)