Two Sum II - Input Array Is Sorted

MediumTwo PointersArrayTwo PointersBinary Search

Problem

You are given an array of integers already sorted in ascending order, along with a target value. Find the two entries that add up to the target and return their positions, counting from 1. Exactly one valid pair exists, and you may not reuse the same element twice.

Example. For the sorted array [2, 7, 11, 15] with target 9, the answer is positions 1 and 2, since 2 + 7 = 9.

Key idea

Ignoring the sorted order and scanning every pair would cost O(n²), the same as the unsorted version of this problem. But sortedness gives you something a plain hash-map scan cannot: a sense of direction. Place one pointer at the first element and another at the last. Their sum is either exactly the target, too small, or too large. If it is too large, the right pointer must move left, since the right element is already the largest value that could pair with anything to its left. If the sum is too small, the left pointer must move right for the mirror reason. Repeating this narrows the search by one element from whichever side is wrong at each step, and the true pair is never skipped by this reasoning.

Solution

function twoSum(numbers: number[], target: number): number[] {
  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]; // convert to 1-indexed positions
    } else if (sum > target) {
      right--; // sum too large, shrink from the right
    } else {
      left++; // sum too small, grow from the left
    }
  }

  return [];
}

Complexity

  • Time: O(n). Each pointer moves inward at most n times combined.
  • Space: O(1). Only two index variables are used.

Watch out for

  • The result is 1-indexed, not 0-indexed, so add one to each raw array position before returning.
  • Keep the left pointer strictly less than the right pointer so the same element is never paired with itself.
  • This shortcut depends on the array being sorted; on an unsorted array a hash map of complements is the right tool instead.

Pattern

This is the sorted-array two-pointer convergence pattern, which trades the extra memory of a hash map for the monotonic structure that sorting provides. The same left/right narrowing shows up whenever a problem asks for pairs or triplets with an additive constraint over sorted data, such as 3Sum.

Related questions