167. Two Sum II - Input Array Is Sorted

Problem Link

Similar to problem TwoSum, except the nums array is sorted now. We can greedily use this information by comparing sum of left and right end. If our sum exceed target, we should reduce it by decreasing the right pointer. Else if our sum is smaller than target, we can increase our current sum by increasing left pointer.

Runtime Complexity

Time: \(O(n)\), since we're only iterating the nums array once.

Space: \(O(1)\), constant space from two pointers.

PythonGo

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        l, r = 0, len(numbers)-1
        while l < r:
            curr = numbers[l] + numbers[r]
            if curr > target:
                r-=1
            elif curr < target:
                l+=1
            else:
                return [l+1, r+1]
        return [-1,-1]

func twoSum2(numbers []int, target int) []int {
    l, r := 0, len(numbers)-1
    for l < r {
        curr := numbers[l] + numbers[r]
        if curr > target {
            r--
        } else if curr < target {
            l++
        } else {
            return []int{l + 1, r + 1}
        }
    }
    return nil
}

---