[Algo Rhythm🕺💃] LeetCode 167. Two Sum II - Input array is sorted

📚 Problem description

Given an array of integers that is already sorted in ascending order, find two numbers such that they add up to a specific target number.

The function twoSum should return indices of the two numbers such that they add up to the target, where index1 must be less than index2.

 

Note:

• Your returned answers (both index1 and index2) are not zero-based.

• You may assume that each input would have exactly one solution and you may not use the same element twice.

Example:
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.

 

🎯 Solution

class Solution {
    public int[] twoSum(int[] numbers, int target) {
        int[] ans = new int[2];
        int left = 0, right = numbers.length - 1;
        
        while(left < right) {
            int sum = numbers[left] + numbers[right];
            if(sum == target) {
                ans[0] = left + 1;
                ans[1] = right + 1;
                break;
            }
            if(sum > target) right--;
            if(sum < target) left++;
        }
        
        return ans;
    }
}

 

🧐 Approach

I used two pointer approach. One pointer, called left,  points the first index and the other pointer, called right, points the last index.

If sum is same as the target, return those indexes.

If sum is larger than the target, right pointer should point the previous index.

If sum is smaller than the target, left pointer should point the next index.

Repeat these rule until left is equal to or greater than right.

 

📖  What I learned