5 Best Ways to Find Three Unique Elements from a List Whose Sum is Closest to K in Python

Rate this post

πŸ’‘ Problem Formulation: Given a list of numbers and an integer K, the challenge is to find three unique elements in the list whose sum is closest to K without exceeding it. For example, if you have a list [1, 2, 3, 4, 5] and K is 10, a desired output could be [2, 3, 5] since their sum, 10, is exactly K.

Method 1: Brute Force Approach

This method involves generating all possible combinations of three different elements from the list, calculating the sum for each combination, and comparing it to K. It ensures the correct answer but may be slow for large lists, having a complexity of O(n^3).

Here’s an example:

from itertools import combinations

def find_closest_triplet(arr, k):
    closest_sum = float('inf')
    for triplet in combinations(arr, 3):
        current_sum = sum(triplet)
        if abs(k - current_sum) < abs(k - closest_sum):
            closest_sum = current_sum
            result = triplet
    return result

arr = [1, 2, 3, 4, 5]
k = 10
print(find_closest_triplet(arr, k))

Output:

(2, 3, 5)

The code defines a function find_closest_triplet that searches for the triplet whose sum of elements is closest to the given value K. It uses the combinations function from itertools to consider every possible triplet combination, making sure the triplet is unique by definition.

Method 2: Sorting and Two-Pointers

Another efficient method is to sort the list and then use two pointers to find the closest sum. This method has a better performance with a complexity of O(n^2).

Here’s an example:

def find_closest_triplet(arr, k):
    arr.sort()
    closest_sum = float('inf')
    for i in range(len(arr)-2):
        left, right = i+1, len(arr)-1
        while left < right:
            current_sum = arr[i] + arr[left] + arr[right]
            if abs(k - current_sum) < abs(k - closest_sum):
                closest_sum = current_sum
                result = (arr[i], arr[left], arr[right])
            if current_sum < k:
                left += 1
            else:
                right -= 1
    return result

arr = [12, 3, 1, 2, -6, 5, 0, -8]
k = 0
print(find_closest_triplet(arr, k))

Output:

(-6, 1, 5)

This code snippet sorts the array and then iterates over it, using a two-pointer approach to find the best triplet. The function find_closest_triplet returns the closest sum triplet to the given target K.

Method 3: Using a HashSet

By using a HashSet, we can check if the remaining value to reach K already exists in our list. This can be more space-efficient in some cases with a time complexity of O(n^2).

Here’s an example:

def find_closest_triplet(arr, k):
    arr.sort()
    closest_sum = float('inf')
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            complement = k - (arr[i] + arr[j])
            if complement in arr[j+1:]:
                current_sum = arr[i] + arr[j] + complement
                if abs(k - current_sum) < abs(k - closest_sum):
                    closest_sum = current_sum
                    result = (arr[i], arr[j], complement)
    return result

arr = [7, 4, 1, 10, 6, 5, 8]
k = 21
print(find_closest_triplet(arr, k))

Output:

(4, 7, 10)

Here, the function find_closest_triplet iterates over each pair of elements and then checks if the third element (K minus the sum of the pair) exists in the rest of the array. The triplet is then considered as the closest if its sum is nearest to K but not over it.

Method 4: Binary Search for the Third Element

For sorted arrays, binary search can be used to find the third element after fixing the first two elements. This method is very efficient with an average case complexity of O(n^2 log n).

Here’s an example:

from bisect import bisect_left

def find_two_elements_and_search(arr, k):
    arr.sort()
    closest_sum = float('inf')
    for i in range(len(arr)-2):
        for j in range(i+1, len(arr)-1):
            complement = k - (arr[i] + arr[j])
            index = bisect_left(arr, complement, j+1)
            if index < len(arr) and abs(complement - arr[index]) < abs(k - closest_sum):
                closest_sum = complement + arr[i] + arr[j]
                result = (arr[i], arr[j], arr[index])
    return result

arr = [1, 3, 4, 6, 7, 8]
k = 20
print(find_two_elements_and_search(arr, k))

Output:

(4, 7, 8)

This code uses the bisect_left function to perform binary search on the sorted array to find the closest third element to complete the triplet. The find_two_elements_and_search function applies this operation after fixing the first two elements.

Bonus One-Liner Method 5: Pythonic Approach with List Comprehensions

A more Pythonic one-liner utilizes list comprehensions for brevity. However, due to its underlying brute-force nature, it shares the same time complexity as the first method, O(n^3).

Here’s an example:

from itertools import combinations
arr, k = [10, 22, 28, 29, 30, 40], 54
closest_triplet = min(combinations(arr, 3), key=lambda triplet: abs(sum(triplet) - k))
print(closest_triplet)

Output:

(10, 22, 28)

The code succinctly expresses the brute-force approach of finding the closest sum triplet using combinations and min built-in functions, with a custom key for comparison based on the target sum K.

Summary/Discussion

Method 1: Brute Force Approach. Guarantees the correct result. High time complexity.

Method 2: Sorting and Two-Pointers. Efficient for medium-sized lists. Requires array sorting.

Method 3: Using a HashSet. Reduced space requirement. Potentially less efficient for finding the complementary value.

Method 4: Binary Search for the Third Element. Efficient for sorted lists. Increased complexity due to binary search.

Method 5: Pythonic Approach with List Comprehensions. Elegant and concise. Maintains brute force complexity.