Two Sum II - Input Array Is Sorted
Sorted input lets two pointers steer toward the target.
Two-Pointer Trace
Problem
You are given a non-decreasing array and a target value. Find the two distinct positions whose values add up to the target, and return their positions using one-based indexing. Every input has exactly one valid pair.
Examples
Input: numbers = [2, 3, 4, 8, 11, 15], target = 15
Output: [3, 5]
Input: numbers = [1, 2, 6, 9], target = 8
Output: [2, 3]
The Goal
Find two different entries that add up to target, and return their positions counting from 1.
For numbers = [2, 3, 4, 8, 11, 15] and target = 15, the pair is 4 + 11. They sit at indices 2 and 4, so the answer is [3, 5].
The array is sorted, and the whole solution depends on that.
Sorted order lets you steer
The smallest number is on the left and the largest is on the right. Move right left and the sum shrinks. Move left right and it grows.
Sorted order does the job a hash map would.
Key Idea: Steer the Sum
Put left on the first number and right on the last.
If the sum is too big, even the smallest number left is too big with numbers[right]. That number can't be in the answer, so move right left.
If the sum is too small, even the largest number left is too small with numbers[left]. Move left right.
Each move rules out every pair that uses the number you leave behind.
Move right left. The numbers get smaller that way.
2 + 15 = 17, more than 15
The Algorithm
Start with left = 0 and right = len(numbers) - 1. Each pass compares the two ends, then moves one of them inward.
while left < right:
total = numbers[left] + numbers[right]
if total == target:
return [left + 1, right + 1]
if total > target:
right -= 1
else:
left += 1Use left < right, not <=. The two entries have to be different.
| Approach | Time | Space | How |
|---|---|---|---|
| Hash map | O(n) | O(n) | Remembers each number's complement |
| Two pointers | O(n) | O(1) | Steers the sum with sorted order |
Walkthrough
Run it on [2, 3, 4, 8, 11, 15] with target = 15.
The sums go 17, 13, 14, 15. The first is too big, so right drops from 15 to 11. The next two are too small, so left climbs from 2 to 4. Then 4 + 11 hits 15, and the answer is [3, 5].
If a pair exists, it's always between the pointers. Change the numbers on the stage and watch that hold.
Checkpoint · predict the next step
Step 4 of 9 on the stage: Add the two ends: 2 + 11 = 13.
left on 2 (index 0) · right on 11 (index 4) · target 15 · sum 13
Pitfalls
- The steering rule needs sorted input. On an unsorted array it moves the wrong way.
- Move one pointer per step. Only one move is ever justified.
- Return
[left + 1, right + 1]. The problem counts from 1. - Stop when the pointers meet. An entry can't pair with itself.
A hash map gets the right answer too, but it spends O(n) memory that sorted order makes unnecessary.
The pointers are on 2 and 15, and the target is 15. Which move is right?
Complexity
Each step moves one pointer inward, so they meet after at most n - 1 moves. That's O(n) time. You keep two indices and a sum, so extra space is O(1).
Sorted input doesn't make this O(log n). The pointers still walk the array one step at a time.
Two pointers against a hash map
- Scan with two pointersEach pointer only moves inward.dominantO(n)
- Pointer stateTwo indices and a sum.O(1)
- Hash map insteadMemory that sorted order makes unnecessary.dominantO(n)
| n | 10 | 100 | 1,000 | 10,000 |
|---|---|---|---|---|
| O(n) | 10 | 100 | 1K | 10K |
One pass and constant extra memory.
In short
Start pointers at both ends. If their sum is too big, move the right pointer left; if too small, move the left pointer right. The sorted order guarantees each move discards only impossible pairs, so you find the answer in one pass with no extra memory.
Common mistake
Reusing the hash-map approach from Two Sum — it works but ignores the sorted structure that enables O(1) space here.