Sum Pair closest to target

JavaView on GFG

Problem Overview

Find pair with sum closest to target.

See our study guide for structured GFG and LeetCode practice.

Intuition

Find pair with sum closest to target. Sort + two pointers tracking minimum difference.

Algorithm

1Sort. l=0, r=n-1. Track minDiff and best pair. If sum < target: l++. If sum > target: r--. If equal: return.

Common Pitfalls

• Same as LC 1679 variant. Sort first. Update best when |sum - target| < minDiff.

Sum Pair closest to target.java

Java

// Approach: Sort array. Two pointers from ends: track closest pair sum to target, move pointers accordingly.
// Time: O(n log n) Space: O(1)
import java.util.*;

class Solution {
    public List<Integer> sumClosest(int[] arr, int target) {
        Arrays.sort(arr);
        List<Integer> res = new ArrayList<>();
        int l = 0;
        int h = arr.length - 1;
        int a = -1;
        int b = -1;
        int maxDiff = 0;

        while (l < h) {
            int sum = arr[l] + arr[h];

            if (sum <= target) {
                if (Math.abs(target - sum) < Math.abs(target - (a + b))
                        || (sum == a + b && Math.abs(arr[l] - arr[h]) > maxDiff)) {
                    a = arr[l];
                    b = arr[h];
                    maxDiff = Math.abs(arr[l] - arr[h]);
                }
                l++;
            } else {
                if ((a == -1 && b == -1) || Math.abs(target - sum) < Math.abs(target - (a + b))
                        || (sum == a + b && Math.abs(arr[l] - arr[h]) > maxDiff)) {
                    a = arr[l];
                    b = arr[h];
                    maxDiff = Math.abs(arr[l] - arr[h]);
                }
                h--;
            }
        }

        if (a != -1 && b != -1) {
            res.add(a);
            res.add(b);
        }

        return res;
    }
}

Was this solution helpful?