Efficiently Solving Two Sum II - Input Array Is Sorted

The "Two Sum II - Input Array Is Sorted" problem is a classic coding challenge that tests your understanding of arrays and pointer manipulation. It’s also a great opportunity to showcase a solution that is both elegant and efficient. Let’s dive into the problem and break down an optimal approach to solving it.

Link to the problem on LeetCode

Problem Statement

Given a 1-indexed array of integers numbers that is sorted in non-decreasing order, your goal is to find two numbers such that their sum equals a given target. You need to return the indices of these two numbers as an array [index1, index2] where 1 <= index1 < index2 <= numbers.length. The solution should use only constant extra space.

Constraints

• The array numbers is sorted in non-decreasing order.
• There is exactly one solution.
• You may not use the same element twice.
• The input array length ranges from 2 to 30,000.
• Values in the array range from −1000 to 1000.

Example Inputs and Outputs

1. Input: numbers = [2,7,11,15], target = 9
   
   Output: [1, 2]

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

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

Approach: Two Pointers

The problem’s constraints—a sorted array and a single solution—make it a perfect candidate for the two-pointer technique. Here’s why:

• Efficiency: Two pointers allow us to traverse the array in a single pass (O(n) time complexity).
• Constant Space: We avoid auxiliary data structures, adhering to the problem’s requirement of constant extra space.

Implementation

Below is the JavaScript implementation of the two-pointer approach:

/**
 * @param {number[]} nums
 * @param {number} target
 * @return {number[]}
 */
var twoSum = function(nums, target) {
    const length = nums.length;
    let rightPointer = length - 1;
    let leftPointer = 0;

    while (leftPointer < rightPointer) {
        if (nums[leftPointer] + nums[rightPointer] === target) {
            return [leftPointer + 1, rightPointer + 1];
        }
        if (nums[leftPointer] + nums[rightPointer] > target) {
            rightPointer--;
        } else {
            leftPointer++;
        }
    }
};

How It Works

1. Initialize Two Pointers:

   • leftPointer starts at the beginning of the array.
   • rightPointer starts at the end of the array.

2. Iterate Until They Meet:

   • Calculate the sum of the elements at leftPointer and rightPointer.
   • If the sum matches the target, return the 1-indexed positions.
   • If the sum is greater than target, decrement the rightPointer to reduce the sum.
   • If the sum is less than target, increment the leftPointer to increase the sum.

3. Return the Indices:

   • Once the correct pair is found, the loop terminates and returns the indices.

Example Walkthrough

Let’s walk through the first example:

• Input: numbers = [2, 7, 11, 15], target = 9
• Initialization: leftPointer = 0, rightPointer = 3

Iteration Steps:

1. Calculate numbers[0] + numbers[3] = 2 + 15 = 17.
   • Too large, decrement rightPointer to 2.
2. Calculate numbers[0] + numbers[2] = 2 + 11 = 13.
   • Still too large, decrement rightPointer to 1.
3. Calculate numbers[0] + numbers[1] = 2 + 7 = 9.
   • Match found, return [1, 2].

Key Points

• 1-Indexed Adjustment: The problem specifies 1-based indexing, so we add 1 to both pointers before returning.
• Edge Cases: The constraints guarantee a single solution, so we don’t need to handle empty arrays or multiple matches.
• Optimization: Using the two-pointer approach ensures we meet the O(n) time complexity and constant space requirements.

Conclusion

The two-pointer method elegantly solves the "Two Sum II - Input Array Is Sorted" problem by leveraging the sorted nature of the input array. It’s a powerful technique that not only ensures efficiency but also adheres to space constraints, making it a go-to approach for similar problems. Happy coding!