💡 Problem Formulation: You need to determine if any two distinct elements within an array add up to a specific target value. For example, given the array [5, 3, 9, 1] and the target value 10, your program should confirm that the elements 1 and 9 sum up to 10.
Method 1: Brute Force Approach
This method involves checking every possible pair in the array to see if they sum up to the target value. The function has_pair_with_sum_brute_force() iterates over each element and checks its sum with every other element.
Here’s an example:
def has_pair_with_sum_brute_force(arr, target):
for i in range(len(arr)):
for j in range(i+1, len(arr)):
if arr[i] + arr[j] == target:
return True
return False
print(has_pair_with_sum_brute_force([5, 3, 9, 1], 10))Output: True
This code snippet is straightforward: it iterates over each element, then checks against all other elements following it in the list until a pair sums to the target value, returning True. If no pair sums to the target, it returns False.
Method 2: Using Sets for Lookup
The function has_pair_with_sum_set() uses a set to store the complements of the target value minus each element, allowing us to check in constant time whether we’ve already encountered an element which, when added to the current one, equals the target value.
Here’s an example:
def has_pair_with_sum_set(arr, target):
seen = set()
for num in arr:
if target - num in seen:
return True
seen.add(num)
return False
print(has_pair_with_sum_set([5, 3, 9, 1], 10))Output: True
This code snippet efficiently checks for a complement pair by keeping track of what numbers we’ve seen. It’s faster than the brute force method, because set lookup is generally O(1).
Method 3: Sorting and Pointers
By sorting the array first, you can use two pointers to find a pair of numbers which sum to the target value. The function has_pair_with_sum_pointers() increases the lower pointer or decreases the upper pointer based on the sum comparison.
Here’s an example:
def has_pair_with_sum_pointers(arr, target):
arr.sort()
low, high = 0, len(arr) - 1
while low < high:
if arr[low] + arr[high] == target:
return True
elif arr[low] + arr[high] < target:
low += 1
else:
high -= 1
return False
print(has_pair_with_sum_pointers([5, 3, 9, 1], 10))Output: True
In this snippet, we sort the array, then use two pointers to scan from both ends of the array, calculating the sum and moving the pointers appropriately until a matching pair is found or the pointers cross.
Method 4: Using HashMaps for Counting
Similar to using sets, the has_pair_with_sum_hashmap() function uses a hashmap (or a dictionary in Python) to count occurrences, then checks if the complement of each element (which is target minus the element) exists in the hashmap.
Here’s an example:
def has_pair_with_sum_hashmap(arr, target):
counts = {}
for num in arr:
if target - num in counts:
return True
counts[num] = counts.get(num, 0) + 1
return False
print(has_pair_with_sum_hashmap([5, 3, 9, 1], 10))Output: True
This code employs a dictionary to track the occurrences of each number. It looks to see if there is a number already seen that would complement the current number to equal the target.
Bonus One-Liner Method 5: Using Python’s Comprehensions and any()
A compact way to achieve our goal is to use a generator expression together with Python’s built-in any() function, which immediately stops and returns True if any iteration is True.
Here’s an example:
print(any(True for i in range(len(arr)) for j in range(i+1, len(arr)) if arr[i] + arr[j] == target))
Assuming arr and target are predefined, this one-liner checks all unique pairs to see if they equal the target.
This approach is a concise way of writing the brute force solution, but it doesn’t offer any performance benefits and can be less readable, especially for those not familiar with comprehensions or the any() function.
Summary/Discussion
- Method 1: Brute Force Approach. Simple and direct. Poor performance with O(n^2) time complexity.
- Method 2: Using Sets for Lookup. Much faster than brute force, with average case O(n) time complexity. However, it requires additional space for the set.
- Method 3: Sorting and Pointers. Efficient with O(n log n) due to the sorting overhead, but doesn’t require extra space.
- Method 4: Using HashMaps for Counting. Similar to sets for lookup, offering a good balance of speed and readability.
- Bonus Method 5: Comprehensions and any(). Elegant one-liner. Suitable for short lists or when performance is not a concern.