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.
+13 hidden tests on Submit
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
A hash map solves the unsorted version in one pass, but it costs O(n) memory. Here the array is sorted, and that order tells you which way to move. Put one pointer at each end. If the sum is too small, only a larger left value can help; if it is 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 i runs from the left and j starts right after it, the first pair you find already has the smaller index first.
This is correct, but it ignores the sorted order. With n = 10^4 there are about 5 × 10^7 pairs, and when the answer sits near the end of the array you test nearly all of them. That is too slow for the large tests.
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 the first value numbers[i], you know its partner exactly: target - numbers[i]. The part of the array to the right of i is sorted, so binary search can tell you in O(log n) steps whether that partner is there.
For [-4, 1, 3, 8, 12] and target = 9: at i = 0 the partner would be 13, which is missing. At i = 1 the partner is 8, and the search finds it at index 3. The answer is [1, 3].
Searching only to the right of i keeps the smaller index first and stops a value from pairing with itself. The pair is unique, so the partner value appears at most once in that range and any match is the answer. In total: 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
Start with left = 0 and right = n-1 and look at numbers[left] + numbers[right]. If it equals target, you are done. If it is too small, numbers[left] cannot be part of the answer: even paired with the largest value still in play, it falls short. So move left right. If the sum is too large, numbers[right] cannot be part of it either, since even the smallest partner left overshoots. So move right left.
Each move throws away one value that can never be in the pair, and the pair itself is never thrown away. The pointers meet after at most n-1 moves, so the scan is O(n) and uses 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
The two pointer loop is short, so the bugs hide in the details around it.
- Returning 1-based positions. This version wants 0-based indices: 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 would use 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. - Overflow. The limits here keep every sum within a 32-bit integer. If values could reach
10^9, add them in a 64-bit type.
Frequently asked questions4
Why do two pointers work for Two Sum on a sorted array?
When the sum of the two ends is too small, the left value is too small for every partner still in play, because the right end is the largest of them. You can drop it for good. The same argument drops the right value when the sum is too large. The answer pair is never dropped, so the pointers end on it.
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.
Python
def twoSumSorted(numbers, target):
# Write code hereCase 1
Case 2
Case 3
Input
numbers = [-4, 1, 3, 8, 12] target = 9
Expected
[1, 3]