DEV Community

Abhinav
Abhinav

Posted on

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++;
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

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!

SurveyJS custom survey software

JavaScript UI Libraries for Surveys and Forms

SurveyJS lets you build a JSON-based form management system that integrates with any backend, giving you full control over your data and no user limits. Includes support for custom question types, skip logic, integrated CCS editor, PDF export, real-time analytics & more.

Learn more

Top comments (0)

AWS Security LIVE!

Tune in for AWS Security LIVE!

Join AWS Security LIVE! for expert insights and actionable tips to protect your organization and keep security teams prepared.

Learn More

👋 Kindness is contagious

Immerse yourself in a wealth of knowledge with this piece, supported by the inclusive DEV Community—every developer, no matter where they are in their journey, is invited to contribute to our collective wisdom.

A simple “thank you” goes a long way—express your gratitude below in the comments!

Gathering insights enriches our journey on DEV and fortifies our community ties. Did you find this article valuable? Taking a moment to thank the author can have a significant impact.

Okay