easyArraysPattern: Two Pointers
MatchingPairs Solution
Problem Statement
You are given two arrays of integers, `left` and `right`, where `left[i]` and `right[j]` represent the capacities of the i-th and j-th items, respectively. Find all pairs of items from `left` and `right` such that the sum of their capacities is equal to the target capacity of 947.
Examples
Example 1:
Input:{"left":[100,200,300],"right":[647,747,847]}
Output:[[100,847],[200,747],[300,647]]
Explanation: The pairs of items with total capacity 947 are (100, 847), (200, 747), and (300, 647).
Example 2:
Input:{"left":[10,20],"right":[937,947]}
Output:[[10,937]]
Explanation: The pair of items with total capacity 947 is (10, 937).
Example 3:
Input:{"left":[1000],"right":[0]}
Output:[]
Explanation: There are no pairs of items with total capacity 947.
Constraints
- 1 <= left.length, right.length <= 10^5
- -10^9 <= left[i], right[j] <= 10^9
- The target capacity is 947.
Time: O(n log n) Space: O(n)
Use the two-pointer technique with sorted arrays to achieve a time complexity of O(n log n).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def matching_pairs(left, right):
target = 947
result = []
left.sort()
right.sort()
i, j = 0, len(right) - 1
while i < len(left) and j >= 0:
if left[i] + right[j] == target:
result.append([left[i], right[j]])
i += 1
j -= 1
elif left[i] + right[j] < target:
i += 1
else:
j -= 1
return result