Leetcode 167: Tow Sum II – Input Array Is Sorted

The original question can be found here.

The question is asking us to find 2 numbers that their sum equals to target value, and exlictly, we cannot use data structures. So we cannot use hash table as in Leetcode 1: Two Sum.

Binary Search

Since array is already sorted, naturally we can think of binary search. If you’re not familiar with binary search, please visit my another post here. For each element, we try to find its counterpart in the rest of array:

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        for index, element in enumerate(numbers):
            right_index = self.binary_search(numbers, target - element, index + 1)
            if right_index != -1:
                return [index + 1, right_index + 1]
        return [-1, -1]
        
    def binary_search(self, numbers: List[int], target: int, start_index: int) -> int:
        left, right = start_index, len(numbers) - 1
        while left + 1 < right:
            mid = (left + right) // 2
            if numbers[mid] == target:
                return mid
            elif numbers[mid] < target:
                left = mid
            else:
                right = mid

        if numbers[left] == target:
            return left
        if numbers[right] == target:
            return right
        return -1

Time Complexity: O(nlogn). Space Complexity: O(1).

Two Pointers

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

Time Complexity: O(n). Space Complexity: O(1).