Couple of days ago while solving a problem, I encountered a situation where my code was getting Terminated Due to Timeout error , so after searching a bit on the online forums I got to know about this famous algorithm the Two Pointer Algorithm , which simply helps your problem to get reduced from \(O(N^2)\) to \(O(N)\).In this blog post I will try to sum up this technique! So let's take a motivation problem based on the same algorithm. Given a Sorted Array and a number. Our task is to check if there exists any two number whose sum equals to that number. Let the array be A and the number be sum.

The naive algorithm one would think of is,

 1for(int i=0;i<array_size;i++)
 3  for(int j=0;j<array_size;j++)
 4  {
 5    if(A[i]+A[j]==sum)
 6    {
 7      cout<<"Found!"<<"\n";
 8      break;
 9    }
10  }

Yes, this is what I did intially. So, now let's try to solve this problem with TPA technique. Let's consider a Sorted Array = {10,15,20,25,40,50} and the Number to find is 40 so the output will be Yes, because we do have such two number exists in our array whose sum is 40 and the numbers are {15,25}. This is how it works, Let's name the first pointer be start starting from first index and the another pointer to be end pointing towards the last index,

Two Pointer Explanation

So, this is what the Two Pointer Algorithm is!

Here's the Algorithm : "Two Pointer Algorithm"

 1bool fun(int sum, int size, int* A)
 3  int start = 0, end = size-1;
 4  while(start<end)
 5  {
 6    if(A[start]+A[end]==sum){
 7     	return 1;
 8    }
 9    else if(A[start]+A[end]>sum){
10    	end--;
11    }
12    else{
13    	start++;
14    }
15  }
16  return 0;