LeetCode Challenge: 167. Two Sum II - Input Array Is Sorted - JavaScript Solution 🚀

Top Interview 150

The Two Sum II problem leverages the fact that the input array is sorted. By using a two-pointer technique, we can solve it efficiently in linear time with constant space.

---

🚀 Problem Description

Given a 1-indexed sorted array numbers, find two numbers such that their sum equals the target.

• Return the indices of these two numbers as [index1, index2] such that 1 <= index1 < index2 <= numbers.length.
• You cannot use the same element twice.
• There is exactly one solution guaranteed.

---

💡 Examples

Example 1

Input: numbers = [2,7,11,15], target = 9  
Output: [1,2]  
Explanation: The sum of 2 and 7 is 9. Therefore, we return [1, 2].

Example 2

Input: numbers = [2,3,4], target = 6  
Output: [1,3]  
Explanation: The sum of 2 and 4 is 6. Therefore, we return [1, 3].

Example 3

Input: numbers = [-1,0], target = -1  
Output: [1,2]  
Explanation: The sum of -1 and 0 is -1. Therefore, we return [1, 2].

---

🏆 JavaScript Solution

We’ll use the two-pointer technique, which works perfectly for sorted arrays.

Implementation

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) {
            left++;
        } else {
            right--;
        }
    }
};

---

🔍 How It Works

1. Pointers Initialization:

   • left starts at index 0.
   • right starts at the last index.

2. Sum Comparison:

   • Calculate the sum of the numbers at the left and right pointers.
   • If the sum equals the target, return the indices.
   • If the sum is less than the target, move the left pointer to the right.
   • If the sum is greater than the target, move the right pointer to the left.

3. Stop When Pointers Meet:

   • The loop stops when left >= right.

---

🔑 Complexity Analysis

• Time Complexity: O(n), where n=numbers.length.

  • Each pointer moves at most once through the array.

• Space Complexity: O(1), as we use no extra space.

---

📋 Dry Run

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

Output: [1, 2]

---

Follow-Up: Why Two Pointers Work

1. Sorted Array:

   • The order guarantees that moving the left pointer increases the sum, while moving the right pointer decreases the sum.

2. Efficiency:

   • No need for nested loops, as a single traversal suffices.

3. Scalability:

   • Handles large arrays efficiently.

---

✨ Pro Tips for Interviews

1. Discuss Edge Cases:

   • Minimal array length ([2, 3], target 5).
   • Negative numbers in the array ([-3, -1, 4], target 3).

2. Explain Complexity:

   • Highlight the linear time complexity as a key advantage over brute force.

3. Understand Indexing:

   • Remember that the problem uses 1-indexed positions.

---

📚 Learn More

Check out the detailed explanation and code walkthrough on my Dev.to post:
👉 Is Subsequence - JavaScript Solution

How would you optimize or approach this problem differently? Let’s discuss! 🚀

JavaScript #LeetCode #CodingInterview #ProblemSolving

Comments

[Rahul Kumar Barnwal]

Follow Me on GitHub 🚀

If you found this solution helpful, check out more of my projects and solutions on my GitHub profile.

Don't forget to follow for more updates!