mediumTwo PointersPattern: Mixed
Pair Sum Combinations Solution
Problem Statement
Given an array of distinct integers `numbers` and a target sum `sumTarget`, find all pairs of unique elements in `numbers` that add up to `sumTarget`. Return the pairs of elements that sum up to `sumTarget`.
Examples
Example 1:
Input:{"numbers":[1,2,3,4,5],"sumTarget":7}
Output:[[2,5],[3,4]]
Explanation: The pairs (2, 5) and (3, 4) sum up to 7.
Example 2:
Input:{"numbers":[-1,0,1],"sumTarget":0}
Output:[[-1,1]]
Explanation: The pair (-1, 1) sums up to 0.
Constraints
- 1 <= length of `numbers` <= 10^4
- -10^9 <= each element in `numbers` <= 10^9
- 1 <= `sumTarget` <= 2 * 10^9
Time: O(n log n) Space: O(1)
An optimized approach uses the two-pointer technique, where the array is first sorted, and then two pointers are initialized, one at the start and one at the end of the array. The sum of the elements at these pointers is compared to the target sum, and the pointers are moved accordingly to find pairs that sum up to the target. This approach has a time complexity of O(n log n) due to the sorting.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
import sys
def find_pairs(numbers, sum_target):
numbers.sort()
left = 0
right = len(numbers) - 1
pairs = []
while left < right:
sum = numbers[left] + numbers[right]
if sum == sum_target:
pairs.append([numbers[left], numbers[right]])
left += 1
right -= 1
elif sum < sum_target:
left += 1
else:
right -= 1
return \n.join(map(lambda pair: " ".join(map(str, pair)), pairs))
numbers = list(map(int, input().split()))
sum_target = int(input())
print(find_pairs(numbers, sum_target))