Triple sum Solution

This is one of the medium difficulty problems in the search section of Hackerrank’s interview preparation kit problem set. Link here.

The problem states that given three arrays a, b and c you need to count all unique ( p, q, r ) such that.p belongs to a , q belongs to b ,r belongs to c ,p ≤ q and q ≥ r

Solution

The solution again is very simple. Since we need r and p to be less than or equal to q and q is in b we just need to count all elements in a and c less than or equal to each element in b. For instance given:

a ={1, 2, 3}, b={2, 3}, c={3}. With b_0 we can form no triples because no elements from c are less than or equal. But with b_1 we can form 3*1 triples because three elements from a match this condition and one from c. This is easy to see if you tabulate the data. Try it!

Now to count the number of items less than or equal at any index we just sort and the index gives us this information. And since the triples should be unique, we should also remove all duplicates.

Code

Link to solution on github

long triplets(vector<int> a, vector<int> b, vector<int> c) {
    
    sort(a.begin(), a.end());
    sort(b.begin(), b.end());
    sort(c.begin(), c.end());
 
    a.erase(unique(a.begin(),a.end()),a.end());
    b.erase(unique(b.begin(),b.end()),b.end());
    c.erase(unique(c.begin(),c.end()),c.end());
    
    int i = 0, j = 0, k = 0;
    long sol=0;
    
    while(i < b.size()){
        while(a[j]<=b[i] && j<a.size())
            j++;
        while(c[k]<=b[i] && k<c.size())
            k++;
        sol+= (long)j*k;
        i++;
    }
    return sol;
}