DEV Community

loading...

167. Two Sum II - Input array is sorted (javascript solution)

cod3pineapple profile image codingpineapple ・1 min read

Description:

Given an array of integers numbers that is already sorted in ascending 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.

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

Solution:

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

// Two pointers
var twoSum = function(numbers, target) {
    // Start a pointer on each side of the array
    let left = 0;
    let right = numbers.length-1
    while(left < right) {
        const cur = numbers[left] + numbers[right];
        // Return 1 base index if the current sum is equal to the target
        if(cur === target) return [left+1, right+1]
        // Because the array is sorted, anytime we move a pointer to the right numbers will get bigger and anytime we move a pointer to the left, numbers will get smaller
        // If cur is greater than target that means we need to use smaller numbers in our sum and we move the right pointer to the left.
        // If cur is less than target that means we need to use bigger number in our sum and we move the left pointer to the right.
        cur > target ? right-- : left++
    }
};
Enter fullscreen mode Exit fullscreen mode

Discussion (0)

pic
Editor guide