Two Sum on a Sorted Array
Find two numbers in a sorted array that add up to a target using two pointers, in O(n) time and O(1) space, with a proof of why it works.
Updated Quick read: 3 min read
Approaches at a glance
| Approach | Time | Space |
|---|---|---|
| Hash map | O(n) | O(n) |
| Two pointers | O(n) | O(1) |
The problem
You are given an array of integers sorted in ascending order and a target number. Exactly one pair of elements adds up to the target. Return the positions of that pair, counting from 1 rather than 0, and use only constant extra space.
numbers = [2, 7, 11, 15], target = 9 → [1, 2] (2 + 7)
numbers = [2, 3, 4], target = 6 → [1, 3] (2 + 4)
numbers = [-1, 0], target = -1 → [1, 2] (-1 + 0)Approach 1: hash map
The hash map solution to Two Sum works on any array, sorted or not: O(n) time, O(n) space. But it ignores the fact that the input is sorted, and it breaks the constant-space requirement.
Approach 2: two pointers
Put one pointer on the smallest number and one on the largest, and look at their sum.
- If the sum equals the target, that is the answer.
- If the sum is too small, move the left pointer right to get a larger number.
- If the sum is too large, move the right pointer left to get a smaller number.
JavaScript
function twoSumSorted(numbers, target) {
let left = 0;
let right = numbers.length - 1;
while (left < right) {
const sum = numbers[left] + numbers[right];
if (sum === target) return [left + 1, right + 1];
if (sum < target) {
left++;
} else {
right--;
}
}
return [];
}Python
def two_sum_sorted(numbers, target):
left = 0
right = len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
if total < target:
left += 1
else:
right -= 1
return []Walkthrough
numbers = [1, 3, 4, 6, 8, 11], target = 10:
| left | right | Sum | Action |
|---|---|---|---|
| 0 (1) | 5 (11) | 12 | Too large, move right |
| 0 (1) | 4 (8) | 9 | Too small, move left |
| 1 (3) | 4 (8) | 11 | Too large, move right |
| 1 (3) | 3 (6) | 9 | Too small, move left |
| 2 (4) | 3 (6) | 10 | Found: return [3, 4] |
Time O(n): every step moves one pointer, and they meet after at most n steps. Space O(1).
Why no pair is missed
It can look as if moving a pointer skips pairs that were never checked. It does, but only pairs that cannot be the answer.
Suppose the sum is too small. numbers[right] is the largest number still in play, so numbers[left] plus anything else available is no larger than the current sum, and is too small as well. numbers[left] cannot be in the answer, so dropping it loses nothing. The same reasoning removes numbers[right] when the sum is too large.
The full argument is in the two pointers pattern.
Try it yourself
Copy a solution from above, add the lines below, and run it. For JavaScript, paste both into the browser console, or save them in a file and run it with node. For Python, save them in a file and run it with python.
JavaScript
console.log(twoSumSorted([2, 7, 11, 15], 9)); // [1, 2]
console.log(twoSumSorted([2, 3, 4], 6)); // [1, 3]Python
print(two_sum_sorted([2, 7, 11, 15], 9)) # [1, 2]
print(two_sum_sorted([2, 3, 4], 6)) # [1, 3]The comment after each line is the result you should see.
Common mistakes
- Returning 0-based indexes. This problem asks for positions starting at 1, hence the
+ 1. - Using
left <= right. When the pointers meet they point at one element, and one element is not a pair. - Applying this to an unsorted array. The rule for moving pointers is only valid when the array is sorted.
Original problem: LeetCode 167: Two Sum II - Input Array Is Sorted