Two Elements Whose Sum is Closest to Zero in Java
Finding two elements whose sum is closest to zero is a common problem in computer science and mathematics. Given an array of integers, the array may contain both positive and negative values, the goal is to find the pair of elements whose sum is closest to zero.
It means that we need to find the pair of elements whose sum has the smallest absolute value. If there are multiple pairs of elements whose sum has the same absolute value, we can return any one of them.
Example 1:
Input: [1, 2, 3, -4, -5]
Output: [-4, 3]
Explanation:
The pair [-4, 3] has a sum closest to zero (-1), compared to other possible pairs such as [1, 2] and [-5, 2].
Example 2:
Input: [-10, -5, -2, 3, 4, 9]
Output: [-10, 9]
Explanation:
The pair [-10, 9] has a sum closest to zero (1), compared to other possible pairs such as [-5, 4] [-2,3].
Approach: Using Brute force
In this approach, we check all possible pairs of elements in the input array, calculate their sum, and keep track of the closest sum.
ALGORITHM:
Step 1: Create a function findClosestPair that takes an integer array nums as input and returns an integer array result as output.
Step 2: Initialize result array of size 2 and closestSum as maximum integer value.
Step 3: Loop through each pair of elements in the array:
Step 3.1: Initialize sum as the sum of current element and the next element in the array.
Step 3.2: Calculate absolute value of sum and update the closestSum if the absolute sum is closer to zero than the previous closestSum.
Step 3.3: Update the result array with current element and the next element if the closestSum is updated.
Step 4: Return the result array.
Step 5: Create the main function that:
Step 5.1: Define two integer arrays nums1 and nums2.
Step 5.2: Call the function findClosestPair for each array.
Step 5.3: Print the closest pair for each array.
Step 6: Compile and run the program.
FileName: ClosestToZeroBruteForce.java
import java.util.*;
public class ClosestToZeroBruteForce {
// This function takes an array of integers and returns an array of size 2
// containing the pair of elements whose sum is closest to zero
public static int[] findClosestPair(int[] nums) {
int[] result = new int[2];
int closestSum = Integer.MAX_VALUE;
// Loop through each pair of elements in the array
for (int i = 0; i < nums.length; i++) {
for (int j = i+1; j < nums.length; j++) {
int sum = nums[i] + nums[j];
int absSum = Math.abs(sum);
// Update the closest pair if the sum is closer to zero
if (absSum < Math.abs(closestSum)) {
closestSum = sum;
result[0] = nums[i];
result[1] = nums[j];
}
}
}
// Return the pair of elements whose sum is closest to zero
return result;
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3, -4, -5};
int[] closestPair1 = findClosestPair(nums1);
System.out.println("Closest pair for nums1: [" + closestPair1[0] + ", " + closestPair1[1] + "]");
int[] nums2 = {-10, -5, -2, 3, 4, 9};
int[] closestPair2 = findClosestPair(nums2);
System.out.println("Closest pair for nums2: [" + closestPair2[0] + ", " + closestPair2[1] + "]");
}
}
Output:
Closest pair for nums1: [3, -4]
Closest pair for nums2: [-10, 9]
Complexity Analysis:
Time complexity: O(n^2) where n is the length of the input array .we loop through each pair of elements in the array.
Space complexity: O(1) as we only use a fixed amount of extra space to store the result array and closestSum variable.
Approach: Using Sorting
ALGORITHM:
Step 1: Sort the input array in ascending order.
Step 2: Initialize two pointers, one at the beginning (left) and one at the end (right) of the array.
Step 3: Loop through the array while the left pointer is less than the right pointer.
Step 4: Calculate the sum of the elements at the left and right pointers.
Step 5: If the absolute value of the sum is less than the absolute value of the closest sum seen so far, update the closest sum and result array with the current elements.
Step 6: Move the pointers towards each other based on the sum. If the sum is less than zero, move the left pointer to the right. Otherwise, move the right pointer to the left.
Step 7: Return the result array.
FileName: ClosestToZeroSorting.java
import java.util.*;
public class ClosestToZeroSorting {
public static int[] findClosestPair(int[] nums) {
int[] result = new int[2];
int closestSum = Integer.MAX_VALUE;
// Sort the array in ascending order
Arrays.sort(nums);
int left = 0;
int right = nums.length - 1;
while (left < right) {
int sum = nums[left] + nums[right];
int absSum = Math.abs(sum);
// Update the closest pair if the sum is closer to zero
if (absSum < Math.abs(closestSum)) {
closestSum = sum;
result[0] = nums[left];
result[1] = nums[right];
}
// Move the pointers towards each other based on the sum
if (sum < 0) {
left++;
} else {
right--;
}
}
return result;
}
public static void main(String[] args) {
int[] nums1 = {1, 2, 3, -4, -5};
int[] closestPair1 = findClosestPair(nums1);
System.out.println("Closest pair for nums1: [" + closestPair1[0] + ", " + closestPair1[1] + "]");
int[] nums2 = {-10, -5, -2, 3, 4, 9};
int[] closestPair2 = findClosestPair(nums2);
System.out.println("Closest pair for nums2: [" + closestPair2[0] + ", " + closestPair2[1] + "]");
}
}
Output:
Closest pair for nums1: [-4, 3]
Closest pair for nums2: [-10, 9]
Complexity Analysis:
The time complexity of the sorting approach is O(n log n), where n is the length of the input array. The sorting operation takes O(n log n) time in the worst case.
The space complexity of the sorting approach is O(1) because it only uses a constant amount of extra space for the result array and a few variables used for iteration and calculation. The sorting operation is usually performed in-place and does not require any extra memory.
Approach: STL(Standard Template Library)
Step 1: Convert the given array to a TreeSet to sort and remove duplicates.
Step 2: Initialize two iterators for the TreeSet; one to iterate from the beginning, and another to iterate from the end.
Step 3: Initialize two variables to store the current value being pointed by both the iterators.
Step 4: While the value pointed by the left iterator is less than or equal to the value pointed by the right iterator, do the following:
Step 4.1: Calculate the sum of the current left and right values.
Step 4.2: Calculate the absolute value of the sum.
Step 4.3: If the absolute value of the sum is less than the absolute value of the closestSum variable, update the closestSum to be the sum, and store the current left and right values in the result array.
Step 4.4: If the absolute value of the sum is equal to the absolute value of the closestSum variable, update the closestSum to be the sum only if it is positive.
Step 4.5: Move the iterator that points to the smaller value.
Step 5: Return the result array containing the two values that sum up closest to zero.
FileName: ClosestToZeroSorting.java
import java.util.*;
public class ClosestToZeroSorting {
public static int[] findClosestPair(int[] nums) {
int[] result = new int[2];
int closestSum = Integer.MAX_VALUE;
// Convert array to TreeSet to sort and remove duplicates
TreeSet<Integer> sortedNums = new TreeSet<>();
for (int num : nums) {
sortedNums.add(num);
}
// Iterate through the sorted set to find the closest pair
Iterator<Integer> left = sortedNums.iterator();
ListIterator<Integer> right = new ArrayList<>(sortedNums).listIterator(sortedNums.size());
int leftVal = left.next();
int rightVal = right.previous();
while (leftVal <= rightVal) {
int sum = leftVal + rightVal;
int absSum = Math.abs(sum);
// Update the closest pair if the sum is closer to zero
if (absSum < Math.abs(closestSum)) {
closestSum = sum;
result[0] = leftVal;
result[1] = rightVal;
}
// Move the iterator with smaller value
if (absSum == Math.abs(closestSum)) {
if (sum > closestSum) {
rightVal = right.previous();
} else {
leftVal = left.next();
}
} else if (sum > 0) {
rightVal = right.previous();
} else {
leftVal = left.next();
}
}
return result;
}
public static void main(String[] args) {
// Example 1
int[] nums1 = {1, 2, 3, -4, -5};
int[] closestPair1 = findClosestPair(nums1);
System.out.println("Closest pair for nums1:(" + closestPair1[0] + ", " + closestPair1[1]+")");
// Example 2
int[] nums2 = {-10, -5, -2, 3, 4, 9};
int[] closestPair2 = findClosestPair(nums2);
System.out.println("Closest pair for nums2:(" + closestPair2[0] + ", " +closestPair2[1]+")");
}
}
Output:
Closest pair for nums1:(-4, 3)
Closest pair for nums2:(-10, 9)
Complexity Analysis:
Time Complexity: Converting the array to TreeSet takes O(n log n) time, and iterating through the TreeSet takes O(n) time. Therefore, the overall time complexity is O(n log n).
Space Complexity: O(n).The space complexity is dominated by the TreeSet created to store the array elements. It takes O(n) space to store the elements in the TreeSet. The result array and iterators used in the algorithm take constant space. Therefore, the overall space complexity is O(n).