medium

Two Sum II - Input Array Is Sorted

Find two numbers in a sorted array that add up to a target value.

1. Define the problem

Two Sum II - Input Array Is Sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order , find two numbers such that they add up to a specific target number. Let these two numbers be numbersindex1 and numbersindex2 where 1 ≤ index1 < index2 ≤ numbers.length. Return the indices of the two numbers, index1 and index2, added by one as an integer array [index1, index2] of length 2. The tests are generated so that there is exactly one solution, and you may not use the same element twice. Start pointers at both ends and converge them inward based on whether the current sum is too small or too large.

Constraints

  • 2 ≤ numbers.length ≤ 3 × 104
  • -1000 ≤ numbersi ≤ 1000
  • numbers is sorted in non-decreasing order.
  • -1000 ≤ target ≤ 1000
  • The tests are generated such that there is exactly one solution.

Example

Inputnumbers = [2, 7, 11, 15], target = 9
Output[1, 2]

Explanation numbers0 + numbers1 = 2 + 7 = 9, so index1 = 1 and index2 = 2 (1-indexed).

2. Visualize the solution

Converge two pointers from both ends

Converge two pointers from both ends
Statusinit

left=2 (idx 0), right=15 (idx 3): sum = 17 > 9, move right inward.

What happens in this step

Step 1 of 3
Steps to visualize
  1. Point left at the first element and right at the last.
  2. Compute the sum of the two pointed-at values.
  3. If the sum is too small, move left one step right to increase it.
  4. If the sum is too large, move right one step left to decrease it.
  5. Stop the moment the sum equals target and return the 1-indexed positions.
3. Walk through the code
Walk through the code
Same walkthrough, now with the code. Press Next to move one step and watch which lines run.
Converge two pointers from both ends
Statusinit
left=2 (idx 0), right=15 (idx 3): sum = 17 > 9, move right inward.
What happens in this step
Step 1 of 3
4. Solution
Solution
solution.tsTypeScript
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];
    } else if (sum < target) {
      left++;
    } else {
      right--;
    }
  }

  return [];
}
Time
O(n)
Space
O(1)
5. Test cases
Test cases
InputExpectedCovers
numbers = [2, 7, 11, 15], target = 9[1, 2]example from the docstring
numbers = [1, 2], target = 3[1, 2]smallest valid input: only two elements
numbers = [-7, -3, 4, 9, 15], target = 6[2, 4]negative and positive numbers mixed in the same array
numbers = [-5, -2, -1, 3, 8], target = -6[1, 3]a negative target value
numbers = [0, 0, 3, 4], target = 0[1, 2]duplicate values that themselves sum to the target
numbers = [1, 3, 3, 6], target = 6[2, 3]duplicate non-zero values that are the unique solution
Keep reading