Finding Pairs with a Sum in Python

Imagine you have a list of numbers and you’re on a quest to find two special ones. These special numbers aren’t just any two numbers — they must add up to a specific target value. This seemingly simple problem has a wide range of applications, from finance and e-commerce to games and logistics. In this blog post, we’ll delve into efficient algorithms for finding these special pairs We’ll begin by discussing the limitations of a brute-force approach.

Problem

Suppose A = [a_1, ..., a_n] is an array of distinct integers and k is a given integer. The goal is to find two distinct elements from A whose sum is exactly k, or report that no such elements exist.

Hash Table

The algorithm used to solve this problem is known as the Hashing Approach. This approach leverages a hash set to efficiently find two distinct elements in an array that sum up to a given target value k.

• This approach utilizes a hash table to store the elements seen so far in the array.
• Iterate through the array:
• For each element a_i, calculate the complement k - a_i.
• Check if the complement exists in the hash table.
• If yes, it means you’ve found two elements (a_i and the one in the hash table) that sum to k. Return them (or a success flag).
• If no, add a_i to the hash table.
• If the loop completes without finding a complement, it means no such pair exists.

function twoSum(A, k):
  # Initialize an empty hash table
  hashTable = {}

  # Iterate through the array
  for a_i in A:
    complement = k - a_i

    # Check if the complement exists in the hash table
    if complement in hashTable:
      # Found a pair! Return them (or a success flag)
      return (a_i, hashTable[complement])
    else:
      # Add the current element to the hash table
      hashTable[a_i] = a_i

  # No pair found
  return "No such elements exist"

This code defines a function twoSum that takes the array A and the target sum k as input. It iterates through the array and for each element a_i, it calculates the complement needed to reach the target sum k.

If the complement exists in the hash table (meaning another element has already been seen that could form the pair), it returns the pair (a_i and the element from the hash table). Otherwise, it adds the current element a_i and its value (a_i) to the hash table. If the loop completes without finding a complement, it returns a message indicating no such pair exists.

Detailed Python Implementation

def two_sum(A, k):
  seen = {}
  pairs = []  # List to store all found pairs

  for number in A:
    complement = k - number

    # Check if the complement exists in the hash table (seen before)
    if complement in seen:
      # Found a pair! Add it to the pairs list
      pairs.append((number, A[seen[complement]]))
    else:
      # Add the current element to the hash table
      seen[number] = A.index(number)  # Store the index of the element

  return pairs  # Return the list of all found pairs

# Example usage (k=15)
A = [10, 15, 4, 7, 0, 11]
k = 15
pairs = two_sum(A, k)

if pairs:
  print("All possible pairs that sum to", k, "are:")
  for pair in pairs:
    print(pair)
else:
  print("There is no pair for", k, "in the array.")

# Example usage (k=17)
A = [10, 15, 4, 7, 0, 11]
k = 17
pairs = two_sum(A, k)

if pairs:
  print("All possible pairs that sum to", k, "are:")
  for pair in pairs:
    print(pair)
else:
  print("There is no pair for", k, "in the array.")

# Example usage (k=5)
A = [10, 15, 4, 7, 0, 11]
k = 5
pairs = two_sum(A, k)

if pairs:
  print("All possible pairs that sum to", k, "are:")
  for pair in pairs:
    print(pair)
else:
  print("There is no pair for", k, "in the array.")

• Set Initialization: An empty set seen is initialized to keep track of the numbers we've processed so far.
• Iterating Through the Array: We go through each element in the array.
• Complement Calculation: For each element a_i, we calculate the complement as k - a_i​.
• Complement Check: We check if the complement is in the seen set:
• If it is, it means the current element a_i​ and its complement k - a_i sum up to k. We return these two elements.
• If it is not, we add the current element a_i​ to the seen set.
• Completion: If we finish iterating through the array without finding any such pairs, we return “No such elements exist.”

Time Complexity

The time complexity of this algorithm is O(n), where nis the number of elements in the array. This is because we make a single pass through the array, and each lookup and insertion operation in the set takes O(n) time on average.

My YouTube Channel

More shell script videos and linux tutorials on my YouTube Channel.