Two Pointers: Two Sum II - Input array is sorted

Question:

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

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

Write a function twoSum to find the two numbers such that they add up to the target, and return their indices (1-indexed).

Example:

Input: numbers = [2,7,11,15], target = 9
Output: [1,2]
Explanation: The sum of 2 and 7 is 9. Therefore, the indices of 2 and 7 are returned as [1,2].

Answer:

The problem can be solved by using the Two Pointers approach.

1. Initialize two pointers, left and right, pointing to the first and last elements of the array, respectively.
2. Loop through the array while left is less than right.
3. Calculate the sum of the elements at pointers left and right.
   • If the sum is equal to the target, return the indices of left and right (1-indexed).
   • If the sum is less than the target, increment left by 1 to move towards larger numbers.
   • If the sum is greater than the target, decrement right by 1 to move towards smaller numbers.
4. If no solution is found, return an empty array.

Here is the implementation of the twoSum function in Python:

def twoSum(numbers, target):
    left = 0
    right = len(numbers) - 1
    
    while left < right:
        sum = numbers[left] + numbers[right]
        
        if sum == target:
            return [left+1, right+1]
        elif sum < target:
            left += 1
        else:
            right -= 1
    
    return [] # No solution found

This implementation has a time complexity of O(n), where n is the length of the input array.