Desired Triplet.

Consider these problems Triplets sum in an array and count the triplets. One common attribute is that you are given an array and you need to find the desired triplet in O(N^2). And the common approach that we need to follow is sort that array. Now fix each element in this array and then put two pointers at starting of the array and ending of the array. You consider this two pointed elements as the desired two. If this two are less than desired increase pointer 1 otherwise decrease pointer 2.

int countTriplet(int arr[], int n) 
? ? ? ? // code here
? ? ? ? Arrays.sort(arr);
? ? ? ? int count = 0;
? ? ? ? for(int i = 0; i < n; i++){
? ? ? ? ? ? int sum = arr[i];
? ? ? ? ? ? arr[i] = -1;
? ? ? ? ? ? int p1 = 0;
? ? ? ? ? ? int p2 = n-1;
? ? ? ? ? ? while(p1<p2){
? ? ? ? ? ? ? ? if(arr[p1]==-1){
? ? ? ? ? ? ? ? ? ? p1++;
? ? ? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(arr[p2]==-1){
? ? ? ? ? ? ? ? ? ? p2--;
? ? ? ? ? ? ? ? ? ? continue;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? if(arr[p1]+arr[p2] == sum){
? ? ? ? ? ? ? ? ? ? count++;
? ? ? ? ? ? ? ? ? ? p1++;
? ? ? ? ? ? ? ? ? ? p2--;
? ? ? ? ? ? ? ? }
? ? ? ? ? ? ? ? else if(arr[p1]+arr[p2] < sum) p1++;
? ? ? ? ? ? ? ? else p2--;
? ? ? ? ? ? }
? ? ? ? ? ? arr[i]=sum;
? ? ? ? }
? ? ? ? return count;        

? Well this is the common standard idea, then why am i writing this??. Look at the above snippet. what i like to share is that the fixed element is converted into something that is not seen. Ex : In the above case array only expects the positive elements. So we converted into 0 and while traversing if we come across this zero we pass through it. Later we change it back to the original form.

So in this article we have seen that to find a triplet generally we follow the above approach and how to hide a element.