# 5 Best Ways to Find the Lowest Sum of Pairs Greater Than a Given Target in Python

Rate this post

π‘ Problem Formulation: Finding the smallest sum of a pair of numbers that is greater than a specified target number is a common problem in algorithm design and programming. For instance, given a list `[5, 20, 16, 11, 10]` and a target sum `21`, the lowest sum of pairs that exceeds the target is `22` resulting from the pair `(11, 11)`.

## Method 1: Brute Force Approach

The brute force approach involves checking the sum of every pair in the list and selecting the smallest sum that is greater than the target. This method is straightforward but not the most efficient, as its time complexity is O(n^2), where n is the size of the list.

Here’s an example:

```def find_lowest_sum_brute_force(nums, target):
nums.sort()
smallest_sum = float('inf')
for i in range(len(nums)):
for j in range(i, len(nums)):
pair_sum = nums[i] + nums[j]
if target < pair_sum < smallest_sum:
smallest_sum = pair_sum
return smallest_sum

print(find_lowest_sum_brute_force([5, 20, 16, 11, 10], 21))```

Output:

`22`

The function `find_lowest_sum_brute_force` first sorts the list to ensure pairs are evaluated in increasing order. It then iterates over each potential pair, updating the `smallest_sum` variable whenever a sum that is greater than the target and smaller than the current `smallest_sum` is found.

## Method 2: Using Binary Search

This method first sorts the array, then for each element, it uses binary search to find the smallest number that, when added to the current element, results in a sum greater than the target. This method has a better time complexity of O(n log n).

Here’s an example:

```def binary_search(nums, start, end, target):
while start < end:
mid = start + (end - start) // 2
if nums[mid] <= target:
start = mid + 1
else:
end = mid
return start

def find_lowest_sum_binary_search(nums, target):
nums.sort()
smallest_sum = float('inf')
for i in range(len(nums)):
complement_index = binary_search(nums, i, len(nums), target - nums[i])
if complement_index != len(nums):
smallest_sum = min(smallest_sum, nums[i] + nums[complement_index])
return smallest_sum

print(find_lowest_sum_binary_search([5, 20, 16, 11, 10], 21))```

Output:

`22`

The `find_lowest_sum_binary_search` function utilizes a helper function `binary_search` to quickly find the smallest element that can complement each number in the sorted list to form a sum greater than the target. This greatly reduces the number of necessary comparisons.

## Method 3: Two-pointers Technique

The two-pointer technique involves iterating through the list with two pointers, moving one from the start and the other from the end, and adjusting their positions based on the sum relative to the target. This is an efficient method with a time complexity of O(n) after the list has been sorted.

Here’s an example:

```def find_lowest_sum_two_pointers(nums, target):
nums.sort()
smallest_sum = float('inf')
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum <= target:
left += 1
else:
smallest_sum = min(smallest_sum, current_sum)
right -= 1
return smallest_sum

print(find_lowest_sum_two_pointers([5, 20, 16, 11, 10], 21))```

Output:

`22`

The `find_lowest_sum_two_pointers` function uses two pointers to efficiently find the smallest sum greater than the target. The while loop continues until the two pointers meet, ensuring all relevant pairs are considered without unnecessary comparisons.

## Method 4: Using a Heap

By turning the list into a min-heap, this method can efficiently find the smallest sum. It pairs each element with the root of the heap (smallest element) unless it is the root itself; if necessary, the next smallest item from the heap is used instead. Time complexity is O(n log n) due to heap operations.

Here’s an example:

```import heapq

def find_lowest_sum_heap(nums, target):
smallest_sum = float('inf')
heapq.heapify(nums)
for num in nums:
while nums and nums[0] <= target - num:
heapq.heappop(nums)
if nums:
smallest_sum = min(smallest_sum, num + nums[0])
return smallest_sum

print(find_lowest_sum_heap([5, 20, 16, 11, 10], 21))```

Output:

`22`

The `find_lowest_sum_heap` function converts the list into a min-heap using the `heapq` library. Then for each element, it pops elements from the heap until it finds one that can be used in a pair where the sum is greater than the target.

## Bonus One-Liner Method 5: List Comprehension with Min Function

A compact and readable one-liner can be constructed using a combination of list comprehension and the `min` function. This method, while concise, will still have the inefficiency of the brute force approach.

Here’s an example:

```def find_lowest_sum_oneliner(nums, target):
return min([x + y for x in nums for y in nums if x + y > target], default=float('inf'))

print(find_lowest_sum_oneliner([5, 20, 16, 11, 10], 21))```

Output:

`22`

This one-liner `find_lowest_sum_oneliner` function constructs a list of the sums of all possible pairs that exceed the target and returns the smallest one. It utilizes Python’s list comprehension and `min` function for succinctness.

## Summary/Discussion

• Method 1: Brute Force Approach. Simple implementation. Inefficient with large datasets.
• Method 2: Using Binary Search. More efficient than brute force. Requires sorted data, adding overhead.
• Method 3: Two-pointers Technique. Efficient and quick. Still necessitates sorted data.
• Method 4: Using a Heap. Suitable for large datasets. Heap construction adds complexity.
• Bonus Method 5: List Comprehension with Min Function. Elegant one-liner. Not optimal for performance.