Two Sum II - Input Array Is Sorted

problem at: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted

# Solution

# Two Pointers

This is the best and most straightforward solution.

Complexity:

  • time:
  • space:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    left, right = 0, len(nums)-1
    while left<right:
        sm = nums[left] + nums[right]
        if sm<target:
            left += 1
        elif sm>target:
            right -= 1
        else:
            return [left+1,right+1]
    return []

# Dictionary

Like one-pass HashMap in Two Sum, a dictionary is used to store mappings from val to idx.

Complexity:

  • time:
  • space:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    dct = {}
    for idx,val in enumerate(nums):
        if target-val in dct:
            return [dct[target-val]+1, idx+1]
        dct[val] = idx
    return [-1,-1]

For each nums[i], use binary search to find target-nums[i].

Complexity:

  • time:
  • space:
def twoSum(self, nums: List[int], target: int) -> List[int]:
    n = len(nums)

    for i in range(n):
        left, right = i+1, n-1
        complement = target-nums[i]
        while left<=right:
            mid = left + (right-left)//2
            if nums[mid] < complement:
                left = mid + 1
            elif nums[mid] > complement:
                right = mid - 1
            else:
                return [i+1, mid+1]
    return [-1, -1]