Two-Pointer Technique - Stack Thrive

The Two Pointers Technique is a simple yet effective method commonly used for searching pairs in a sorted array.

The technique is based on the idea of having two pointers, one at the start and the other at the end of the array, and then moving these pointers conditionally based on the sum of the values at both pointers.

What is the Two-Pointer Technique?

The Two-Pointer Technique is a method where two pointers iterate through an array simultaneously, each moving at a different speed or under different conditions. This technique is often used to solve array-related problems more efficiently.

How and When to Use the Two-Pointer Technique?

The Two-Pointer Technique is used when you need to track two positions in an array at the same time. It’s particularly useful when the array is sorted or when you’re looking for pairs of elements that meet certain conditions.

You can use the Two-Pointer Technique in any situation where you need to traverse an array in a non-standard way.

For example, it’s used in problems where you need to find a pair of elements that sum to a specific value, or to find the middle element of a linked list.

Example

let’s use the array [2, 3, 5, 8, 9, 10, 11] and find pairs that sum up to 15 using the two-pointer technique.

JavaScript

function twoPointer(arr, target) {
    // Initialize two pointers: one at the start (left) and one at the end (right) of the array
    let left = 0;
    let right = arr.length - 1;

    // Initialize an empty array to store the pairs
    let pairs = [];

    // Start a while loop that continues as long as left is less than right
    while (left < right) {
        // Calculate the sum of the elements at the left and right pointers
        let sum = arr[left] + arr[right];

        // If the sum is equal to the target, we have found a pair
        if (sum === target) {
            // Add the pair to the pairs array
            pairs.push([arr[left], arr[right]]);

            // Move the left pointer one step to the right and the right pointer one step to the left
            left++;
            right--;
        } 
        // If the sum is less than the target, move the left pointer one step to the right to increase the sum
        else if (sum < target) {
            left++;
        } 
        // If the sum is greater than the target, move the right pointer one step to the left to decrease the sum
        else {
            right--;
        }
    }

    // Return the pairs array which contains all pairs that sum up to the target
    return pairs;
}

let arr = [2, 3, 5, 8, 9, 10, 11];
let target = 15;
let pairs = twoPointer(arr, target);

// Print the pairs
console.log(pairs);

Now, let’s break down the steps:

1. We start with an array: [2, 3, 5, 8, 9, 10, 11] and a target value: 15.

2. We initialize two pointers, left and right, at the start and end of the array, respectively. So, left is pointing to 2 and right is pointing to 11.

3. We calculate the sum of the numbers at the positions pointed to by left and right, which is 2 + 11 = 13.

4. Since 13 is less than 15, we move the left pointer one step to the right. Now, left is pointing to 3 and right is still pointing to 11.

5. We calculate the new sum, which is 3 + 11 = 14.

6. Since 14 is still less than 15, we move the left pointer one step to the right again. Now, left is pointing to 5 and right is still pointing to 11.

7. We calculate the new sum, which is 5 + 11 = 16.

8. Since 16 is greater than 15, we move the right pointer one step to the left. Now, left is pointing to 5 and right is pointing to 10.

9. We calculate the new sum, which is 5 + 10 = 15.

10. Since 15 is equal to 15, we’ve found our pair! It’s [5, 10]. We add this pair to the pairs array, then move the left pointer one step to the right and the right pointer one step to the left to continue the search.

11. The loop continues until the left pointer is no longer less than the right pointer. In this case, no other pairs that sum up to 15 are found.

12. After the loop finishes, the function returns the pairs array, which contains all pairs of numbers that add up to the target sum. In this case, the function returns [[5, 10]].

Complexity

The time and space complexity of the two-pointer technique can vary depending on the specific problem and implementation.

Time Complexity:

The time complexity of the two-pointer technique is typically O(n), where n is the size of the array or list. This is because each pointer will traverse the array or list at most once, resulting in a linear number of operations.

Space Complexity:

The space complexity of the two-pointer technique is usually O(1), which means it uses constant extra space. This is because the two-pointer technique doesn’t require any additional data structures that grow with the size of the input. The only extra space used is for the two pointers and a few variables, which doesn’t change with the size of the array or list.

Please note that these complexities can change based on the specific problem and how the two-pointer technique is used. For example, if you’re using the two-pointer technique to find all pairs of numbers in an array that meet a certain condition and storing those pairs in a new array, the space complexity would be O(n) because the new array could potentially contain n/2 pairs.

Pros of the Two-Pointer Technique:

Efficiency: The two-pointer technique can significantly reduce the time complexity of algorithms. For example, in problems where you need to find pairs that meet a certain condition (like summing to a target), a naive approach would be to use two nested loops, resulting in O(n^2) time complexity. The two-pointer technique can solve these problems in O(n) time.
Simplicity: The two-pointer technique is conceptually simple and easy to understand. Once you grasp the idea of maintaining two pointers and moving them based on certain conditions, it becomes straightforward to apply this technique to a variety of problems.
No Extra Space: The two-pointer technique doesn’t require any additional data structures, so it doesn’t increase the space complexity of the algorithm.

Cons of the Two-Pointer Technique:

Applicability: The two-pointer technique is not a universal solution. It can only be applied to certain types of problems, typically those involving arrays or linked lists. Furthermore, it often requires the array or list to be sorted.
Edge Cases: Implementing the two-pointer technique can sometimes be tricky due to edge cases. For example, you need to be careful to avoid off-by-one errors and ensure that the pointers don’t cross each other.
Readability: While the two-pointer technique is conceptually simple, the resulting code can sometimes be hard to read, especially for those not familiar with the technique. It’s important to comment your code well when using this technique.

Conclusion

The Two-Pointer Technique is a powerful tool that can help you solve array-related problems more efficiently. By tracking two positions in the array at the same time, you can often reduce the time complexity of your algorithm.

However, like all techniques, it’s not a one-size-fits-all solution. It’s important to understand where and when to use it to make the most of its benefits.

Remember, practice makes perfect! Try implementing the Two-Pointer Technique in different coding problems to get a good grasp of it.

Happy coding 😄!

Learn More: