Two Sum II — Input Array Is Sorted [Medium] — O(1) Space Two Ptr

Problem Statement

Given a 1-indexed sorted array, find two numbers that add up to target. Return their 1-indexed positions. Exactly one solution guaranteed. O(1) extra space.

Input: numbers=[2,7,11,15], target=9 → Output: [1,2]

Solutions

C++

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

Java

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

Python

def twoSum(numbers: list[int], target: int) -> list[int]:
    l, r = 0, len(numbers)-1
    while l < r:
        s = numbers[l] + numbers[r]
        if s == target: return [l+1, r+1]
        elif s < target: l += 1
        else: r -= 1
    return []

Complexity

Time: O(n), Space: O(1)