POTD #17 - Sum Pair closest to target | Geeks For Geeks

{% raw %}

Problem Statement

Geeks For Geeks : https://www.geeksforgeeks.org/problems/pair-in-array-whose-sum-is-closest-to-x1124/1

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.

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

Input: arr[] = [5, 2, 7, 1, 4], target = 10Output: [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 = 10Output: []Explanation: As the input array has only 1 element, return an empty array.

My Approach

O(n2) Approach

#User function Template for python3class Solution:    def sumClosest(self, arr, target):        # code here        arr.sort()        n = len(arr)        left = 0        right = n - 1                pairs = []        diff_to_target = None        abs_diff_in_pairs = None                for itr in range(n):            for jtr in range(itr+1, n):                _sum = arr[itr] + arr[jtr]                diff = abs(target - (arr[itr] + arr[jtr]))                abs_diff = abs(arr[jtr] - arr[itr])                # print("diff to target", diff_to_target)                if diff_to_target is None or (diff < diff_to_target) or (diff == diff_to_target and abs_diff > abs_diff_in_pairs):                    diff_to_target = diff                    abs_diff_in_pairs = abs_diff                    pairs = [arr[itr], arr[jtr]]        #     if abs_diff_in_pairs and abs_diff_in_pairs > abs(arr[-1] - arr[itr]) and diff_to_target != 0:        #         break        return pairs

But got timeout :).

Optimal Approach – Two Pointer

class Solution:    def sumClosest(self, arr, target):        # code here        arr.sort()        n = len(arr)        closest_diff = (2 * (10 ** 5)) + 1        result = []        left, right = 0, n - 1        while left < right:            current_sum = arr[left] + arr[right]            current_diff = abs(target - current_sum)            if current_diff < closest_diff:                closest_diff = current_diff                result = [arr[left], arr[right]]            elif current_diff == closest_diff:                if abs(arr[right] - arr[left]) > abs(result[1] - result[0]):                    result = [arr[left], arr[right]]            if current_sum < target:                left += 1            else:                right -= 1        return result

{% endraw %}