Two Sum II - Input Array Is Sorted

Problem Statement

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 \le \text{index1} < \text{index2} \le \text{numbers.length}$.
Return the indices of the two numbers, index1 and index2, added 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:
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].

Approach: Two Pointers

The standard Two Sum problem requires a Hash Map to achieve $O(n)$ time complexity, which takes $O(n)$ extra space.

However, since this input array is already sorted, we can solve this problem using Two Pointers with just $O(1)$ extra space!

We place one pointer at the very beginning (left) and one pointer at the very end (right) of the array. At each step, we calculate the sum of the elements at these two pointers.

• Because the array is sorted, if our sum is too large, we know we need a smaller number, so we decrement our right pointer.
• If our sum is too small, we know we need a larger number, so we increment our left pointer.
• If the sum matches the target, we return the 1-based indices!

1. Initialize left = 0 and right = numbers.length - 1.
2. Start a while loop that continues as long as left < right.
3. Calculate sum = numbers[left] + numbers[right].
4. If sum === target, we found the answer! Return [left + 1, right + 1] (since the problem requires 1-based indexing).
5. If sum > target, the sum is too big. Decrement right to try a smaller number.
6. If sum < target, the sum is too small. Increment left to try a larger number.

Solution

/**
 * @param {number[]} numbers
 * @param {number} target
 * @return {number[]}
 */
function twoSum(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;
    
    while (left < right) {
        const sum = numbers[left] + numbers[right];
        
        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum > target) {
            right--;
        } else {
            left++;
        }
    }
    
    // The problem guarantees exactly one solution exists, 
    // so we theoretically never reach here.
    return [];
}

Complexity Analysis

• Time Complexity: $O(n)$ where $n$ is the length of the numbers array. In the worst case, the pointers will scan through the entire array exactly once until they meet in the middle.
• Space Complexity: $O(1)$ auxiliary space. We only use two integer variables (left and right) to keep track of indices, requiring no extra memory scaled to the input size.