Two Pointer Technique

Suppose we have a sorted array. We have to find if the number “x” is present as the sum of two distinct elements in that array, i.e, a[i]+a[j] = x ∀ i,j ∈ [0,n-1]. i ≠ j

Firstly we could think of doing it in O( $n^2$ ) using two for loops. But we could also do this question in O(n) using the Two-Pointer technique.

Note: Not just this but many such questions can be done using Two-Pointer Algorithm.

Welcome to our comprehensive guide on the Two Pointer Technique, an invaluable algorithmic approach that can significantly enhance your problem-solving skills. In this blog post, we’ll delve into the inner workings of the Two Pointer Technique, exploring its applications in various programming scenarios. Whether you’re a beginner or an experienced developer, this technique will empower you to optimize time and space complexity while efficiently solving complex array and linked list problems.

What is the Two Pointer Technique?

The Two Pointer Technique is a strategy that involves using two pointers or indices to traverse through a data structure such as an array or a linked list. These pointers move at different speeds or in different directions, allowing us to perform operations efficiently. The technique is based on the idea that by manipulating the positions of the pointers intelligently, we can solve a variety of problems in a more optimal way.

How does the Two Pointer Technique work?

The Two Pointer Technique typically involves initializing two pointers at different locations within the data structure and manipulating their positions based on specific conditions. By moving the pointers in a systematic manner, we can navigate through the structure, compare elements, and perform necessary operations. This technique is particularly useful in scenarios where the problem involves searching, sorting, or finding patterns within the data.

Two Pointer Technique intuition

let’s see the following example to understand two pointer method.

. Let a[] ={1,2,3,4,5}, x = 5.
. let ‘l’ and ‘r’ be the left and right-most index of the array resp. I.e, l=0, r=4.
. now a[l]+a[r] is 1+5, i.e 6. So this number is greater than x.
. so decrement r, only then our sum will reduce
. Note, incrementing I will increase the sum, and decrementing r will reduce the sum
Two-Pointer Technique:
if(a[l]+a[r] > x) r–;
else if ( a[l]+a[r] < x) l++;
else print(element found);

// two pointer technique
int x=5;
int l=0,r=n-1;
while(l<r)
{
     if(a[l]+a[r] > x) r--; // decrementing sum
     else if ( a[l]+a[r] < x) l++; // incrementing sum
     else {cout<<"two elements found whose sum is x\n"; break;}
}

Bonus:
You can try the below popularly asked interview question:
1. find if the number “x” is present as the sum of three distinct elements in an array, i.e,
a[i] + a[j] + a[k] = x ∀ i,j,k ∈ [0,n-1]. Where i ≠ j ≠ k.
Expected time complexity: O( $n^2$ )

Advantages and benefits of using Two Pointer technique:

Improved time complexity: The Two Pointer Technique often allows us to solve problems with better time complexity compared to other approaches. By efficiently traversing through the data structure, we can eliminate unnecessary iterations, resulting in faster solutions.
Reduced space complexity: In many cases, the Two Pointer Technique minimizes the need for extra data structures or additional space, thereby reducing the space complexity of our algorithms. This is especially beneficial when dealing with large datasets.
Simplicity and readability: The technique is relatively straightforward and easy to understand once you grasp the concept. It simplifies the problem-solving process by breaking it down into smaller steps and providing a clear strategy for traversal and manipulation.
Versatility: The Two Pointer Technique can be applied to a wide range of problems involving arrays, linked lists, strings, and more. Its versatility makes it a valuable tool in a programmer’s arsenal.

You might also like to check the following articles:

Algorithm