Sum Pair closest to target
Problem Description
Given an array of integers and a target value, find a pair of elements (a, b) such that a <= b
and their sum is closest to the target. If there are multiple such pairs, return the one with the maximum absolute difference. If no valid pair exists, return an empty list.
Example:
- Input:
arr[] = [10, 30, 20, 5]
,target = 25
- Output:
[5, 20]
- Explanation: The sum of
5
and20
is25
, which is closest to the target.
Solution Code
import java.util.*;
class Solution {
public List<Integer> sumClosest(int[] arr, int target) {
Arrays.sort(arr); // Sort the array to use the two-pointer approach
int left = 0; // Pointer to the start of the array
int right = arr.length - 1; // Pointer to the end of the array
int closestSum = Integer.MAX_VALUE; // To store the closest sum to the target
List<Integer> result = new ArrayList<>(); // To store the result pair
while (left < right) {
int sum = arr[left] + arr[right]; // Calculate the current sum
// Check if the current sum is closer to the target than the previous closest sum
if (Math.abs(sum - target) < Math.abs(closestSum - target)) {
closestSum = sum;
result.clear();
result.add(arr[left]);
result.add(arr[right]);
} else if (Math.abs(sum - target) == Math.abs(closestSum - target)) {
// If the sums are equally close, choose the pair with the maximum absolute difference
if (Math.abs(arr[left] - arr[right]) > Math.abs(result.get(0) - result.get(1))) {
result.clear();
result.add(arr[left]);
result.add(arr[right]);
}
}
// Adjust pointers based on the comparison with the target
if (sum < target) {
left++; // Move left pointer to increase the sum
} else {
right--; // Move right pointer to decrease the sum
}
}
return result;
}
}
Hint
- Sort the array and use a two-pointer approach to efficiently find the pair whose sum is closest to the target. Handle ties by selecting the pair with the maximum absolute difference.
Approach Name
Two-Pointer Technique with Sorting
Intuition
By sorting the array, we can use two pointers to traverse the array from both ends. This allows us to efficiently find the pair whose sum is closest to the target. If there are multiple pairs with the same closeness, we prioritize the pair with the maximum absolute difference.
Algorithm
- Sort the array in ascending order.
- Initialize two pointers,
left
at the start andright
at the end of the array. - Use a variable
closestSum
to track the sum closest to the target. - While
left < right
:- Calculate the sum of the elements at
left
andright
. - If the current sum is closer to the target than
closestSum
, updateclosestSum
and store the pair. - If the current sum is equally close to the target, choose the pair with the maximum absolute difference.
- Adjust the pointers based on whether the sum is less than or greater than the target.
- Calculate the sum of the elements at
- Return the result pair.
Test Input
10 30 20 5, 25
Complexity Analysis
- Time Complexity: O(n log n), where
n
is the number of elements in the array. Sorting takes O(n log n), and the two-pointer traversal takes O(n). - Space Complexity: O(1), as we are using a constant amount of extra space.
This solution efficiently finds the pair whose sum is closest to the target using sorting and a two-pointer approach, ensuring optimal performance for the given constraints.