Two-Pointer Algorithm in JavaScript

The two-pointer technique is a powerful approach to solving certain problems with optimal time and space complexity. One common application is finding pairs in a sorted array that sum up to a given target. In this example, we’ll delve into the two-pointer algorithm to solve this problem efficiently.

Problem Statement

Given a sorted array and a target sum, we aim to find two elements whose sum equals the target.

Example

javascriptCopy code

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

Implementation of Two-Pointer Algorithm

function twoSum(numbers, target) {
    let i = 0;
    let j = numbers.length - 1;

    while (i < j) {
        let sum = numbers[i] + numbers[j];

        if (sum === target) {
            return [i + 1, j + 1];
        } else if (sum < target) {
            i++;
        } else {
            j--;
        }
    }

    return [-1, -1];
}

Algorithm Explanation

1. Initialize two pointers, i and j, pointing to the start and end of the array, respectively.
2. Check the sum of elements at i and j.
3. If the sum equals the target, return the indices of the elements.
4. If the sum is less than the target, move the i pointer to the right.
5. If the sum is greater than the target, move the j pointer to the left.
6. Repeat steps 2-5 until i and j pointers meet or cross.
7. If the sum is never equal to the target, return [-1, -1].

This algorithm ensures an efficient O(n) time complexity and O(1) space complexity. The two-pointer technique is particularly useful in scenarios where elements need to be compared or traversed in a sorted or specific order. Understanding and implementing this algorithm can significantly enhance problem-solving skills in algorithmic challenges.