Problem statement

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

The tests are constructed so that there is exactly one solution. Your solution must use only constant extra space.

Example 1

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 + 7 = 9.

Example 2

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Constraints

• 2 <= numbers.length <= 25
• -500 <= numbers[i] <= 500
• numbers is sorted; exactly one solution exists.

Hints for Two Sum II - Input Array Is Sorted

1. Hint 1

   One pointer at each end: the sum tells you which pointer to move.

2. Hint 2

   Sum too small → move left pointer right; too big → move right pointer left.

How to solve Two Sum II - Input Array Is Sorted

Sortedness turns the pair search into a single sweep. Start with the widest possible pair — first and last — and note that its sum is an extreme. If the sum is too small the only way to grow it is to raise the left value; if too big, the only way to shrink it is to lower the right. Each comparison discards a whole row of candidates.

Approach

1. Put l at the first index and r at the last.
2. Compute numbers[l] + numbers[r].
3. If it equals the target, return [l + 1, r + 1] — the problem is 1-indexed.
4. If the sum is below the target, move l right; if above, move r left.
5. The guaranteed unique solution is always reached before the pointers cross.

Why it works

Think of the candidate pairs as a grid. When the sum at (l, r) is too small, every pair (l, r') with r' < r is smaller still — the array is sorted — so the entire column below r for that l can be discarded, which is exactly what advancing l does. The symmetric argument covers the too-big case. Nothing that could be the answer is ever skipped, and each step retires one index, giving a linear sweep in constant space.

Complexity

• Time — O(n)
• Space — O(1)

Pitfalls

• The indices are 1-based — return l + 1 and r + 1, not the raw offsets.
• A hash map also finds the pair but costs O(n) extra space, which the problem forbids.
• Move exactly one pointer per step; moving both can step over the unique solution.
• Values may be negative, but sortedness is all this argument needs.

Reference solution

Python

from typing import List

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]
        if s < target:
            l += 1
        else:
            r -= 1
    return [-1, -1]

Java

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

C++

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

JavaScript

var twoSum = function(numbers, target) {
    let l = 0, r = numbers.length - 1;
    while (l < r) {
        const sum = numbers[l] + numbers[r];
        if (sum === target) return [l + 1, r + 1];
        if (sum < target) l++;
        else r--;
    }
    return [-1, -1];
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Implement Router Medium
• Design Memory Allocator Medium
• Design a Food Rating System Medium
• Design an ATM Machine Medium
• Design Bitset Medium
• Range Frequency Queries Medium