Count the number of times a particular triplet (x,y,z) appear in the array in O(N*N) time or even better , O(N) time .

Question

Expected Time Complexity : O(N*N) , where 'N'  is the size of array .

1<=A[i]<=1000000

1<=N<=100000

Example :

100 200 400 10000 5 5 300

(x,y,z) = (100,200,300)

Output : There is only 1 triplet  (100,200,300) in the array , hence answer is '1' .

Note :

1)Algorithm-explanation is must .

2)Adding code is optional .

3)Use Format option while adding code

 

The triplet is valid only if x occurs before y, and y occurs before z .

Answer 1

I think i get it wrong, coz O(n) solution exists. Jump to last for debugged ouput and someone first tell
me wether or not this was the logic that question was expecting. Then i will edit and make algo clear +
remove unnecessary code.
Just Let me know 

#include<bits/stdc++.h>

using namespace std;


void naiveSolution(vector<int> &a, vector<int> &b)    // TIME COMPLEXITY O(n3)

{

    int n = a.size(),        ct = 0;


    cout<<"Indexex are as follows "<<endl;

    for(int i=0 ; i<n; i++)

    {

        int smallCt = 0;

        if(a[i] == b[0])

        for(int j=i+1 ; j<n ; j++)

        {

            if(a[j] == b[1])

            for(int k=j+1 ; k<n ; k++)

            {

                if(a[k] == b[2])

                    printf("%d %d %d\n" , i , j , k),

                    ct++;


            }

        }

    }

    cout<<"Total count is using Naive with time complexity O(n3) is \t\t="<<ct<<endl;

}


void testSolution(vector<int> &a, vector<int> &b)     // timeComplxity O(n);    

{

    int n = a.size();

    int ct1 = 0 , ct2 = 0 , ct3 = 0;


    for(auto i : a)

    {

        if(i == b[0])

            ct1++;

        else if(i == b[1])

            ct2 += ct1;

        else if(i == b[2])

            ct3 += ct2;

    }

    cout<<"Total count is using Optimised approach is with complexity O(n) is\t="<<ct3<<endl;

}

int32_t main()

{

    vector<int> TC1 = {1,2,1,3,2,3,2,3};

    vector<int> TC2 = {1,2,3,3,3,3};    

    vector<int> TC3 = {3,2,3,1,2,3,2,1,3,2,3,1,3};    

    vector<int> TC4 = {3,3,3,3,3};    

  

    vector<int> b = {1,2,3};

    vector<int> TC = TC1;


    naiveSolution(TC,b);

    testSolution(TC,b);

}


Sample TEST CASE , idk whether or not I understand this question correctly, Coz O(n) solution can easily
be deduced. Let me know about whether or not this was the required Logic/Answer. Then I will add algo for
the same.

Smaple Input 1

[1,2,1,3,2,3,2,3]

(1,2,3)

Output For 1st Test Case : Debugged output

Indexex are as follows
0 1 3
0 1 5
0 1 7
0 4 5
0 4 7
0 6 7
2 4 5
2 4 7
2 6 7
Total count is using Naive with time complexity O(n3) is                = 9
Total count is using Optimised approach is with complexity O(n) is      = 9