Two Sum II - Input Array Is Sorted

Problem Statement

You are given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, and a value target. Return the indices of the two numbers (as [index1, index2], 1-indexed) such that they add up to target.

• There is exactly one valid solution.
• You may not use the same element twice.
• Your solution must use only constant O(1) extra space.

Example

Input:  numbers = [2, 7, 11, 15], target = 9
Output: [1, 2]
Explanation: numbers[0] + numbers[1] = 2 + 7 = 9, so the 1-indexed answer is [1, 2].

Two Pointer Approach

Because the array is sorted, we can place one pointer at the start (left) and one at the end (right), then move them toward each other based on the current sum:

• If numbers[left] + numbers[right] == target → we found the pair.
• If the sum is too small, move left right to increase it.
• If the sum is too large, move right left to decrease it.

This works because sorting guarantees that moving left only increases the sum and moving right only decreases it, so we never skip the answer.

Complexity

• Time: O(n) — each pointer moves at most n steps.
• Space: O(1) — no extra data structures.

Solution Code

Python

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    while left < right:
        total = numbers[left] + numbers[right]
        if total == target:
            return [left + 1, right + 1]  # 1-indexed
        elif total < target:
            left += 1
        else:
            right -= 1
    return []

Java

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

C++

vector<int> twoSum(vector<int>& numbers, int target) {
    int left = 0, right = numbers.size() - 1;
    while (left < right) {
        int total = numbers[left] + numbers[right];
        if (total == target) return {left + 1, right + 1};
        else if (total < target) left++;
        else right--;
    }
    return {};
}

Key Takeaways

• The sorted property is what makes the two pointer technique valid here — it turns an O(n²) brute force into O(n).
• Remember the answer is 1-indexed, so add 1 to both pointer positions.
• This pattern generalises to many "find a pair/triplet with a given sum" interview problems.