What is Two pointer technique?
A two pointer technique is a technique where given a sorted array we have two starting points or two points of consideration as they both move towards the middle of the array being iterated over, the two pointer technique is a useful tool to utilize when searching for pairs in a sorted array. Although not it’s only use case, when used this technique can save both time and space complexity.
when iterating through the data in a linear fashion we usually have a single entry point and we move through the data in one direction.
Example:
Given a sorted array we need to find the pair of number which sums up to the given number x.
Approach 1: Brute Force Solution
In the brute force solution of the problem we use a loop within a loop to iterate over all of the elements in the array, forming every possible pair combination and having the time complexity of O(n^2)
This approach takes too much time to run, which can further be optimized to run in O(n) time complexity.
Approach 2: Two Pointer Solution
Now let’s look how the two pointer solution works and gives a better time complexity than brute force solution,
We take two pointers one which points to the first element(low) and one which points to the last element(high) of the array now according to the problem statement given we add the last and the first values together and check if the sum matches with the provided sum (x) if the computed sum is less than the given sum(x) then we increment the low pointer and if the sum is greater the given sum(x) we decrement the high pointer, we do this till we get the desired sum or the low > high.
Boolean pairSum(int Arr[], int n, int x)
{
// represents first pointer
int low = 0;
// represents second pointer
int high = n - 1;
while (low < high) {
// If we find a pair
if (Arr[low] + Arr[high] == x)
return true;
// If sum of elements at current
// pointers is less, we move towards
// higher values by doing low++
else if (Arr[low] + Arr[high] < x)
low++;
// If sum of elements at current
// pointers is more, we move towards
// lower values by doing high--
else
high--;
}
return false;
}
For this algorithm to work effectively we assume that we are given a sorted array and we move the pointers toward the center of the array so we do not miss any pair and we move one pointer only if the above conditions are met so that no pair is left untouched and every pair is checked once.