Skip to content

167. Two Sum II Input Array Is Sorted

Array Two Pointers Binary Search

Problem - Two Sum II Input Array Is Sorted

Medium

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].

Example 3:

Input: numbers = [-1,0], target = -1
Output: [1,2]
Explanation: The sum of -1 and 0 is -1. Therefore index1 = 1, index2 = 2. We return [1, 2].

 

Constraints:

  • 2 <= numbers.length <= 3 * 104
  • -1000 <= numbers[i] <= 1000
  • numbers is sorted in non-decreasing order.
  • -1000 <= target <= 1000
  • The tests are generated such that there is exactly one solution.

Solutions

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        n = len(numbers)
        # for i in range(n - 1):
        #     search = target - numbers[i]
        #     found_index = bisect_left(numbers, search, lo=i+1) # i+1 for 1 indexing
        #     if found_index < n and numbers[found_index] == search:
        #         return [i + 1, found_index + 1] # +1 for 1 indexing
        left, right = 0, n - 1
        while right > left:
            curr_sum = numbers[left] + numbers[right]
            if curr_sum == target:
                break
            if curr_sum < target:
                left += 1
            else:
                right -= 1

        return [left + 1, right + 1]

Submission Stats:

  • Runtime: 0 ms (100.00%)
  • Memory: 18.8 MB (9.60%)