Two Sum II - Input Array Is Sorted

Difficulty: Medium

You're given a list of numbers that is already sorted in increasing order, and a target number. Find two different numbers in the list that add up exactly to the target, and return their positions.

There's a small twist compared to the usual Two Sum: positions here are counted starting from 1, not 0. You can assume there's always exactly one valid pair, you can't reuse the same element twice, and — since the list is already sorted — you should be able to solve this using only a constant amount of extra space.

Examples

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

numbers[0] + numbers[1] = 2 + 7 = 9, and using 1-based positions that's [1, 2].

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

2 + 4 = 6, which are positions 1 and 3.

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

Constraints

2 <= numbers.length <= 3 * 10^4
-1000 <= numbers[i] <= 1000
numbers is sorted in non-decreasing order.
Exactly one valid answer exists.

Approach

Because the list is sorted, you get a useful guarantee: moving the left pointer forward can only increase the sum, and moving the right pointer backward can only decrease it. That means you never have to backtrack — you always know exactly which pointer to move next.

Start with one pointer at the very first number and one at the very last. If their sum is too small, the only way to increase it is to move the left pointer forward (to a bigger number). If it's too big, move the right pointer backward (to a smaller number). If it matches, you're done. This finds the answer in a single pass, using no extra memory beyond the two pointers.

Solutions

Brute Force — Check Every Pair

Try every possible pair of positions and check whether they sum to the target. Correct, but it doesn't use the fact that the list is sorted at all.

function twoSum(numbers, target) {
  for (let i = 0; i < numbers.length; i++) {
    for (let j = i + 1; j < numbers.length; j++) {
      if (numbers[i] + numbers[j] === target) {
        return [i + 1, j + 1];
      }
    }
  }
  return [];
}

Time: O(n²) · Space: O(1)

Hash Map

Walk through the list once, and for each number check whether the value needed to complete the pair has already been seen, using a Map for instant lookups. This ignores the sorted order and uses O(n) extra memory, but it's faster than the brute force.

function twoSum(numbers, target) {
  const seen = new Map(); // value -> index

  for (let i = 0; i < numbers.length; i++) {
    const complement = target - numbers[i];
    if (seen.has(complement)) {
      return [seen.get(complement) + 1, i + 1];
    }
    seen.set(numbers[i], i);
  }

  return [];
}

Time: O(n) · Space: O(n)

Optimal — Two Pointers

Take advantage of the sorted order directly. Start one pointer at each end of the list, and move whichever pointer will move the sum in the right direction: forward from the left if the sum is too small, backward from the right if it's too big.

function twoSum(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];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return [];
}

Time: O(n) · Space: O(1)