Two Sum on a Sorted Array

Medium

📘 Problem Statement

Given a sorted array of integers numbers and an integer target, return the 1-based indices of the two numbers such that they add up to target.

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

---

🔍 Example

numbers = [2, 7, 11, 15]
target = 9

answer = [1, 2]

---

💡 Key Observations

• The array is sorted in ascending order.

• There is exactly one pair whose sum is equal to the target.

• We must return indices (1-based), not the actual numbers.

Intuition

• Since the array is sorted, we can use two pointers (left and right) to move inward:

• If the sum of the two numbers is too small, move the left pointer to the right.

• If the sum is too large, move the right pointer to the left.

• Stop when the sum is exactly the target.

🛠️ Solution

def twoSum(numbers: List[int], target: int) -> List[int]:
    left = 0
    right = len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left + 1, right + 1]  # Convert to 1-based index
        elif current_sum < target:
            left += 1  # Need a larger sum
        else:
            right -= 1  # Need a smaller sum

    return []  # Not expected to reach here as per problem constraints

🕒 Time Complexity: \(O(n)\)

📦 Space Complexity: \(O(1)\)