Two Sum II: Sorted Input
You get an array of integers numbers sorted in non-decreasing order, and an integer target. Exactly one pair of different positions holds two values that add up to target. Return those two positions as 0-based indices, the smaller index first.
Function
- numbersinteger-array
- the sorted array of integers
- targetinteger
- the sum the two values must reach
- Returnsinteger-array
- the two 0-based indices [i, j] with i < j and numbers[i] + numbers[j] == target
Constraints
2 ≤ numbers.length ≤ 104-5 × 108 ≤ numbers[i] ≤ 5 × 108-109 ≤ target ≤ 109numbersis sorted in non-decreasing order.- Exactly one pair of indices
i < jhasnumbers[i] + numbers[j] == target.
Examples
- Input
- numbers = [-4, 1, 3, 8, 12]target = 9
- Output
- [1, 3]
- Explanation
- 1 sits at index 1 and 8 at index 3, and 1 + 8 = 9. No other pair reaches 9: for example, -4 + 12 = 8.
- Input
- numbers = [2, 2, 5, 7]target = 4
- Output
- [0, 1]
- Explanation
- The two 2s at indices 0 and 1 are two different positions, so they may form the pair: 2 + 2 = 4.
- Input
- numbers = [-10, -3, 0, 6]target = -4
- Output
- [0, 3]
- Explanation
- -10 at index 0 and 6 at index 3 give -10 + 6 = -4. The answer can span the whole array.
Follow-up
Can you solve it in O(n) time with O(1) extra memory?
Hints
Open them one at a time. Each one gives away a little more.
The array is sorted. Look at the smallest and the largest value together. What does their sum tell you when it is below
target?If the first value plus the last value is too small, the first value is too small for every partner, because the last value is already the largest. You can rule it out.
Keep a pointer at each end. When the sum is too small, move the left pointer right; when it is too large, move the right pointer left. Stop when the sum equals
target.
Solution
The array is sorted, and that order tells you which way to move. Put a pointer at each end. If the sum is too small, only a larger left value can help; if too large, only a smaller right value can. Each step rules out one value for good, so one pass finds the pair with no extra memory.
Check every pair
Correct, but does not finish on the largest tests
Intuition
Try every pair of positions i < j and test whether numbers[i] + numbers[j] equals target. Since j starts right after i, the pair you find has the smaller index first.
It ignores the sorted order. With n = 10^4 there are about 5 × 10^7 pairs, and an answer near the end of the array means testing nearly all of them.
Algorithm
- Loop
iover every index. - Loop
jfromi+1to the last index. - If
numbers[i] + numbers[j]equalstarget, return[i, j].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n):
for j in range(i + 1, n):
if numbers[i] + numbers[j] == target:
return [i, j]
return []Binary search for each partner
Intuition
Once you fix numbers[i], its partner is exactly target - numbers[i]. The range right of i is sorted, so binary search tells you in O(log n) steps whether the partner is there. Searching only to the right keeps the smaller index first and stops a value from pairing with itself, and since the pair is unique, any match is the answer.
In the first example, i = 0 needs 13, which is missing; i = 1 needs 8, found at index 3. That is n searches of O(log n) each.
Algorithm
- Loop
ifrom 0 ton-2. - Compute
need = target - numbers[i]. - Binary search
needin the indicesi+1ton-1. - If you find it at
mid, return[i, mid].
def twoSumSorted(numbers, target):
n = len(numbers)
for i in range(n - 1):
need = target - numbers[i]
lo, hi = i + 1, n - 1
while lo <= hi:
mid = (lo + hi) // 2
if numbers[mid] == need:
return [i, mid]
if numbers[mid] < need:
lo = mid + 1
else:
hi = mid - 1
return []Two pointers from both ends
Intuition
Look at numbers[left] + numbers[right]. If it is too small, numbers[left] cannot be in the answer: even paired with the largest value still in play, it falls short. If it is too large, numbers[right] overshoots even with the smallest partner left. So each move discards a value that can never be in the pair, and never the pair itself. The pointers reach it after at most n-1 moves, with two variables.
On [-4, 1, 3, 8, 12] with target = 9: -4 + 12 = 8 is too small, so left moves to index 1. Then 1 + 12 = 13 is too large, so right moves to index 3. Now 1 + 8 = 9, and the answer is [1, 3].
Algorithm
- Set
leftto 0 andrightton-1. - While
left < right, computetotal = numbers[left] + numbers[right]. - If
totalequalstarget, return[left, right]. - If
totalis smaller, add 1 toleft; if larger, subtract 1 fromright.
def twoSumSorted(numbers, target):
left, right = 0, len(numbers) - 1
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left, right]
if total < target:
left += 1 # need a bigger sum
else:
right -= 1 # need a smaller sum
return []
Pitfalls and edge cases
- Returning 1-based positions. For
[-4, 1, 3, 8, 12]andtarget = 9the answer is[1, 3], not[2, 4]. In Lua and R, subtract 1 before you return. - Looping with
left <= right. When the pointers meet, the sum uses one value twice. - Moving the wrong pointer. A sum that is too small needs a larger value, and only
leftcan give one. - Rejecting duplicate values.
[2, 2, 5, 7]withtarget = 4uses both 2s, which sit at different positions.
Frequently asked questions3
What is the time complexity of Two Sum II?
The two pointer solution runs in O(n) time and O(1) extra space: each step moves one pointer inward, and they meet after at most n-1 steps. Binary searching each partner takes O(n log n), and checking every pair takes O(n²).
Why not use a hash map like in the first Two Sum?
A hash map works and also runs in O(n) time, but it stores up to n values. The sorted order makes that memory unnecessary: the two pointers know which way to move from the sum alone. Interviewers ask this version to see whether you use the order you were given.
When is binary search the better choice here?
When one value is fixed and you only need its partner. If numbers[0] must be in the pair, one binary search finds the other index in O(log n). To find an unknown pair, the two pointer scan is faster than n separate searches.
Similar problems
Problems that use the same ideas. Solving two or three of them is what makes a pattern stick.
def twoSumSorted(numbers, target):
# Write code hereTest #1
Test #2
Test #3
Arguments
numbers = [-4, 1, 3, 8, 12] target = 9
Expected Output
[1, 3]