Two Sum II - Input Array Is Sorted medium

Problem Statement

Given a 1-indexed array of integers numbers that is already sorted in ascending order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where answer[0] < answer[1].

You may assume that each input would have exactly one solution and you may not use the same element twice.

Example 1:

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

Example 2:

Input: numbers = [2,3,4], target = 6 Output: [1,3] Explanation: Because numbers[1] + numbers[2] == 6, we return [1, 3].

Steps

1. Two-Pointer Approach: Utilize a two-pointer technique, initializing left to 0 and right to numbers.length - 1.

2. Sum and Comparison: Calculate the sum sum of numbers[left] and numbers[right].

3. Adjustment:

   • If sum equals the target, return [left + 1, right + 1] (1-indexed).
   • If sum is less than the target, increment left to consider a larger number.
   • If sum is greater than the target, decrement right to consider a smaller number.

4. Iteration: Repeat steps 2 and 3 until the left and right pointers cross each other (left >= right). This condition implies that no solution exists within the array (though the problem statement guarantees a solution).

Explanation

The algorithm leverages the sorted nature of the input array. By using two pointers starting from opposite ends, we efficiently search for a pair that sums to the target. If the sum is too small, we move the left pointer to a larger number; if the sum is too large, we move the right pointer to a smaller number. This systematic approach avoids unnecessary comparisons and ensures that we find the solution in linear time.

Code

function twoSum(numbers: number[], target: number): number[] {
    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]; // 1-indexed
        } else if (sum < target) {
            left++;
        } else {
            right--;
        }
    }

    //This line will never be reached due to problem constraints, but is included for completeness.
    return []; 
};

Complexity

• Time Complexity: O(N), where N is the length of the input array. We perform a single pass through the array using the two-pointer approach.
• Space Complexity: O(1). The algorithm uses only a constant amount of extra space to store the pointers and the sum.