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

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 = 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.

My Approach

O(n2) Approach


#User function Template for python3
class 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