167. Two Sum II - Input Array Is Sorted

 

Solving the Two Sum II Problem with a Two-Pointer Technique in JavaScript

When faced with the task of finding two numbers in a sorted array that sum up to a specific target, the Two Sum II problem on LeetCode provides a classic challenge. In this post, we'll explore an efficient and elegant solution using the two-pointer technique in JavaScript. This approach ensures that we find the solution in linear time.

Problem Statement

Given an array of integers numbers that is already sorted in non-decreasing order, find two numbers such that they add up to a specific target number. Return the indices of the two numbers (1-based index) as an integer array [index1, index2]. You may assume that each input would have exactly one solution, and you may not use the same element twice.

Example

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

Intuition

Since the array is sorted, we can efficiently find the two numbers using the two-pointer technique. This method involves initializing two pointers at different ends of the array and moving them inward based on the sum of the elements at these pointers.

Approach

  1. Initialize Pointers:

    • Start with one pointer (si) at the beginning of the array.

    • Place the other pointer (li) at the end of the array.

  2. Iterate with a While Loop:

    • Use a while loop to move the pointers until they meet.

    • If the sum of the numbers at the two pointers equals the target, return their 1-based indices.

    • If the sum is greater than the target, decrement the end pointer to reduce the sum.

    • If the sum is less than the target, increment the start pointer to increase the sum.

Code Implementation

Here's the JavaScript implementation of the Two Sum II problem using the two-pointer technique:

javascript
var twoSum = function(numbers, target) {
    let si = 0;
    let li = numbers.length - 1;
    while (si <= li) {
        if (numbers[si] + numbers[li] === target) {
            return [si + 1, li + 1];
        } else if (numbers[si] + numbers[li] > target) {
            li--;
        } else {
            si++;
        }
    }
};

Complexity Analysis

  • Time Complexity: O(n), where n is the length of the numbers array. This is because each element is checked at most once due to the two-pointer technique.

  • Space Complexity: O(1), since we only use a few extra variables regardless of the input size.

Conclusion

The two-pointer technique is a powerful tool when dealing with sorted arrays. It allows us to efficiently find pairs of elements that meet certain criteria, such as summing to a specific target. By leveraging this approach, we can solve the Two Sum II problem in linear time, making it both elegant and efficient.

For more detailed explanations and additional solutions, check out the discussion on LeetCode: https://leetcode.com/problems/two-sum-ii-input-array-is-sorted/solutions/6146809/easy-and-simple-approach-by-bikash_kumar-88wv/ .

Happy coding! šŸ˜Š

Comments

Post a Comment

Popular posts from this blog

3Sum Closest: O(n²) Two-Pointer Magic šŸš€ leetcode: 16

Three Sum Closest - LeetCode Solution In this blog post, we'll dive into the Three Sum Closest problem, a popular coding challenge on LeetCode. We'll explore the intuition behind the solution, discuss the approach, analyze the complexity, and provide a detailed explanation of the code. Additionally, I'll share my LeetCode solution link for further reference. Problem Statement Given an integer array nums of length n and an integer target , find three integers in nums such that the sum is closest to target . Return the sum of the three integers. You may assume that each input would have exactly one solution. Intuition The problem requires finding three numbers in the array whose sum is as close as possible to the target. To efficiently find such a triplet, we can use a combination of sorting and the two-pointer technique . Sorting : First, sort the array. This allows us to use the two-po...
Read more

Kadane's Algorithm: Maximum Subarray Problem - LeetCode(53) Solution

Maximum Subarray Problem - LeetCode Solution Maximum Subarray Problem - LeetCode Solution Problem Statement Given an integer array nums , find the contiguous subarray (containing at least one number) that has the largest sum and return its sum. Intuition The problem requires finding the contiguous subarray with the maximum sum. A brute force approach would involve checking all subarrays, but this would be inefficient. Instead, we use Kadane's Algorithm , which efficiently finds the maximum sum subarray in O(n) time. Approach Initialize two variables: total (running sum) and maxi (maximum sum encountered so far). Iterate through the array: Add the current element to total . Update maxi with the maximum of maxi and total . If total becomes negative, reset it to zero. Return maxi as the maximum sub...
Read more

14. Longest Common Prefix

  Finding the Longest Common Prefix in JavaScript When working with arrays of strings, a common problem is finding the longest common prefix among these strings. The longest common prefix is the initial portion of all strings in the array that is identical. This is a frequent problem on coding platforms like LeetCode, and it's essential to understand how to tackle it efficiently. In this blog post, we'll dive into the intuition, approach, and complexity of finding the longest common prefix in JavaScript. Intuition The intuition behind finding the longest common prefix is simple. By sorting the array of strings lexicographically (alphabetically), we can bring the smallest and largest strings to the beginning and end of the array. The common prefix between the first and last string in this sorted array will give us the longest common prefix for the entire array. This approach leverages the natural order of strings to simplify our task. Approach Sort the Array : First, we sort the...
Read more