Two Sum II - Input Array Is Sorted

Share

Given a 1-indexed array of integers numbers sorted in non-decreasing order, find two numbers such that they add up to a specific target. Return the indices of the two numbers (1-indexed) as an array [index1, index2] where 1 <= index1 < index2 <= numbers.length. The solution must use only constant extra space.

Example 1
Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: 2 + 7 = 9. Return [1, 2].
Example 2
Input: numbers = [2,3,4], target = 6
Output: [1,3]
Example 3
Input: numbers = [-1,0], target = -1
Output: [1,2]
Constraints:

Contents

Approach 1: Brute Force O(n²)
Java
public int[] twoSum(int[] numbers, int target) {
    for (int i = 0; i < numbers.length - 1; i++) {
        for (int j = i + 1; j < numbers.length; j++) {
            if (numbers[i] + numbers[j] == target) {
                return new int[]{i + 1, j + 1};
            }
        }
    }
    return new int[]{};
}

Approach 2: Two Pointers O(n)

Because the array is sorted, place one pointer at the left and one at the right. If their sum is less than target, move left right (increase sum); if greater, move right left (decrease sum).

Java
public int[] twoSum(int[] numbers, int target) {
    int left = 0, 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[]{}; // guaranteed to find answer
}

Complexity Analysis
ApproachTimeSpace
Brute ForceO(n²)O(1)
Two PointersO(n)O(1)