Two Pointer Approach
In this blog I would like to write something about this important topic which is the Two Pointer Approach.
This is a really easy and simplistic approach usually taken to find searching pairs in sorted arrays. The question given is “ Given an array A find two elements A[i], A[j] such that their sum is X”.
Now taking the naive approach in this case.
We would write the algorithm as follows-
for (i = 0; i < N; i++) {
for (j = 0; j < N; j++) {
if (A[i] + A[j] == X)
return true; // pair exists
if (A[i] + A[j] > X)
break; // as the array is sorted
}
Credits GeeksForGeeks
In this approach we get the complexity as O(n²)
This time complexity can be improved by using the approach of two pointers.
We first take two pointers, one is situated at the first element of the array whereas the other one is situated at the last element of the array. we keep adding both the values which are kept at both the pointers, if the sum which we want is returned then the approach stops. If their sum is smaller than x then we shift the left pointer or if their sum is greater then we shift the right pointer and in this way we get the sum which is needed.
bool isPairSum(A[], N, X)
{
// represents first pointer
int i = 0;
// represents second pointer
int j = N - 1;
while (i < j) {
// If we find a pair
if (A[i] + A[j] == X)
return true;
// If sum of elements at current
// pointers is less, we move towards
// higher values by doing i++
else if (A[i] + A[j] < X)
i++;
// If sum of elements at current
// pointers is more, we move towards
// lower values by doing j--
else
j--;
}
return false;
}
Credits GeeksforGeeks
This approach reduces the time complexity to O(n).
