Two Sum II – Input Array Is Sorted

Medium Problem 18 of 151 Java and Python

Problem

Given a 1-indexed array numbers sorted in non-decreasing order, find two numbers that add up to target. Return their indices as [index1, index2] with 1 ≤ index1 < index2.

There is exactly one solution, you may not use the same element twice, and your solution must use only constant extra space.

Example 1

Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Why: 2 + 7 = 9, at positions 1 and 2.

Example 2

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

Constraints

2 ≤ numbers.length ≤ 3 × 10⁴
-1000 ≤ numbers[i], target ≤ 1000
numbers is sorted in non-decreasing order.

Explanation

Put one pointer on the smallest number and one on the largest. If their sum is too small, the only way to grow it is to move the left pointer right; if it is too big, move the right pointer left.

Each step rules out one number for good, so the pointers meet the answer in at most n steps.

Approach 1 · Better

Binary search for the partner

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

For each number, binary-search the rest of the array for target - numbers[i]. This uses the sorted order, but not as well as two pointers.

For each i, search [i + 1, n - 1] for target - numbers[i].
If found at j, return [i + 1, j + 1].

Java

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

Python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for i, num in enumerate(numbers):
            need = target - num
            lo, hi = i + 1, len(numbers) - 1
            while lo <= hi:
                mid = (lo + hi) // 2
                if numbers[mid] == need:
                    return [i + 1, mid + 1]
                if numbers[mid] < need:
                    lo = mid + 1
                else:
                    hi = mid - 1
        return []

Approach 2 · Optimal

Pointers from both ends

Time O(n)
Space O(1)

Move the left pointer up when the sum is too small and the right pointer down when it is too large.

Set left = 0, right = n - 1.
Compute sum = numbers[left] + numbers[right].
If sum == target, return [left + 1, right + 1]; if smaller, left++; if larger, right--.

Java

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

Python

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers) - 1
        while left < right:
            total = numbers[left] + numbers[right]
            if total == target:
                return [left + 1, right + 1]
            if total < target:
                left += 1
            else:
                right -= 1
        return []

Complexity compared

Approach	Time	Space
Better Binary search for the partner	O(n log n)	O(1)
Optimal Pointers from both ends	O(n)	O(1)

Key takeaways

A sorted array plus a pair condition almost always means two pointers from both ends.
The answer is 1-indexed: add 1 to both indices.

Your notes

Saved in this browser as you type.

Solved it on your own?

Mark it done to track your progress, or star it to come back before an interview.

Next problem