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 <= index1 < index2 <= 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.

Additional information

• 2 <= numbers.length <= 3 * 10^4
• -1000 <= numbers[i] <= 1000
• numbers is sorted in non-decreasing order.

Example 1:

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

Output: [1, 2]

Example 2:

Input: numbers = [2, 3, 4], target = 6

Output: [1, 3]

Example 3:

Input: numbers = [-1, 0], target = -1

Output: [1, 2]

Brute Force (Time Limit Exceeded)

Intuition
Even though the array is sorted, we can still use the brute force approach from the original "Two Sum" problem. We can iterate through every pair of numbers and check if their sum equals the target. However, this fails to utilize the sorted property of the array and is inefficient for large inputs.

Algorithm

1. Iterate through the array with pointer i from 0 to n-1.
2. Iterate through the array with pointer j from i + 1 to n-1.
3. If numbers[i] + numbers[j] equals target, return [i + 1, j + 1].

def two_sum(numbers: list[int], target: int) -> list[int]:
    n = len(numbers)
    for i in range(n):
        for j in range(i + 1, n):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]
    return []

Time & Space Complexity

• Time complexity: O(n^2)

• Reason: We check every possible pair of elements.

• Space complexity: O(1)

• Reason: We only use variables for iteration.

Two Pointers (Optimal)

Intuition
Since the array is sorted, we can make smart decisions about which numbers to check. We put one pointer at the beginning (l) and one at the end (r).
If the sum of numbers[l] and numbers[r] is greater than the target, we know we need a smaller sum. Because the array is sorted, the only way to get a smaller sum is to move the right pointer to the left (pick a smaller number).
Conversely, if the sum is smaller than the target, we need a larger sum, so we move the left pointer to the right.

Algorithm

1. Initialize l to 0 and r to len(numbers) - 1.
2. While l < r:

• Calculate current_sum = numbers[l] + numbers[r].
• If current_sum equals target, return [l + 1, r + 1].
• If current_sum is greater than target, decrement r.
• If current_sum is less than target, increment l.

def two_sum(numbers: list[int], target: int) -> list[int]:
    l, r = 0, len(numbers) - 1

    while l < r:
        cur_sum = numbers[l] + numbers[r]

        if cur_sum > target:
            r -= 1
        elif cur_sum < target:
            l += 1
        else:
            return [l + 1, r + 1]
    return []

Time & Space Complexity

• Time complexity: O(n)

• Reason: The pointers l and r move towards each other, processing each element at most once.

• Space complexity: O(1)

• Reason: We only use two integer pointers.