Finding pairs that sum to a specific target value is a common problem in programming interviews and data analysis.
This article provides multiple methods in Python to efficiently identify all unique pairs within a list that add up to the target sum. We’ll explore different approaches, from brute-force techniques to more optimized solutions using sets and dictionaries, along with detailed code examples and explanations of the Python code.
Learn how to use Python to solve this problem using several Python techniques for efficient pair finding.
For example, given the list [1, 2, 3, 4, 5] and a target sum of 6, the desired output would be [(1, 5), (2, 4)].
Input: nums = [1, 2, 3, 4, 5], target = 6 Output: [(1, 5), (2, 4)]
Method 1: Brute Force Approach
The brute-force method involves iterating through all possible pairs in the list and checking if their sum equals the target. This is the simplest approach to understand, but it’s also the least efficient for large lists because it has quadratic time complexity.
def find_pairs_brute_force(nums, target):
pairs = []
n = len(nums)
for i in range(n):
for j in range(i + 1, n):
if nums[i] + nums[j] == target:
pairs.append((nums[i], nums[j]))
return pairs
nums = [1, 2, 3, 4, 5]
target = 6
result = find_pairs_brute_force(nums, target)
print(result)
[(1, 5), (2, 4)]
Explanation: This code iterates through each element nums[i] and then, for each element, iterates through the rest of the list nums[j] (where j > i to avoid duplicates). If the sum of nums[i] and nums[j] equals the target, the pair (nums[i], nums[j]) is added to the pairs list.
Method 2: Using a Set to Optimize
This method improves efficiency by using a set to store the numbers we’ve encountered. For each number in the list, we check if its complement (target - number) is in the set. If it is, we’ve found a pair. This reduces the time complexity to O(n).
def find_pairs_with_set(nums, target):
seen = set()
pairs = []
for num in nums:
complement = target - num
if complement in seen:
pairs.append((num, complement))
seen.add(num)
return pairs
nums = [1, 2, 3, 4, 5]
target = 6
result = find_pairs_with_set(nums, target)
print(result)
[(5, 1), (4, 2)]
Explanation: The code iterates through the nums list. For each num, it calculates the complement needed to reach the target sum. It then checks if the complement is already in the seen set. If it is, a pair is found, and added to the pairs list. Finally, it adds the current num to the seen set to check for its complement later in the list. This approach drastically improves performance by reducing the search time for each complement.
Method 3: Using a Dictionary (Hash Map)
A dictionary (or hash map) can be used to store the frequency of each number in the list. This method allows us to quickly check if the complement exists and also handles cases where the same number can form a pair with itself if the target is even.
def find_pairs_with_dict(nums, target):
num_counts = {}
pairs = []
for num in nums:
complement = target - num
if complement in num_counts:
pairs.append((num, complement))
if num in num_counts:
num_counts[num] += 1
else:
num_counts[num] = 1
return pairs
nums = [1, 2, 3, 4, 5]
target = 6
result = find_pairs_with_dict(nums, target)
print(result)
[(5, 1), (4, 2)]
Explanation: This method uses a dictionary num_counts to store the count of each number encountered. When iterating through the nums list, the code calculates the complement required to reach the target. If the complement is in the num_counts dictionary, a pair is found and added to the pairs list. The frequency of the current num is then updated in the num_counts dictionary to keep track of each number’s occurrence.
Method 4: Two Pointer Approach (For Sorted Lists)
If the list is sorted, we can use the two-pointer approach for a more efficient solution. We start with two pointers, one at the beginning and one at the end of the list. We adjust the pointers based on whether the sum of the pointed numbers is less than, greater than, or equal to the target.
def find_pairs_two_pointers(nums, target):
nums.sort() # Ensure the list is sorted
left = 0
right = len(nums) - 1
pairs = []
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == target:
pairs.append((nums[left], nums[right]))
left += 1
right -= 1
elif current_sum < target:
left += 1
else:
right -= 1
return pairs
nums = [1, 5, 2, 4, 3] # Unsorted list
target = 6
result = find_pairs_two_pointers(nums, target)
print(result)
[(1, 5), (2, 4)]
Explanation: First, the list nums is sorted. Then, two pointers, left and right, are initialized to the start and end of the list, respectively. The code enters a while loop that continues as long as left is less than right. Inside the loop, the sum of the numbers at the left and right pointers is calculated. If the current_sum is equal to the target, the pair is added to the pairs list, and both pointers are moved one step closer to the center. If the current_sum is less than the target, the left pointer is moved to the right to increase the sum. If the current_sum is greater than the target, the right pointer is moved to the left to decrease the sum. This method is efficient for sorted lists, with a time complexity of O(n log n) due to the sorting step, but the two-pointer iteration is O(n).