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

Constraints:

• 2 <= numbers.length <= 3 * 104

• -1000 <= numbers[i] <= 1000

• numbers is sorted in non-decreasing order.

• -1000 <= target <= 1000

• The tests are generated such that there is exactly one solution.

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.

Input: numbers = [2,3,4], target = 6
Output: [1,3]

Input: numbers = [-1,0], target = -1
Output: [1,2]

💡 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

class Solution {
    /**  
     * @time  : O(n)
     * @space : O(1)
     */
    
    public int[] twoSum(int[] numbers, int target) {
        int l = 0, r = numbers.length - 1;
        
        while(l < r) {
            int tmp = numbers[l] + numbers[r];
            if(tmp == target) return new int[] {l+1, r+1};
            else if(tmp > target) r--;
            else if(tmp < target) l++;
        }
        
        return new int[] {-1, -1};
    }
}