5 Best Ways to Check if We Can Find Three Unique Elements Whose Sum Equals K in Python

Rate this post

πŸ’‘ Problem Formulation: Given an array of integers and a target value k, the challenge is to determine whether there exist three distinct elements in the array that add up to k. For example, in the array [1, 4, 45, 6, 10, 8] and target value k=22, a possible solution could be the elements (4, 10, 8).

Method 1: Brute Force

The brute force method involves checking all possible combinations of three elements in the array to see if their sum equals the target value k. While simple, this method has a high time complexity of O(n^3), making it inefficient for large arrays.

Here’s an example:

def find_three_sum_brute_force(arr, k):
    n = len(arr)
    for i in range(n):
        for j in range(i+1, n):
            for l in range(j+1, n):
                if arr[i] + arr[j] + arr[l] == k:
                    return (arr[i], arr[j], arr[l])
    return None

print(find_three_sum_brute_force([1, 4, 45, 6, 10, 8], 22))

Output:

(4, 10, 8)

In this code snippet, we define a function find_three_sum_brute_force() that searches for any triplet in the array that adds up to the target sum k. It uses three nested loops, each selecting an element of the triplet, to check every possible combination.

Method 2: Sorting and Two-pointers Technique

This method first sorts the array, then uses a fixed point and two pointers to find pairs that add up to k minus the fixed element. This reduces time complexity to O(n^2).

Here’s an example:

def find_three_sum_two_pointers(arr, k):
    arr.sort()
    for i in range(len(arr)-2):
        l, r = i + 1, len(arr) - 1
        while l < r:
            current_sum = arr[i] + arr[l] + arr[r]
            if current_sum == k:
                return (arr[i], arr[l], arr[r])
            elif current_sum < k:
                l += 1
            else:
                r -= 1
    return None

print(find_three_sum_two_pointers([1, 4, 45, 6, 10, 8], 22))

Output:

(4, 10, 8)

The function find_three_sum_two_pointers() first sorts the array. It then iterates over the array, fixing one number and using two other pointers to scan through the array for the other two numbers required to meet the target sum k.

Method 3: Hashing

Hashing can be used to achieve O(n^2) time complexity as well. This method checks if the sum k minus a fixed element exists in a hash table containing all possible sums of the two other numbers.

Here’s an example:

def find_three_sum_hashing(arr, k):
    for i in range(len(arr) - 1):
        s = set()
        current_sum = k - arr[i]
        for j in range(i + 1, len(arr)):
            if (current_sum - arr[j]) in s:
                return (arr[i], arr[j], current_sum - arr[j])
            s.add(arr[j])
    return None

print(find_three_sum_hashing([1, 4, 45, 6, 10, 8], 22))

Output:

(4, 10, 8)

This code establishes a hash table for holding the integers we have processed. The function find_three_sum_hashing() iterates through the array, at each step, looking within the hash table for the complement of the current element that would fulfill the target sum k.

Method 4: Using Binary Search

After sorting the array, for each element, we can use binary search to find the other two elements which complete the sum k. This utilizes the fact that the array is sorted to reduce the search space for each pair.

Here’s an example:

def binary_search(arr, start, end, x):
    while start <= end:
        mid = start + (end - start) // 2
        if arr[mid] == x:
            return mid
        elif arr[mid] < x:
            start = mid + 1
        else:
            end = mid - 1
    return -1

def find_three_sum_binary_search(arr, k):
    arr.sort()
    for i in range(len(arr)):
        for j in range(i+1, len(arr)):
            target = k - (arr[i] + arr[j])
            if binary_search(arr, j+1, len(arr)-1, target) != -1:
                return (arr[i], arr[j], target)
    return None

print(find_three_sum_binary_search([1, 4, 45, 6, 10, 8], 22))

Output:

(4, 6, 12)

The code defines a helper function called binary_search() which is employed by find_three_sum_binary_search() to find the third number that makes up the target sum k along with two other fixed numbers.

Bonus One-Liner Method 5: Using itertools Combinations

Python’s itertools library includes a function to generate all possible combinations of N elements, which can be applied to create a one-liner solution to finding three elements that sum up to k. This is an elegant but not the most efficient solution.

Here’s an example:

from itertools import combinations

def find_three_sum_itertools(arr, k):
    return next((combo for combo in combinations(arr, 3) if sum(combo) == k), None)

print(find_three_sum_itertools([1, 4, 45, 6, 10, 8], 22))

Output:

(4, 10, 8)

This one-liner uses a generator expression with combinations() from the itertools module to iterate through all possible sets of three elements, returning the first that sums up to k.

Summary/Discussion

  • Method 1: Brute Force. Easy to implement. Inefficient with high time complexity, especially for large arrays.
  • Method 2: Sorting and Two-pointers. More efficient than brute force. Requires the array to be mutable for sorting.
  • Method 3: Hashing. Offers good time complexity. Extra space complexity due to hash table creation. Possible issue with handling of duplicates.
  • Method 4: Using Binary Search. Offers a logarithmic search time after initial sorting. Requires additional implementation for binary search logic if not using built-in functions.
  • Bonus Method 5: Using itertools Combinations. Simple and elegant. Not suitable for performance-critical applications due to its O(n^3) time complexity.