Two Sum II - Input Array Is Sorted

Try every pair of indices and check if they sum to the target. Since the array is 1-indexed in the return value, we add 1 to each index.

1. 1For each index i, iterate j from i+1 to the end.
2. 2If numbers[i] + numbers[j] == target, return [i+1, j+1].

Why it's not optimal: O(n²) time. Since the array is sorted, we can do much better by exploiting the ordering with two pointers.

def twoSum(numbers, target):
    for i in range(len(numbers)):
        for j in range(i + 1, len(numbers)):
            if numbers[i] + numbers[j] == target:
                return [i + 1, j + 1]

Because the array is already sorted, we do not need to use $O(n)$ space for a Hash Map! We can place a pointer at the beginning (smallest possible value) and the end (largest possible value) and logically eliminate options.

1. 1Initialize pointer L at the 0th index and R at the end.
2. 2Sum the values at both pointers. If the sum is larger than our target, we know the sum must be reduced. The only way to securely reduce the sum is to shrink the right pointer.
3. 3If the sum is smaller than our target, the array sum must be increased. We do this by increasing the left pointer to larger elements!
4. 4When we match the target, we simply return the 1-indexed positions [L+1, R+1].