Two-Pointer Technique in JavaScript

Introduction

Welcome to this unit's coding session! We're going to take a deep dive into an exciting technique — the two-pointer technique . This technique is a crucial skill for enhancing your algorithmic problem-solving abilities, especially when dealing with arrays. In this unit, we'll apply this technique to a problem that involves an array of integers and a target value. Let's get started!

Task Statement

Envision the problem at hand: we've been given an array of distinct integers and a target value. The task is to find all pairs of integers from the given array that sum up to the target value using the two-pointer technique. The function findPairs should take this array of integers and a target value as parameters. It should return an array containing pairs of numbers, sorted in ascending order by the first element of each pair. If no pairs satisfy this requirement, the function should return an empty array. Consider, for instance, an example in which you're given an array, let numbers = [1, 3, 5, 2, 8, -2], and target = 6 . In this case, the function should return [[ -2, 8 ], [ 1, 5 ]] because only these pairs from the input array of integers add up to the target value.

The Naive Approach

The naive approach to solving this problem would be to use a pair of nested loops to check each pair of numbers. This would have a time complexity of O(n^2) and a space complexity of O(1) . The naive approach can be time-consuming and inefficient, particularly for large arrays. Comparatively, the two-pointer technique makes the problem-solving process more efficient by eliminating unnecessary operations (repeatedly checking pairs that can't sum to the target), thus enhancing the overall performance and efficiency of the solution.

The Algorithm

We start out with sorting the array, preparing it for easier comparisons. We then apply the two-pointer technique: Two pointers, one at the start (left) and the other at the end (right), are initialized. In each iteration, we calculate the sum of the two numbers pointed to by the two respective pointers. If the sum is equal to the target value, the pair is added to the output list, and both pointers are moved toward the center. This is because we know there are no other potential pairs with the current values of numbers[left] and numbers[right] (since the numbers are distinct). When the sum is less than the target, we move the left pointer to the right (increasing the value of numbers[left]), and when the sum is greater than the target, we move the right pointer to the left (decreasing the value of numbers[right]). This process continues until the left pointer crosses the right pointer. At this point, all potential pairs have already been identified and added to the return list.

Join the 1M+ learners on CodeSignal

Be a part of our community of 1M+ users who develop and demonstrate their skills on CodeSignal

The first step to addressing this problem is sorting the array. By sorting the array of integers, we can use the two-pointer technique effectively, as we know that values on the left are always smaller, while those on the right are always larger. Let's start building our function with this step:

JavaScript

function findPairs(numbers, target) {
    // Sorting the array
    numbers.sort((a, b) => a - b);
    return [];
}

function findPairs(numbers, target) {
    // Sorting the array
    numbers.sort((a, b) => a - b);
    return [];
}

Once the array is sorted, let's move on to the next stage. We'll initialize two pointers — one at the start of the array, left, and the other at the end of the array, right. We'll also set up an empty array, pairs, to store our potential number pairs.

JavaScript

function findPairs(numbers, target) {
    numbers.sort((a, b) => a - b);
    let left = 0;
    let right = numbers.length - 1;
    let pairs = [];
    return pairs;
}

function findPairs(numbers, target) {
    numbers.sort((a, b) => a - b);
    let left = 0;
    let right = numbers.length - 1;
    let pairs = [];
    return pairs;
}

Finding Pairs

The most challenging and exciting part is the formation of pairs. We'll run a while loop until the left pointer crosses the right one. In each iteration, if the total equals the target, we'll store the pair and move one step from both ends. If the total is smaller than the target, we'll move one step to the right from the left, seeking a larger value. Conversely, if the total is larger than the target, we'll move one step to the left from the right, seeking a smaller value. Here is how it could be done:

JavaScript

function findPairs(numbers, target) {
    // Sorting the array in ascending order
    numbers.sort((a, b) => a - b);
    let left = 0;
    let right = numbers.length - 1;
    let pairs = [];

    // Using two-pointer technique to find pairs
    while (left < right) {
        let total = numbers[left] + numbers[right];

        if (total === target) {
            // Add the pair to the result array if the sum matches the target
            pairs.push([numbers[left], numbers[right]]);
            left++;  // Move left pointer one step to the right
            right--; // Move right pointer one step to the left
        } else if (total < target) {
            left++;  // Move left pointer one step to the right to increase the sum
        } else {
            right--; // Move right pointer one step to the left to decrease the sum
        }
    }
    return pairs; // Return the array of pairs that sum up to the target
}

// Example usage
let numbers = [1, 3, 5, 2, 8, -2];
let result = findPairs(numbers, 6);
console.log(result); // Output: [ [ -2, 8 ], [ 1, 5 ] ]

function findPairs(numbers, target) {
    // Sorting the array in ascending order
    numbers.sort((a, b) => a - b);
    let left = 0;
    let right = numbers.length - 1;
    let pairs = [];

    // Using two-pointer technique to find pairs
    while (left < right) {
        let total = numbers[left] + numbers[right];

        if (total === target) {
            // Add the pair to the result array if the sum matches the target
            pairs.push([numbers[left], numbers[right]]);
            left++;  // Move left pointer one step to the right
            right--; // Move right pointer one step to the left
        } else if (total < target) {
            left++;  // Move left pointer one step to the right to increase the sum
        } else {
            right--; // Move right pointer one step to the left to decrease the sum
        }
    }
    return pairs; // Return the array of pairs that sum up to the target
}

// Example usage
let numbers = [1, 3, 5, 2, 8, -2];
let result = findPairs(numbers, 6);
console.log(result); // Output: [ [ -2, 8 ], [ 1, 5 ] ]

In the findPairs function, we first sort the array, preparing it for easier pair identification. We then initialize two pointers and an empty array to store the pairs. Using a while loop, we move the pointers according to the sum they point to, finding and storing pairs that add up to the target value. Finally, the pairs array containing the valid pairs is returned.

Sorting Operation: The numbers.sort((a, b) => a - b) function sorts the array in ascending order. The time complexity of this sorting step is O(n log n), where n is the number of elements in the array.
Two-Pointer Traversal: After sorting, the whileloop traverses the array with two pointers (left and right). Each pointer moves towards the center of the array and makes a constant amount of work per iteration (either moving the left pointer, moving the right pointer, or both). The total number of iterations is linear in the number of elements, so the time complexity for this part is O(n). Since the sorting step dominates the time complexity, the overall time complexity of the function is O(n log n).

The space complexity is O(n) because, in the worst-case scenario (when all elements form a pair summing up to the target), the return list would require space for n/2 pairs. The 1/2 is just a constant, and the polynomial expression is of order 1, hence O(n).

Congratulations on successfully handling a problem that requires the imperative two-pointer technique! This scenario involved understanding and meticulously applying the two-pointer technique to identify all relevant pairs of integers. In this task, we learned how summarizing concepts can ultimately aid us in finding a solution more efficiently, without having to approach each element explicitly.

Now, it's time for some practice! In the subsequent practice session, you'll handle similar problems that demand the use of the two-pointer method. Take everything you've learned from this lesson and apply it directly to the practice! Thank you for attending the session, and keep up the excellent work!

Introduction

Task Statement

The Naive Approach

The Algorithm

Join the 1M+ learners on CodeSignal

Sorting the Array

Initializing Pointers & Pair Storage

Finding Pairs

Complexity Analysis

Lesson Summary