Count Triplets

public class Solution {

    public static int countAllTripletSum(Node head, int x) {

        // Write your code here.

        Node temp = head;

        int count = 1;

        while(temp!=null && temp.next!=null){

            temp=temp.next;

            count++;

        }

        if(count<=2){

            return 0;

        }

        int curr=0,res=0;

        Node h,t;

        while(head!=temp){

            curr=x-head.data;

            h=head.next;

            t=temp;

            while(h!=t && h.prev!=t){

                if((h.data + t.data) == curr){

                    res++;

                    t=t.prev;

                    h=h.next;

                }else if((h.data + t.data) > curr){

                    t=t.prev;

                }else{

                    h=h.next;

                }

            }

            head=head.next;

        }

        return res;

    }

}

int countAllTripletSum(Node *head, int x)

{

    int cnt = 0;

    if(head==NULL)  return cnt;

    Node * right;

    Node*temp = head;

    while(temp->next != NULL){

        temp = temp->next;

    }

   right=temp;

    Node * curr = head;

    while(curr!=NULL && curr->next!=NULL&&curr->next->next!=NULL){

        right = temp;

        Node * left = curr->next;

        int target = x - curr->data;

        while(left!=right){

          int sum= left->data + right->data;

          if(sum==target)

           {

               cnt++;

             right = right->prev;

           }

           else if(sum > target){

               right=right->prev;

           }

           else{

                left = left->next;

           }

        }

        curr=curr->next;

    }

    return cnt;

}

#include <bits/stdc++.h>

/***************************************

    Following is the Node class already written.

    class Node

    {

    public:

        int data;

        Node* next;

        Node* prev;

        Node(int data)

        {

            next = NULL; prev=NULL;

            this->data = data;

        }

        ~Node()

        {

            if (next != NULL)

            {

                delete next;

            }

        }

    };

***************************************/

void solve(Node* left,Node* right,int key,int& ans)

{

    if(left==NULL)

    return; 

    while(left!=right)

    {

        if(left->data+right->data==key)

        {

           ans+=1;

           left=left->next;

        }else{

            if(left->data+right->data<key)

            {

                left=left->next;

            }else{

                right=right->prev;

            }

        }

    }

}

int countAllTripletSum(Node *head, int x)

{

    if(head==NULL)

    return 0;

    Node* tail=head;

    while(tail->next)

    {

        tail=tail->next;

    }

    int ans=0;

    for(Node* num1=head;  num1;    num1=num1->next)

    {

       solve(num1->next,tail,x-num1->data,ans);

    }

    return ans;

}

def countAllTripletSum(head, x):
    arr=[]
    while head is not None:
        arr.append(head.data)
        head=head.next
    ans=0
    for i in range(len(arr)-2):
        l=i+1
        j=len(arr)-1
        while l<j:
            if arr[i]+arr[l]+arr[j]==x:
                ans+=1
                l+=1
                j-=1
            elif arr[i]+arr[l]+arr[j]<x:
                l+=1
            
            else:
                j-=1

    return ans

#include <bits/stdc++.h> 
int countAllTripletSum(Node *head, int x){
    int count = 0;
    if(head == NULL) return count;

    Node *tail = head;
    while(tail->next) tail = tail->next;

    for(Node *num1 = head;num1->next && num1->next->next;num1=num1->next){
        Node *num2 = num1->next , *num3 = tail;
        int target = x - num1->data;
        while(num2 != num3){
            int currSum = num2->data + num3->data;
            count += (currSum == target);
            if(currSum <= target) num2 = num2->next;
            else num3 = num3->prev;
        }
    }

    return count;
}

int pairSum(Node * head, int k){
    Node *start=head;
    Node *end=head;
    int cnt=0;
    while(end->next) end=end->next;
    while(start!=end && end->next!=start){
        int sum=start->data + end->data;
        if(sum==k){
            cnt++;
            start=start->next;
            end=end->prev;
        }
        else if(sum<k) start=start->next;
        else end=end->prev;
    }
    return cnt;
}

int countAllTripletSum(Node *head, int x)
{
    // Write your code here.
    Node *start=head;
    Node *end=head;
    int cnt=0;
    unordered_map<int,int> mp;
    
    while(start && start->next){
        int k=x-start->data;
        cnt+=pairSum(start->next,k);
        start=start->next;
    }
    return cnt;
}

int countAllTripletSum(Node *head, int x) {    // Write your code here.    unordered_map<int,int>mp;     Node *curr=head;     int count=0;     while(curr!=NULL){         Node *res=curr->next;         while(res!=NULL){             if(mp.find(x-curr->data-res->data)!=mp.end()){                 count++;                                               }             res=res->next;                      }         mp[curr->data]++;         curr=curr->next;              }          return count; }

Two pointers Approach  with T.C = O(N*N),  S.C = O(N).

int countTriplets(struct Node* head, int x)  {     // code here.    vector<int>v;    while(head!=NULL){        v.push_back(head->data);        head=head->next;    }        int count=0;    for(int i=0; i<v.size(); i++){        int s=i+1, e=v.size()-1;        while(s<e){            if(v[i] + v[s] + v[e] > x)                e--;                        else if(v[i] + v[s] + v[e] < x)                s++;                        else{                count++;                s++;                e--;            }            }    }    return count; } 

Hey everyone, creating this thread to discuss the interview problem - Count Triplets.

Practise this interview question on Coding Ninjas Studio (hyperlinked with the following link): Count Triplets