Closest Pair Sum in an unsorted Array

Summary

This problem is about finding the pair of elements in an unsorted array that has a sum closest to a given target value. The key concepts involved are sorting and two-pointer algorithm.

Detailed Explanation

The solution involves using the two-pointer technique, where we first sort the array and then initialize two pointers at the start and end of the array. We keep track of the closest pair found so far and update it as we move the pointers towards each other.

Here is a step-by-step breakdown of the solution:

1. Sort the input array in ascending order.
2. Initialize two pointers, start and end, to the first and last elements of the sorted array, respectively.
3. Calculate the sum of the elements at the start and end positions.
4. If the calculated sum is closer to the target value than the closest pair found so far, update the closest pair.
5. Move the pointers towards each other by incrementing the start pointer or decrementing the end pointer based on whether the current sum is less than or greater than the target value, respectively.
6. Repeat steps 3-5 until the pointers meet in the middle of the array.

The time complexity of this solution is O(n log n) due to the sorting step, where n is the length of the input array. The space complexity is O(1) as we only use a constant amount of extra space.

Optimized Solutions

Java

java
public class ClosestPairSum {
    public static int closestPairSum(int[] arr, int target) {
        Arrays.sort(arr);
        int start = 0;
        int end = arr.length - 1;
        int closestPairSum = Integer.MAX_VALUE;
        while (start < end) {
            int currentSum = arr[start] + arr[end];
            if (Math.abs(currentSum - target) < Math.abs(closestPairSum - target)) {
                closestPairSum = currentSum;
            }
            if (currentSum < target) {
                start++;
            } else {
                end--;
            }
        }
        return closestPairSum;
    }
}

Python

python
def closest_pair_sum(arr, target):
    arr.sort()
    start = 0
    end = len(arr) - 1
    closest_pair_sum = float('inf')
    while start < end:
        current_sum = arr[start] + arr[end]
        if abs(current_sum - target) < abs(closest_pair_sum - target):
            closest_pair_sum = current_sum
        if current_sum < target:
            start += 1
        else:
            end -= 1
    return closest_pair_sum

C++

cpp
int closestPairSum(int arr[], int n, int target) {
    sort(arr, arr + n);
    int start = 0;
    int end = n - 1;
    int closestPairSum = INT_MAX;
    while (start < end) {
        int currentSum = arr[start] + arr[end];
        if (abs(currentSum - target) < abs(closestPairSum - target)) {
            closestPairSum = currentSum;
        }
        if (currentSum < target) {
            start++;
        } else {
            end--;
        }
    }
    return closestPairSum;
}

JavaScript

javascript
function closestPairSum(arr, target) {
    arr.sort((a, b) => a - b);
    let start = 0;
    let end = arr.length - 1;
    let closestPairSum = Infinity;
    while (start < end) {
        let currentSum = arr[start] + arr[end];
        if (Math.abs(currentSum - target) < Math.abs(closestPairSum - target)) {
            closestPairSum = currentSum;
        }
        if (currentSum < target) {
            start++;
        } else {
            end--;
        }
    }
    return closestPairSum;
}