12. Two Sum II (Sorted Input) · DSA Practice

numbers is sorted in non-decreasing order. Find the two numbers that add up to target and return their positions 1-indexed as [index1, index2] with index1 < index2. Exactly one solution exists. Use only O(1) extra space.

Example 1

Input: numbers = [1,3,4,5,9], target = 10

Output: [1,5]

Explanation: 1 + 9 = 10, at positions 1 and 5.

Example 2

Input: numbers = [-4,-1,0,5], target = -5

Output: [1,2]

Hint 1

Start with the smallest and largest numbers.

Hint 2

If the sum is too small, only moving the left pointer can increase it.

Two PointersBinary Search

Approach 1: Binary search

For each element, binary-search its partner.

⏱ Time O(n log n)💾 Space O(1)

Approach 2: Two pointers ✅

Move lo right when the sum is too small and hi left when it is too big.

⏱ Time O(n)💾 Space O(1)

Reference solution for Two pointers (time O(n), space O(1)). Each solution passes every test in all four languages.

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        lo, hi = 0, len(numbers) - 1
        while lo < hi:
            s = numbers[lo] + numbers[hi]
            if s == target:
                return [lo + 1, hi + 1]
            if s < target:
                lo += 1        # need a bigger sum
            else:
                hi -= 1        # need a smaller sum
        return []

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int lo = 0, hi = numbers.length - 1;
        while (lo < hi) {
            int s = numbers[lo] + numbers[hi];
            if (s == target) return new int[]{lo + 1, hi + 1};
            if (s < target) lo++; else hi--;
        }
        return new int[0];
    }
}

class Solution {
public:
    vector<int> twoSum(vector<int>& numbers, int target) {
        int lo = 0, hi = (int)numbers.size() - 1;
        while (lo < hi) {
            int s = numbers[lo] + numbers[hi];
            if (s == target) return {lo + 1, hi + 1};
            if (s < target) lo++; else hi--;
        }
        return {};
    }
};

function twoSum(numbers, target) {
  let lo = 0, hi = numbers.length - 1;
  while (lo < hi) {
    const s = numbers[lo] + numbers[hi];
    if (s === target) return [lo + 1, hi + 1];
    if (s < target) lo++; else hi--;
  }
  return [];
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

Watch the core idea of this problem step by step. Change the input and press Visualize.

Explained in the lesson Two Pointers.