5 Best Ways to Find Pair Sum Lesser Than Target in Python

by

💡 Problem Formulation: Given a list of numbers, the task is to find a pair whose sum is as close as possible to, but not exceeding, a specified target number. For example, given numbers = [10, 20, 3, 7, 8, 2] and target = 15, the desired output would be (7, 8), since 7+8=15, which is the highest sum less than or equal to the target.

Method 1: Brute Force Search

This brute force approach involves checking every possible pair in the list to find the closest sum to the target without going over. The function will iterate through the list with two nested loops to find the optimal pair if it exists.

Here’s an example:

def find_pair(nums, target):
    best_sum = float('-inf')
    best_pair = ()
    for i in range(len(nums)):
        for j in range(i+1, len(nums)):
            current_sum = nums[i] + nums[j]
            if best_sum < current_sum <= target:
                best_sum = current_sum
                best_pair = (nums[i], nums[j])
    return best_pair

numbers = [10, 20, 3, 7, 8, 2]
target = 15
print(find_pair(numbers, target))

Output: (7, 8)

This snippet defines a function find_pair() that takes a list of numbers and a target sum. It initializes the best sum and best pair, then iterates through all possible pair combinations to find the pair with the highest sum less than or equal to the target.

Method 2: Sort and Two-Pointer Technique

By first sorting the list, this method uses a two-pointer technique to find the optimal pair. The pointers start on opposite ends of the list and move towards each other to find a suitable sum. This method is more efficient than the brute force approach as it requires fewer comparisons.

Here’s an example:

def find_pair_sorted(nums, target):
    nums.sort()
    left, right = 0, len(nums) - 1
    best_sum = float('-inf')
    best_pair = ()
    while left  target:
            right -= 1
        else:
            if current_sum > best_sum:
                best_sum = current_sum
                best_pair = (nums[left], nums[right])
            left += 1
    return best_pair

numbers = [10, 20, 3, 7, 8, 2]
target = 15
print(find_pair_sorted(numbers, target))

Output: (7, 8)

The function find_pair_sorted() sorts the list and initializes two pointers and the best pair. It iterates while adjusting the pointers based on their sum compared to the target, updating the best pair if the sum is optimal.

Method 3: Hash Map Lookup

This method uses a hash map (dictionary in Python) to store the difference between the target and current element. While iterating the list, the function checks if the current element’s complement (target – current element) is present in the hash map.

Here’s an example:

def find_pair_hash(nums, target):
    hashmap = {}
    best_sum = float('-inf')
    best_pair = ()
    for num in nums:
        complement = target - num
        if complement in hashmap:
            current_sum = complement + num
            if current_sum > best_sum:
                best_sum = current_sum
                best_pair = (complement, num)
        hashmap[num] = num
    return best_pair

numbers = [10, 20, 3, 7, 8, 2]
target = 15
print(find_pair_hash(numbers, target))

Output: (7, 8)

The snippet defines a function find_pair_hash() that uses a hash map to track elements. It updates the best pair whenever a complement of the current number is found in the map, and the sum is optimal.

Method 4: Binary Search for Complements

After sorting the array, for each element, perform a binary search to find the complement that gives the highest sum less than or equal to the target. This method leverages the sorted property to efficiently find the optimal pair.

Here’s an example:

def binary_search(nums, left, right, complement):
    while left < right:
        mid = left + (right - left) // 2
        if nums[mid]  best_sum:
                best_sum = current_sum
                best_pair = (num, nums[complement_index])
    return best_pair

numbers = [10, 20, 3, 7, 8, 2]
target = 15
print(find_pair_binary_search(numbers, target))

Output: (7, 8)

This code uses a helper function binary_search() to find the index of the number that, when added to the current number, gives the best sum. The main function find_pair_binary_search() iterates through the sorted list and uses the helper function to update the best pair.

Bonus One-Liner Method 5: Using itertools

The Python itertools module provides a combination function to iterate through all the pairs directly. This one-liner approach uses list comprehension to find the best pair and is a concise way to perform a brute force search.

Here’s an example:

from itertools import combinations

def find_pair_itertools(nums, target):
    return max((pair for pair in combinations(nums, 2) if sum(pair) <= target), key=sum, default=())

numbers = [10, 20, 3, 7, 8, 2]
target = 15
print(find_pair_itertools(numbers, target))

Output: (7, 8)

This snippet uses the combinations() function from the itertools module to generate all pairs and list comprehension to find the best pair. The max() function with the key=sum argument determines the pair with the highest sum that is less than or equal to the target.

Summary/Discussion

  • Method 1: Brute Force Search. Strength: Simple and straightforward. Weakness: Inefficient for larger lists due to O(n^2) time complexity.
  • Method 2: Sort and Two-Pointer Technique. Strength: More efficient than brute force, specifically O(nlogn) due to sorting. Weakness: Modifies the original list.
  • Method 3: Hash Map Lookup. Strength: Can find pairs in linear time, O(n). Weakness: Requires additional space for the hash map.
  • Method 4: Binary Search for Complements. Strength: Efficient search with O(nlogn) due to binary search. Weakness: Requires sorting upfront and more complex code.
  • Method 5: Using itertools. Strength: Concise code with a one-liner solution. Weakness: Equally inefficient as brute force with large datasets, due to O(n^2) combinations generation.