0167. Two Sum II - Input array is sorted

Easy | Two Pointer | 56 ms (95.70%), 14.8 MB (32.12%)

❓ Problem Statement

Source: LeetCode - Two Sum II - Input array is sorted GitHub: Solution / Performance

Given an 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.

Return the indices of the two numbers (1-indexed) as an integer array answer of size 2, where 1 <= answer[0] < answer[1] <= numbers.length.

The tests are generated such that there is exactly one solution. You may not use the same element twice.

✍🏻 Constraints & Example

💡 Ideas

Since there is exactly one solution, two-pointers with dynamically adjusted indexes could help to solve.

Starting with the left- and right-most elements, we sum up them to see whether the result meets the target value.

• If the result is greater than the target, we move the right-pointer forward.

• If the result is less than the target, we move the left-pointer backward.

🤖 Python3

class Solution:
    def twoSum(self, numbers: List[int], target: int) -> List[int]:
        # (base case)
        if len(numbers) == 2: return [1, 2] if sum(numbers) == target else [-1, -1]
        
        # ==================================================
        #  Array + Two Pointer                             =
        # ==================================================
        # time  : O(n)
        # space : O(1)
        
        l, r = 0, len(numbers) - 1
        while l < r:
            tmp = numbers[l] + numbers[r]
            if   tmp == target: return [l+1, r+1]
            elif tmp > target: r -= 1
            elif tmp < target: l += 1
                
        return [-1, -1]
        
        '''
        # ==================================================
        #  Binary Search                                   =
        # ==================================================
        # time  : O(nlog(n))
        # space : O(1)
        
        for i in range(len(numbers) - 1):
            l = i + 1
            r = len(numbers) - 1
            remain = target - numbers[i]
            
            while l <= r:
                mid = (l + r) // 2
                if   numbers[mid] == remain: return [i+1, mid+1]
                elif numbers[mid]  > remain: r = mid - 1
                elif numbers[mid]  < remain: l = mid + 1
                    
        return [-1, -1]
        '''

🤖 Java