Pair sum in a sorted array
Walk inward from both ends. About 8 minutes.
Two fingers, walking towards each other
You have a sorted list of prices and a gift card worth exactly 10. Which two items use it up exactly?
Put one finger on the cheapest item and one on the most expensive, and add them. Too much? The expensive one has to go, so move the right finger one step left. Too little? The cheap one has to go, so move the left finger one step right. Keep going until the two prices add up to 10.
1 + 11 = 12 is too big, so right moves one step left.
Why every move is safe
When the sum is too big, the right-hand item can't be in the answer. Even paired with the cheapest item left, it's too much, so pairing it with anything else is worse. You can drop it for good. The same goes for the left item when the sum is too small.
So every move rules out one item forever, and after at most n moves you're done. Checking every pair instead would take about n × n.
left, right = 0, len(nums) - 1
while left < right:
total = nums[left] + nums[right]
if total == target:
return [left, right]
if total < target:
left += 1
else:
right -= 1The sum is 12 and the target is 10. Which finger moves?
1, 3, 4, 6, 8, 11 · left finger on 1, right finger on 11
- AThe left finger, one step right
- BThe right finger, one step left
- CBoth fingers
Show the answer
The right finger, one step left. The sum is too big, so swap the 11 for something smaller.
Pair sum in a sorted array
You get numbers sorted from smallest to largest, and a target. Return the positions of the two numbers that add up to the target. There is always exactly one answer.
nums = [1, 3, 4, 6, 8, 11], target = 10 → [2, 3]
2 ≤ n ≤ 1,000,000 · sorted ascending · exactly one answer