5 Best Ways to Find Any Two Numbers Summing to K in Python Lists

Rate this post

πŸ’‘ Problem Formulation: You have been given a list of integers, and you’re required to find any two distinct numbers in that list which add up to a specified number k. For instance, if the input list is [1, 2, 3, 4] and k is 5, the output should be a tuple like (1, 4) or (2, 3).

Method 1: Brute Force

The brute force approach checks every possible pair of numbers in the list to see if they add up to k. This is done using nested loops. Although this method is straightforward and easy to implement, it is not optimal for large lists due to its O(n^2) time complexity.

Here’s an example:

def find_pair_brute_force(nums, k):
    for i in range(len(nums)):
        for j in range(i + 1, len(nums)):
            if nums[i] + nums[j] == k:
                return nums[i], nums[j]
    return None

pair = find_pair_brute_force([3, 4, 5, 6], 9)
print(pair)

Output: (3, 6)

This code snippet defines a function find_pair_brute_force which takes a list of numbers and the target sum k. It iterates over each element, using nested loops to check every pair’s sum. When a pair summing to k is found, it returns the pair, otherwise it returns None.

Method 2: Sorting and Two-Pointer Technique

This method involves sorting the list first, and then using a two-pointer technique where one pointer starts at the beginning and the other at the end of the sorted list. This method is more efficient with a time complexity of O(n log n) due to sorting.

Here’s an example:

def find_pair_two_pointer(nums, k):
    nums.sort()
    left, right = 0, len(nums) - 1
    while left < right:
        current_sum = nums[left] + nums[right]
        if current_sum == k:
            return nums[left], nums[right]
        elif current_sum < k:
            left += 1
        else:
            right -= 1
    return None

pair = find_pair_two_pointer([3, 4, 5, 6], 9)
print(pair)

Output: (3, 6)

The find_pair_two_pointer function sorts the list and initializes two pointers. It checks pairs and moves the pointers closer together until it finds a pair that adds up to k, at which point it returns the pair.

Method 3: Using a Hash Table

By using a hash table (dictionary in Python), we can store numbers we’ve visited and check if the complement (k – current number) exists in O(1) average time complexity. This results in an overall time complexity of O(n).

Here’s an example:

def find_pair_hash_table(nums, k):
    complements = {}
    for num in nums:
        if k - num in complements:
            return k - num, num
        complements[num] = True
    return None

pair = find_pair_hash_table([3, 4, 5, 6], 9)
print(pair)

Output: (3, 6)

In this snippet, the find_pair_hash_table function creates a dictionary to store elements as keys. During iteration, it checks if the complement of the current element to achieve k is already in the dictionary, and returns the pair if found.

Method 4: Binary Search for Complements

After sorting the list, we can use binary search to find the complement for each number, thus avoiding the two-pointer technique. This method has a time complexity of O(n log n) due to sorting and binary searching.

Here’s an example:

import bisect

def find_pair_binary_search(nums, k):
    nums.sort()
    for i in range(len(nums)):
        complement = k - nums[i]
        j = bisect.bisect_left(nums, complement, i+1)
        if j < len(nums) and nums[j] == complement:
            return nums[i], nums[j]
    return None

pair = find_pair_binary_search([3, 4, 5, 6], 9)
print(pair)

Output: (3, 6)

The find_pair_binary_search function sorts the list and then uses the Python bisect module for efficient binary searching. For each element in the list, it searches for its complement that would add up to the target sum k.

Bonus One-Liner Method 5: List Comprehension with a Set

As a quick solution, using list comprehensions combined with a set can find a pair that adds to k, although it lacks the efficiency of method three and four on larger lists due to creation of intermediary tuples.

Here’s an example:

def find_pair_set_comprehension(nums, k):
    nums_set = set(nums)
    pair = next(((num, k - num) for num in nums if (k - num) in nums_set), None)
    return pair

pair = find_pair_set_comprehension([3, 4, 5, 6], 9)
print(pair)

Output: (3, 6)

This one-liner find_pair_set_comprehension function converts the list to a set for faster lookups. Then, it uses list comprehension to iterate once through the numbers, checking for the presence of the complement in the set.

Summary/Discussion

  • Method 1: Brute Force. Simple to implement. Not recommended for large lists due to inefficiency.
  • Method 2: Sorting and Two-Pointer Technique. More efficient than brute force. Requires the list to be mutable for sorting.
  • Method 3: Using a Hash Table. Highly efficient with linear time complexity. Slightly more memory usage due to hash table.
  • Method 4: Binary Search for Complements. Efficient when dealing with sorted lists. Requires sorting step.
  • Method 5: List Comprehension with a Set. Elegant one-liner. Not as efficient as other methods on larger datasets due to the creation of intermediary tuples.