DEV Community

Cover image for LeetCode Challenge: 167. Two Sum II - Input Array Is Sorted - JavaScript Solution πŸš€
Rahul Kumar Barnwal
Rahul Kumar Barnwal

Posted on

2 1 1 1 1

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].
Enter fullscreen mode Exit fullscreen mode

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].
Enter fullscreen mode Exit fullscreen mode

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].
Enter fullscreen mode Exit fullscreen mode

πŸ† 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--;
        }
    }
};
Enter fullscreen mode Exit fullscreen mode

πŸ” 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

Two Sum
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

Sentry image

Hands-on debugging session: instrument, monitor, and fix

Join Lazar for a hands-on session where you’ll build it, break it, debug it, and fix it. You’ll set up Sentry, track errors, use Session Replay and Tracing, and leverage some good ol’ AI to find and fix issues fast.

RSVP here β†’

Top comments (1)

Collapse
 
rahulgithubweb profile image
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!

Billboard image

The Next Generation Developer Platform

Coherence is the first Platform-as-a-Service you can control. Unlike "black-box" platforms that are opinionated about the infra you can deploy, Coherence is powered by CNC, the open-source IaC framework, which offers limitless customization.

Learn more

πŸ‘‹ Kindness is contagious

Please leave a ❀️ or a friendly comment on this post if you found it helpful!

Okay