Coding Interview Prep: Two Sum II with Solution in JavaScript

Solution

/*
Two Sum solution using 2 pointers
Time Complexity: O(n)
Space Complexity: O(1)
Runtime: 54 ms
 */
var twoSum = function(numbers, target) {
    let left = 0;
    let right = numbers.length-1;
    while (left < right){
        const sum = numbers[left]+numbers[right];

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

Complexity

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

Explanation

This solution solves the 2 sum ii problem in O(1) space and O(n) time complexity using 2 pointers. As we know, the two sum i problem can use a hashmap, but the downside is that the hashmap uses O(n) space. In this question, it is stated that we need to use only constant O(1) space. How to do this? We will use 2 pointers.

We will start with initializing the first left pointer to index 0 and the second right pointer to the last element of the array. First we will declare a while loop that will stop only on the condition when the left pointer reaches the right pointer. If the sum matches the target, we will return an array of the first and second pointer. If the sum is greater than the target, then we will decrease the right pointer by 1. If the sum is less than the target, then will increase the left pointer by 1.