Skip to main content
Ace Hired
All coding problems

Two Sum II - Input Array Is Sorted

Mediumtwo pointersTwo pointerstwo-pointersarraysbinary-search

Maintained by Vikas D, software engineer

You are handed an array called numbers that is already sorted from smallest to largest, where equal values are allowed to sit next to each other. You also get a target value. Exactly one pair of entries in the array adds up to that target, and your job is to locate that pair.

The catch is what you return. Instead of the values themselves, you report the positions of the two entries, counted starting from 1 rather than 0. The smaller position comes first, so the answer is always [index1, index2] with index1 strictly less than index2.

The sorted order is the gift here. It lets you reason about whether a candidate sum is too big or too small and adjust which entries you are looking at, rather than checking every possible pair. The problem also asks for O(1) extra space, which rules out building any auxiliary lookup structure.

Examples

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]

The values at positions 1 and 2 are 2 and 7, and 2 + 7 equals 9, so the 1-based answer is [1, 2].

Input: numbers = [2, 3, 4], target = 6
Output: [1, 3]

2 at position 1 and 4 at position 3 sum to 6. The matching values sit at the two ends of the array.

Input: numbers = [-1, 0], target = -1
Output: [1, 2]

With only two values, -1 + 0 already equals the target, so both positions are part of the pair.

Constraints

  • 2 <= numbers.length <= 3 * 10^4
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order
  • -1000 <= target <= 1000
  • Exactly one valid pair exists
  • Return 1-based indices and use O(1) extra space

Visible test cases

  • twoSumSorted([2,7,11,15], 9) == [1,2]
  • twoSumSorted([2,3,4], 6) == [1,3]
  • twoSumSorted([3,24,50,79,88,150,345], 200) == [3,6]
  • twoSumSorted([-1,0], -1) == [1,2]
  • twoSumSorted([1,2,3,4,5], 9) == [4,5]
  • twoSumSorted([0,0,3,4], 0) == [1,2]

Hints

Hint 1

The array being sorted is not just decoration. If a sum of two values is too large, which one should you shrink, and if it is too small, which one should you grow?

Hint 2

Place one marker at the front and one at the back. The front value is the smallest available and the back value is the largest, so their sum brackets the range of reachable sums.

Hint 3

Compare the current sum to the target: too small means move the left marker rightward to a bigger value, too large means move the right marker leftward to a smaller value. Stop when they meet in the middle.

Loading the editor...

Approaches

Brute force pairs

Time O(n^2) · Space O(1)

Ignore the sorted order and simply try every pair of positions, checking whether the two values add up to the target.

  1. Loop i over each index from the start.
  2. For each i, loop j over every later index.
  3. If numbers[i] + numbers[j] equals target, return [i + 1, j + 1] to convert to 1-based.
  4. Because a solution is guaranteed, the loops will always find it before ending.

Two pointers from both ends

Time O(n) · Space O(1)

Since the array is sorted, a sum that is too small can only grow by advancing the low end, and a sum that is too large can only shrink by pulling in the high end, so a single sweep finds the pair.

  1. Set lo to the first index and hi to the last index.
  2. While lo is less than hi, compute sum = numbers[lo] + numbers[hi].
  3. If sum equals target, return [lo + 1, hi + 1].
  4. If sum is less than target, increment lo to reach a larger value.
  5. If sum is greater than target, decrement hi to reach a smaller value.
  6. The pointers converge in at most n steps and the guaranteed pair is found along the way.

Common mistakes

  • Returning 0-based positions. The problem counts from 1, so add 1 to each pointer before returning.
  • Returning the values numbers[lo] and numbers[hi] instead of their indices.
  • Reaching for a hash map keyed by value. It works but uses O(n) extra space, which the constant-space requirement forbids, and the sorted input makes it unnecessary.
  • Moving the wrong pointer: shrinking the high end when the sum is already too small only makes it smaller and skips the answer.
  • Looping while lo <= hi instead of lo < hi, which lets a single element pair with itself.

Follow-up variations

  • What changes if the array can contain more than one valid pair and you must return all of them?
  • How would you handle an unsorted input array while still aiming for better than quadratic time?
  • Could you adapt the two-pointer idea to find three numbers that sum to the target?
  • If the array were enormous and stored on disk so random access was costly, how would your approach change?

Recommended problems

Build the rest of your prep