Two Sum II - Input Array Is Sorted

mediumTwo Pointers16 stepsJava · Python · C++

The array is sorted, so put one pointer at each end. If the sum is too small, move the left pointer right to increase it; if too big, move the right pointer left. The pointers meet the answer in one pass with O(1) space.

▶ Watch the animated trace

Traced input: numbers = [2, 3, 4, 7, 11, 15], target = 9 → [1, 4]. Original problem: neetcode.io/problems/two-integer-sum-ii

Complexity

BestO(1)

AverageO(n)

WorstO(n)

SpaceO(1)

Best case is when the two ends are the answer.

Key idea

Sorted order tells you which way to move: left increases the sum, right decreases it.
Moving the smaller side can never skip the answer, because that element can't pair with anything bigger than r either.
Return 1-based indices, as the problem asks.

Common mistakes

Returning 0-based indices.
Using a hash map works but ignores the sorted property and the O(1) space requirement.
Binary search for each element is O(n log n).

Solution

Java

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};
}

Python

def twoSum(numbers: List[int], target: int) -> List[int]:
    l, r = 0, len(numbers) - 1
    while l < r:
        total = numbers[l] + numbers[r]
        if total == target:
            return [l + 1, r + 1]
        if total < target: l += 1
        else: r -= 1
    return [-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 {l + 1, r + 1};
        }
        if (sum < target) l++;
        else r--;
    }
    return {-1, -1};
}

Edge cases

Each one has its own trace in the interactive view.

Case	Input	Answer
Negative numbers -3 + 2 = -1. Negative values follow the same rules.	`numbers = [-3, -1, 0, 2, 5], target = -1`	`[1, 4]`
Two elements The ends are the answer immediately.	`numbers = [1, 2], target = 3`	`[1, 2]`
Duplicates The two 3s are different positions.	`numbers = [1, 3, 3, 4], target = 6`	`[2, 3]`
Answer in the middle Both pointers walk inward several times.	`numbers = [1, 2, 3, 4, 4, 9, 56, 90], target = 8`	`[4, 5]`