Sum Pair closest to target

Given an array arr[] and a number target, find a pair of elements (a, b) in arr[], where a<=b whose sum is closest to target.
Note: Return the pair in sorted order and if there are multiple such pairs return the pair with maximum absolute difference. If no such pair exists return an empty array.

Examples:

Input: arr[] = [10, 30, 20, 5], target = 25
Output: [5, 20]
Explanation: As 5 + 20 = 25 is closest to 25.

Input: arr[] = [5, 2, 7, 1, 4], target = 10
Output: [2, 7]
Explanation: As (4, 7) and (2, 7) both are closest to 10, but absolute difference of (2, 7) is 5 and (4, 7) is 3. Hence, [2, 7] has maximum absolute difference and closest to target. 

Input: arr[] = [10], target = 10
Output: []
Explanation: As the input array has only 1 element, return an empty array.

Constraints:
1 <= arr.size() <= 2*10⁵
0 <= target<= 2*10⁵
0 <= arr[i] <= 10⁵

Approach 01:

#include <vector>
#include <algorithm>
#include <climits>
using namespace std;

class Solution {
public:
    vector<int> sumClosest(vector<int>& numbers, int target) {
        vector<int> result;  // To store the pair with the closest sum
        sort(numbers.begin(), numbers.end());  // Sort the array to use the two-pointer technique
        int size = numbers.size();
        int left = 0, right = size - 1;  // Two pointers for finding the closest sum
        int closestDifference = INT_MAX;  // Minimum difference encountered so far

        while (left < right) {
            int currentSum = numbers[left] + numbers[right];

            // Update the closest pair if a smaller difference is found
            if (abs(currentSum - target) < closestDifference) {
                closestDifference = abs(currentSum - target);
                result = {numbers[left], numbers[right]};
            }

            // Adjust pointers based on the comparison of the current sum and target
            if (currentSum < target) {
                ++left;  // Increase the sum
            } else if (currentSum > target) {
                --right;  // Decrease the sum
            } else {
                return result;  // Exact match found, return immediately
            }
        }

        return result;  // Return the closest pair
    }
};

from typing import List

class Solution:
    def sumClosest(self, numbers: List[int], target: int) -> List[int]:
        numbers.sort()  # Sort the array to use the two-pointer technique
        left, right = 0, len(numbers) - 1  # Two pointers for finding the closest sum
        closestDifference = float('inf')  # Minimum difference encountered so far
        result = []  # To store the pair with the closest sum

        while left < right:
            currentSum = numbers[left] + numbers[right]

            # Update the closest pair if a smaller difference is found
            if abs(currentSum - target) < closestDifference:
                closestDifference = abs(currentSum - target)
                result = [numbers[left], numbers[right]]

            # Adjust pointers based on the comparison of the current sum and target
            if currentSum < target:
                left += 1  # Increase the sum
            elif currentSum > target:
                right -= 1  # Decrease the sum
            else:
                return result  # Exact match found, return immediately

        return result  # Return the closest pair

Time Complexity:

Time Complexity:

• Sorting the Array:

  The `sort` function is applied to the array, which takes \( O(n \log n) \), where \( n \) is the size of the array.

• Two-Pointer Traversal:

  The two-pointer approach iterates through the array once, resulting in \( O(n) \).

• Overall Time Complexity:

  \( O(n \log n) \), as the sorting operation dominates the traversal.

Space Complexity:

• In-place Sorting:

  The sorting operation is performed in-place, so no additional space is used for sorting, contributing \( O(1) \).

• Result Vector:

  The `result` vector requires \( O(2) \) space to store the pair of numbers.

• Overall Space Complexity:

  \( O(1) \), as the result vector and auxiliary variables use constant space.