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]

Steps

1. Initialization: We'll use two pointers, left and right, initialized to the beginning and end of the array, respectively.
2. Iteration: We'll iterate while left is less than right.
3. Sum Check: In each iteration, we calculate the sum of the elements at the left and right pointers.
4. Target Match: If the sum equals the target, we've found our pair. We return their 1-indexed indices.
5. Adjustment: If the sum is less than the target, we need a larger sum, so we increment left. If the sum is greater than the target, we need a smaller sum, so we decrement right.
6. No Solution: If the loop completes without finding a solution, it means there's no pair that adds up to the target. (The problem statement guarantees a solution, so this step is technically unnecessary for this specific problem).

Explanation

This approach leverages the fact that the input array is sorted. By using two pointers from opposite ends and moving them inwards based on the sum, we efficiently search for the target pair. This avoids nested loops, resulting in a linear time complexity.

Code

def twoSum(numbers, target):
    """
    Finds two numbers in a sorted array that add up to a target.

    Args:
        numbers: A sorted list of integers.
        target: The target sum.

    Returns:
        A list containing the 1-indexed indices of the two numbers.
    """
    left = 0
    right = len(numbers) - 1

    while left < right:
        current_sum = numbers[left] + numbers[right]
        if current_sum == target:
            return [left + 1, right + 1]  # 1-indexed return
        elif current_sum < target:
            left += 1
        else:
            right -= 1

    # This line is unreachable given the problem constraints but 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 two pointers.
• Space Complexity: O(1). We use a constant amount of extra space to store the pointers and the sum.