Two Sum Problem in Javascript with Sorted Array

Given a sorted array of integers numbers and an integer target, your task is to identify the indices of two distinct numbers in the array that sum up to the specified target.

Each input will have exactly one solution, and you cannot use the same element more than once. Return the answer in any order.

Examples

// Example 1:
Input: numbers = [2, 7, 11, 15], target = 9
Output: [1, 2] // Because numbers[0] + numbers[1] = 2 + 7 = 9

// Example 2:
Input: numbers = [2, 3, 4], target = 6
Output: [1, 3] // Because numbers[0] + numbers[2] = 2 + 4 = 6

Solution

There can be two approaches to solve this problem:

1. Two Pointers Approach
2. Binary Search Approach

Approach 1: Two Pointers

This approach uses two pointers, one starting from the beginning of the array and the other from the end. By summing the values at these pointers, we can efficiently find the target sum. The time complexity is O(n) and the space complexity is O(1).

var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length - 1;

    while (left < right) {
        let sum = numbers[left] + numbers[right];
        if (sum === target) {
            return [left + 1, right + 1];
        } else if (sum > target) {
            right--;
        } else {
            left++;
        }
    }
};

Approach 2: Binary Search

This approach utilizes binary search to find the second number needed to reach the target. For each number in the array, we search for the corresponding number that, when added, equals the target. The time complexity for this approach is O(n log n) due to the binary search operation, and the space complexity is O(1).

var twoSum = function(num, target) {
    let right = num.length - 1;

    for (let i = 0; i < num.length; i++) {
        let left = i + 1;
        
        while (left <= right) {
            let mid = Math.floor(left + (right - left) / 2);
            let sum = num[i] + num[mid];
            
            if (sum === target) {
                return [i + 1, mid + 1];
            } else if (sum > target) {
                right = mid - 1;
            } else {
                left = mid + 1;
            }
        }
    }
};