5 Best Ways to Check for Four Elements Summing to K in Python

Rate this post

πŸ’‘ Problem Formulation: Given an array of integers and a target sum value k, we seek an efficient algorithm in Python to determine whether any four elements within the array can be summed to equal the value of k. For instance, if we have the array [1, 0, -1, 0, -2, 2] and a target sum k = 0, a desired output would be True because the quadruple (-1, 0, 0, 1) sums to 0.

Method 1: Brute Force Approach

The brute force method involves checking all possible combinations of four elements in the array to see if any of them sum to k. While this method is straightforward and easy to understand, it is highly inefficient with a time complexity of O(n^4) as it tests every combination without any optimization or early exit strategies.

Here’s an example:

def four_sum_brute_force(nums, k):
    n = len(nums)
    for i in range(n):
        for j in range(i+1, n):
            for l in range(j+1, n):
                for m in range(l+1, n):
                    if nums[i] + nums[j] + nums[l] + nums[m] == k:
                        return True
    return False

print(four_sum_brute_force([1, 0, -1, 0, -2, 2], 0))

Output: True

This code checks each unique set of four indices in the array and sums the corresponding elements to check against k. If a group is found that sums to k, the function returns True; if none are found, it returns False.

Method 2: Using Sorting and Two-Pointer Technique

This method first sorts the array and then applies the two-pointer technique in a nested loop, reducing the problem complexity to O(n^3). It is more efficient than the brute force method but still not optimal for large datasets.

Here’s an example:

def four_sum_two_pointers(nums, k):
    nums.sort()
    n = len(nums)
    for i in range(n - 3):
        for j in range(i + 1, n - 2):
            l, r = j + 1, n - 1
            while l < r:
                total = nums[i] + nums[j] + nums[l] + nums[r]
                if total == k:
                    return True
                elif total < k:
                    l += 1
                else:
                    r -= 1
    return False

print(four_sum_two_pointers([1, 0, -1, 0, -2, 2], 0))

Output: True

By sorting the array first and then using two pointers to reduce the need for extra iterations, we can improve the efficiency of our solution significantly, though it can still be slow if the input array is large.

Method 3: Using a Hash Table

This approach uses a hash table to store pairs of sums, thereby checking if a given sum minus a current pair’s sum is already in the hash table, resulting in an average time complexity close to O(n^2).

Here’s an example:

def four_sum_hash_table(nums, k):
    hash_table = {}
    n = len(nums)
    for i in range(n - 1):
        for j in range(i + 1, n):
            current_sum = nums[i] + nums[j]
            diff = k - current_sum
            if diff in hash_table:
                return True
            hash_table[current_sum] = (i, j)
    return False

print(four_sum_hash_table([1, 0, -1, 0, -2, 2], 0))

Output: True

A hash table is used to store the sums of all pairs of integers. For every pair, we calculate the difference between the target sum k and the current pair sum; if this difference is already in the table, we return True, else we continue.

Method 4: Using a Set for Early Stopping

Similar to the hash table method, this one also seeks to achieve O(n^2) time complexity. It utilizes sets and an early stopping mechanism to avoid unnecessary processing once the target sum has been found.

Here’s an example:

def four_sum_set_early_stop(nums, k):
    nums.sort()
    found_values = set()
    n = len(nums)
    for i in range(n - 3):
        if i > 0 and nums[i] == nums[i - 1]:
            continue
        for j in range(i + 1, n - 2):
            l, r = j + 1, n - 1
            while l < r:
                current_sum = nums[i] + nums[j] + nums[l] + nums[r]
                if current_sum == k:
                    return True
                found_values.add((nums[i], nums[j], nums[l], nums[r]))
                if current_sum < k:
                    l += 1
                else:
                    r -= 1
    return False

print(four_sum_set_early_stop([1, 0, -1, 0, -2, 2], 0))

Output: True

This method sorts the array, uses a set to store quadruples, and avoids processing duplicates. It incorporates an early stopping rule when the sum is found, making it more efficient than previous brute-force approaches.

Bonus One-Liner Method 5: Python’s Combinations and Any

This succinct method uses Python’s itertools module to generate combinations of four elements from the list and then checks if any of these combinations sum to k. It’s compact and makes use of built-in functionality but is not efficient for large datasets.

Here’s an example:

from itertools import combinations

def four_sum_one_liner(nums, k):
    return any(sum(c) == k for c in combinations(nums, 4))

print(four_sum_one_liner([1, 0, -1, 0, -2, 2], 0))

Output: True

This one-liner makes use of the combinations method from Python’s itertools module, providing a convenient and terse way to generate all possible quadruples and then checks if any sum to k.

Summary/Discussion

  • Method 1: Brute Force. Simple to understand. Extremely slow for large inputs.
  • Method 2: Two-Pointer Technique. Improved efficiency using sorting. Not suitable for very large lists due to O(n^3) complexity.
  • Method 3: Hash Table. Offers good average-case performance. Requires additional space for the hash table.
  • Method 4: Set with Early Stopping. Similar efficiency to the hash table approach, but stops early if a solution is found. Avoids checking duplicates.
  • Method 5: Combinations and Any. Elegant one-liner. Not efficient for large datasets due to combinatorial explosion.