703192. Sum Pair closest to target
Sum Pair closest to target
Slug: pair-in-array-whose-sum-is-closest-to-x1124 Difficulty: Easy Id: 703192 Topic Tags: Arrays, Data Structures, two-pointer-algorithm Company Tags: Ola Cabs
Summary
Given an array of integers and a target sum x, find the pair in the array whose sum is closest to x. The function should return the pair's indices. This problem involves arrays, data structures, and the two-pointer algorithm.
Detailed Explanation
To solve this problem, we can use the two-pointer algorithm. Initialize two pointers, one at the start of the array (left) and one at the end of the array (right). Calculate the sum of the values at these indices. If the calculated sum is less than x, move the left pointer to the right. If the calculated sum is greater than x, move the right pointer to the left. Repeat this process until the left and right pointers meet or cross each other.
Here's a step-by-step breakdown of the solution:
- Initialize two pointers,
leftandright, to the start and end of the array, respectively. - Calculate the sum of the values at the current indices (
leftandright) and compare it withx. - If the calculated sum is less than
x, move theleftpointer to the right. - If the calculated sum is greater than
x, move therightpointer to the left. - Repeat steps 2-4 until the
leftandrightpointers meet or cross each other. - Return the indices of the pair with a sum closest to
x.
The time complexity of this solution is O(n), where n is the length of the array, since we only need to traverse the array once. The space complexity is O(1), as we don't use any extra space.
Optimized Solutions
Java
public int[] closestPair(int[] arr, int x) {
int left = 0;
int right = arr.length - 1;
int minDiff = Integer.MAX_VALUE;
int[] result = new int[2];
while (left < right) {
int sum = arr[left] + arr[right];
if (Math.abs(sum - x) < minDiff) {
minDiff = Math.abs(sum - x);
result[0] = left;
result[1] = right;
}
if (sum < x) {
left++;
} else {
right--;
}
}
return result;
}