Two Sum II — Input array is sorted

Given a 1-indexed array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Let these two numbers be numbers[index1] and numbers[index2] where 1 <= index1 < index2 <= numbers.length.

Return the indices of the two numbers index1 and index2, each incremented by one, as an integer array [index1, index2] of length 2.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

Your solution must use only constant extra space.

Example 1:

Input: numbers = [2,7,11,15], target = 9 Output: [1,2] Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: The sum of 2 and 4 is 6. Therefore index1 = 1, index2 = 3. We return [1, 3].

Example 3:

Input: numbers = [-1,0], target = -1 Output: [1,2] Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

Constraints:

• 2 <= numbers.length <= 3 * 104
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.
• -1000 <= target <= 1000
• The tests are generated such that there is exactly one solution.

Approach: Two Pointers (Optimal Solution)

Algorithm

1. Place one pointer at the start (lo = 0) and one at the end (hi = numbers.length - 1)
2. Compute the sum of the two pointed values
3. If the sum equals the target, return the 1-based indices
4. If the sum is less than the target, increment lo (need a larger number)
5. If the sum is greater than the target, decrement hi (need a smaller number)
6. Repeat until the solution is found

Time & Space Complexity

• Time Complexity: O(n) - each pointer moves at most n steps total
• Space Complexity: O(1) - only constant extra space, as required

Java Implementation

public class TwoSumII {

    /**
     * Find the 1-based indices of two numbers that add up to the target.
     * @param numbers Sorted (non-decreasing) array
     * @param target Target sum
     * @return 1-based indices [index1, index2]
     */
    public static int[] twoSum(int[] numbers, int target) {
        int lo = 0;
        int hi = numbers.length - 1;

        while (lo < hi) {
            int sum = numbers[lo] + numbers[hi];

            if (sum == target) {
                return new int[]{lo + 1, hi + 1};
            } else if (sum < target) {
                lo++;
            } else {
                hi--;
            }
        }

        // Exactly one solution is guaranteed
        return new int[]{-1, -1};
    }

    // Test method
    public static void main(String[] args) {
        int[] numbers1 = {2, 7, 11, 15};
        int target1 = 9;
        int[] result1 = twoSum(numbers1, target1);
        System.out.println("Input: numbers = [2, 7, 11, 15], target = 9");
        System.out.println("Output: [" + result1[0] + ", " + result1[1] + "]"); // Expected: [1, 2]

        int[] numbers2 = {2, 3, 4};
        int target2 = 6;
        int[] result2 = twoSum(numbers2, target2);
        System.out.println("Input: numbers = [2, 3, 4], target = 6");
        System.out.println("Output: [" + result2[0] + ", " + result2[1] + "]"); // Expected: [1, 3]

        int[] numbers3 = {-1, 0};
        int target3 = -1;
        int[] result3 = twoSum(numbers3, target3);
        System.out.println("Input: numbers = [-1, 0], target = -1");
        System.out.println("Output: [" + result3[0] + ", " + result3[1] + "]"); // Expected: [1, 2]
    }
}

Example Walkthrough

For numbers = [2, 7, 11, 15] and target = 9:

1. lo=0, hi=3: sum = 2 + 15 = 17 > 9, hi—
2. lo=0, hi=2: sum = 2 + 11 = 13 > 9, hi—
3. lo=0, hi=1: sum = 2 + 7 = 9, return [1, 2]

Key Points

1. Sorted Array Enables Two Pointers: The monotonic order lets us move pointers deterministically
2. Constant Space: Unlike Two Sum, no hash map is needed (also required by the problem)
3. 1-Based Output: Add 1 to both zero-based indices before returning
4. Guaranteed Solution: The tests always contain exactly one answer
5. O(n) Time: Each step eliminates one element