Problem Description

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.

Example 1:

  • Input: numbers = [2,7,11,15], target = 9
  • Output: [1,2]
  • Explanation: The sum of 2 and 7 is 9. Therefore, index1 = 1, index2 = 2. We return [1, 2].

Example 2:

  • Input: numbers = [2,3,4], target = 6
  • Output: [1,3]
  • Explanation: The sum of 2 and 4 is 6. Therefore, index1 = 1, index2 = 3. We return [1, 3].

My Idea

My initial idea was to iterate over the elements of numbers and for each of them check if the integer needed to reach target by addition was in the array as well and return the indices. This approach, however, results in a time complexity of O(n^2). The more optimized solution came next. We use two pointers starting at opposite ends of the array numbers, add the respective value and according to the result move one of the pointers in search of the target sum. Here we make use of the fact that the array is sorted, so if the sum is >target this means we have to move the pointer on the right end of numbers inwards to reduce the sum, and if it’s <target we have to move the one at the beginning respectively. This approach only traverses the array once and thus yields a time complexity of O(n)

My solution

# Optimized solution with Time Complexity: O(n)
def twoSum(numbers: list[int], target: int) -> list[int]:
    cur=target-1
    i=0
    j=len(numbers)-1
    while(cur!=target):
        cur=numbers[i]+numbers[j]
        if cur>target:
            j-=1
            continue
        if cur<target:
            i+=1
            continue
    return [i+1,j+1]

# Initial approach with Time Complexity: O(n^2)
def twoSumInitial(numbers: list[int], target: int) -> list[int]:
    for i in numbers:
        needed=target-i
        if needed in numbers:
            return [numbers.index(i)+1,numbers.index(needed)+1]