Leetcode 167. Two Sum II - Input Array Is Sorted

Problem

Leetcode 167 - Two Sum II - Input Array Is Sorted

Example:

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

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

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

Approach

Since we’re trying to get a target with sorted array, we can simply use two pointer one at beginning of the array, and one at the end of the array. There are 3 outcomes of these sums

• sum < target:
  • we increment left pointer
• sum > target:
  • we decrement right pointer
• sum == target:
  • we simply return index of two pointer

Visualization of the Approach:

numbers = [2,7,11,15], target = 9
left = 0, right = 3
numbers[left] = 2, numbers[right] = 15
since sum = 17 > target, we decrement right

left = 0, right = 2
numbers[left] = 2, numbers[right] = 11
since sum = 13 > target, we decrement right

left = 0, right = 1
numbers[left] = 2, numbers[right] = 7
since sum == target we return index

return [1, 2]

Here is the Python code for the solution:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        left, right = 0, len(numbers)-1

        while left < right:
            two = numbers[left] + numbers[right]

            if two < target:
                left += 1
            elif two > target:
                right -= 1
            else:
                return [left+1, right+1]

Time Complexity and Space Complexity

Time Complexity: $O(n)$

Space Complexity: $O(1)$