Two Sum II

Try It Yourself

Use the editor below to find the target pair without building a lookup map. Use the array's sorted order to decide which pointer should move after each sum.

Submit your implementation when it passes the examples. Return one-based indices and handle negative and duplicate values.

Two Sum II — Input Array Is Sorted

mediumTwo Pointers · Arrays25 minLC 167

Problem

Given a one-indexed array of integers sorted in non-decreasing order and a target, find two different values that add up to the target.

Return their one-based indices as [index1, index2], with index1 smaller than index2.

Example 1:

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

Output: [1, 2]

Example 2:

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

Output: [1, 3]

Constraints

2 ≤ numbers.length ≤ 30,000
Exactly one solution exists.

0 attempts

Solution

Place one pointer at each end of the sorted array. If their sum is too small, moving the left pointer right is the only way to increase it. If it is too large, move the right pointer left.

When the sum equals the target, convert both zero-based positions to the required one-based indices.

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

  return [];
}

Big O notation

Measure	Complexity	Explanation
Time	`O(n)`	Each pointer moves inward at most n positions.
Auxiliary space	`O(1)`	Only two pointer indices and the current sum are stored.