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 and 20 is 25, 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

  1. Sort the array in ascending order.
  2. Initialize two pointers, left at the start and right at the end of the array.
  3. Use a variable closestSum to track the sum closest to the target.
  4. While left < right:
    • Calculate the sum of the elements at left and right.
    • If the current sum is closer to the target than closestSum, update closestSum 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.
  5. 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.