Finding Closest Pair Without Exceeding Target

January 2, 2024

Problem #

Given an array of integers, find the pair of numbers that has the closest sum to a given target value, without exceeding it. Return the pair of numbers.

Solution: #

Algorithm: Two Pointers

Time Complexity: O(n log n) due to sorting Space Complexity: O(1) or O(n) depending on sorting algorithm

Steps:

1. Sort the array: Sort the array of integers in ascending order.
2. Initialize pointers: Create two pointers, left and right, pointing to the beginning and end of the array, respectively.
3. Iterate and compare:
   • While left is less than right:
     • Calculate the current sum: current_sum = array[left] + array[right].
     • If current_sum is equal to the target value, return the pair [array[left], array[right]].
     • If current_sum is less than the target value, move left to the next index to try a larger sum.
     • If current_sum is greater than the target value, move right to the previous index to try a smaller sum.
4. Return closest pair: If no exact match is found, return the pair that had the closest sum to the target value without exceeding it.

Code:

def closest_pair_to_target(array, target):
    array.sort()  # Sort the array
    left, right = 0, len(array) - 1
    closest_sum = float('inf')  # Initialize with infinity
    closest_pair = None

    while left < right:
        current_sum = array[left] + array[right]
        if current_sum == target:
            return [array[left], array[right]]  # Exact match found

        if abs(current_sum - target) < abs(closest_sum - target):
            closest_sum = current_sum
            closest_pair = [array[left], array[right]]

        if current_sum < target:
            left += 1
        else:
            right -= 1

    return closest_pair  # Return the closest pair found

array = [1, 4, 7, 10]
target = 8
result = closest_pair_to_target(array, target)
print(result)  # Output: [4, 7]