The list is sorted, so start one pointer at each end. If the pair adds up too small, move the left one right; too big, move the right one left. Each step rules out a whole row of pairs: O(n) time, O(1) space.
▼The problem
LeetCode 167 (Medium). Given a 1-indexed array numbers sorted in non-decreasing order and a target, return the positions [index1, index2] (1-indexed, index1 < index2) of the two numbers that add up to target. Exactly one solution exists, the same element can't be used twice, and only O(1) extra space is allowed.
Examples (LeetCode's): [2,7,11,15], 9 → [1,2]; [2,3,4], 6 → [1,3] (both shown in scene 2); [-1,0], -1 → [1,2] (checked, not shown).
The solution
def twoSum(numbers, target):
l, r = 0, len(numbers) - 1
while l < r:
s = numbers[l] + numbers[r]
if s == target:
return [l + 1, r + 1]
if s < target:
l += 1
else:
r -= 1Transcript
Two Sum Two. The numbers come sorted, smallest first. Find the two that add up to a target, and return their positions, counting from one. Exactly one pair works. Use only constant extra space.
Take two, seven, eleven, fifteen, with target nine. Two plus seven is nine, so the answer is one, two. With two, three, four and target six, it's one, three.
The slow way tries every pair, about n squared sums. A hash map, like in Two Sum, is fast but needs extra memory, which isn't allowed here.
Instead, use the order. Point at the smallest number and the largest. If their sum is too small, the left number can't work even with the biggest, so move left forward. If it's too big, the right number is too big even with the smallest, so move right back. If it's equal, we're done.
In code, loop while left is before right: add the two, return both positions plus one if it matches, otherwise step the pointer that's wrong.
Try one, three, four, six, eight, eleven, with target ten. One plus eleven is twelve: too big, so eleven goes. One plus eight is nine: too small, so one goes. Three plus eight is eleven: eight goes. Three plus six is nine: three goes. Four plus six is ten. The answer is three, four.
Every step crosses out a whole row or column of pairs, so at most n steps. Linear time, and two pointers: constant space.
Start at both ends, compare, move the side that's off. That's Two Sum Two.