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




Initialize Two Pointers:



leftPointer starts at the beginning of the array.

rightPointer starts at the end of the array.



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.



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:



Calculate numbers[0]   numbers[3] = 2   15 = 17. 


Too large, decrement rightPointer to 2.


Calculate numbers[0]   numbers[2] = 2   11 = 13. 


Still too large, decrement rightPointer to 1.


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!


          

            
        
The above is the detailed content of Efficiently Solving Two Sum II - Input Array Is Sorted. For more information, please follow other related articles on the PHP Chinese website!