💡 Problem Formulation: This article deals with the problem of identifying the maximum number of pairs in an array that add up to a given sum k. Given an array nums and an integer k, the goal is to find the maximum number of unique pairs (nums[i], nums[j]) where i != j and nums[i] + nums[j] == k. For example, given nums = [1, 2, 3, 4] and k = 5, the desired output is 2, corresponding to pairs (1, 4) and (2, 3).
Method 1: Brute Force Approach
This brute force approach involves checking all possible pairs in the array to count how many of them sum up to k. It is not the most efficient method, as it has a time complexity of O(n2), where n is the number of elements in the array.
Here’s an example:
def max_k_sum_pairs_brute(nums, k):
count = 0
pairs = set()
for i in range(len(nums)):
for j in range(i + 1, len(nums)):
if nums[i] + nums[j] == k and (i, j) not in pairs and (j, i) not in pairs:
pairs.add((i, j))
count += 1
return count
# Example usage:
print(max_k_sum_pairs_brute([1, 2, 3, 4], 5))Output:
2
In this code snippet, the function max_k_sum_pairs_brute is defined to find the maximum number of k-sum pairs using the brute force approach. It iterates over each possible pair in the array to see if they add up to k and ensures pairs are not counted twice by using a set to store already found pairs.
Method 2: Sorting and Two-Pointers Technique
The sorting and two-pointers technique improves over the brute force by first sorting the array and then using two pointers to find pairs. The efficiency of this method is O(nlogn) because of the sorting process, but the actual pair-finding is O(n).
Here’s an example:
def max_k_sum_pairs_two_pointers(nums, k):
nums.sort()
count = 0
left, right = 0, len(nums) - 1
while left < right:
current_sum = nums[left] + nums[right]
if current_sum == k:
count += 1
left += 1
right -= 1
elif current_sum < k:
left += 1
else:
right -= 1
return count
# Example usage:
print(max_k_sum_pairs_two_pointers([1, 2, 3, 4], 5))Output:
2
This function max_k_sum_pairs_two_pointers sorts the array and then uses a left and right pointer to efficiently find and count pairs that sum up to k. When a valid pair is found, both pointers are moved inward to continue searching for more pairs.
Method 3: Using a Hash Map
Using a hash map allows us to track the frequency of each number in the array, reducing the time complexity to O(n). This method is efficient for unsorted arrays and does not require altering the original array.
Here’s an example:
from collections import Counter
def max_k_sum_pairs_hashmap(nums, k):
count = 0
num_count = Counter(nums)
for num in nums:
complement = k - num
if num_count[complement] > 0 and num_count[num] > 0:
if num != complement or num_count[num] > 1:
count += 1
num_count[complement] -= 1
num_count[num] -= 1
return count // 2 # Pairs are counted twice
# Example usage:
print(max_k_sum_pairs_hashmap([1, 2, 3, 4], 5))Output:
2
This code snippet uses a Counter from the collections module to create a frequency map for the array elements. The function max_k_sum_pairs_hashmap iterates through the array and checks the hash map for a complement that, when paired with the current element, sums up to k. Each found pair is counted once, hence the final count is divided by two.
Method 4: Greedy with Sorted Counter
This method involves sorting a counter (frequency dictionary) and then iteratively reducing the frequency of encountered pairs. It is similar to using a hash map but incorporates sorting, which can be advantageous in certain cases for reducing the number of required operations.
Here’s an example:
from collections import Counter
def max_k_sum_pairs_greedy(nums, k):
count = 0
num_count = Counter(nums)
for num in sorted(num_count):
complement = k - num
pair_count = min(num_count[num], num_count[complement])
if num == complement:
pair_count //= 2
count += pair_count
num_count[num] -= pair_count
num_count[complement] -= pair_count
return count
# Example usage:
print(max_k_sum_pairs_greedy([1, 2, 3, 4], 5))Output:
2
The function max_k_sum_pairs_greedy sorts the keys of the frequency map and iteratively looks for complements. If it finds a valid complement, it greedily takes as many pairs as possible, taking into account the specific case where the number and its complement are the same.
Bonus One-Liner Method 5: Pythonic Approach with Counter
This one-liner approach exploits Python’s comprehension syntax and Counter to achieve the same result in a more concise manner, though it sacrifices a bit of readability.
Here’s an example:
from collections import Counter nums = [1, 2, 3, 4] k = 5 print(sum(min(Counter(nums)[i], Counter(nums)[k - i]) // (2 if i == k-i else 1) for i in set(nums)))
Output:
2
This one-liner uses a generator expression to iterate over unique elements in the array, counts how many times a number and its complement can form a pair, and sums up these counts. It includes conditionals to handle the case where a number can pair with itself.
Summary/Discussion
- Method 1: Brute Force Approach. Simple but inefficient for large arrays. The strength lies in its simplicity and the fact that it doesn’t require any additional data structures. Its weakness is the O(n2 ) time complexity.
- Method 2: Sorting and Two-Pointers Technique. More efficient than brute force, especially on sorted arrays. Strengths include better performance for larger data sets and being more intuitive after sorting. Weakness is that the initial sorting incurs O(nlogn) time complexity.
- Method 3: Using a Hash Map. Efficient and fast for large datasets, with a time complexity of O(n). The strength of this method is its efficiency and direct approach. However, it requires O(n) additional space for the hash map.
- Method 4: Greedy with Sorted Counter. Similar to Method 3 but may have a better practical performance in specific scenarios. Its strengths mirror those of Method 3 but with potentially fewer operations. Weakness includes additional complexity when dealing with the counter.
- Method 5: Pythonic Approach with Counter. Extremely concise and leverages Python features. Its strength is the concise and expressive code. The weakness is the lack of readability and potential performance hit due to the repeated creation of Counters.