algoadvance

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, as a 1-indexed array [index1, index2].

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

Examples

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

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

  3. Input: numbers = [-1,0], target = -1 Output: [1,2]

Clarifying Questions

  1. Can we assume that the input list always has at least two elements?
  2. Are there any constraints on the values of the elements in the input list?
  3. Is the input list always sorted in non-decreasing order?

Strategy

Since the list is already sorted, we can utilize the two-pointer approach to solve this problem efficiently:

  1. Initialize two pointers: one at the beginning (left pointer) and one at the end (right pointer) of the list.
  2. Calculate the current sum of the elements pointed to by these pointers.
  3. If the current sum equals the target, return the 1-indexed positions of left and right.
  4. If the current sum is less than the target, increment the left pointer to increase the sum.
  5. If the current sum is greater than the target, decrement the right pointer to decrease the sum.
  6. Repeat steps 2-5 until a solution is found.

This approach ensures that we find the solution in linear time.

Time Complexity

The time complexity of this solution is O(n), where n is the number of elements in the input list. This is because each element is processed at most once.

Code

def twoSum(numbers, target):
    left, right = 0, len(numbers) - 1
    
    while left < right:
        current_sum = numbers[left] + numbers[right]
        
        if current_sum == target:
            return [left + 1, right + 1]
        elif current_sum < target:
            left += 1
        else:
            right -= 1
            
    # In practice we should never reach this statement given the problem constraints
    return []

# Example usage:
print(twoSum([2,7,11,15], 9))  # Output: [1,2]
print(twoSum([2,3,4], 6))  # Output: [1,3]
print(twoSum([-1,0], -1))  # Output: [1,2]

Summary

This solution leverages the sorted property of the input list to efficiently find the two indices that add up to the target using a two-pointer technique. The algorithm runs in O(n) time complexity and requires O(1) additional space.

Try our interview co-pilot at AlgoAdvance.com