We use cookies to ensure you have the best browsing experience on our website. Please read our cookie policy for more information about how we use cookies.
- Count Triplets
- Discussions
Count Triplets
Count Triplets
Sort by
recency
|
794 Discussions
|
Please Login in order to post a comment
My C++ solution from 6 years ago. Gets 100%:
long getMax(long a, long b) { if (a>b) return a; return b; }
// Complete the countTriplets function below. long countTriplets(vector arr, long r) { typedef std::unordered_map HashNumberCounts;
}
javascript
this version is more intuitive but fails on case 3. the version down below improved performance based on it.
Here is mine in Go.
My first solution was to enumerate all the indexes for all the items in the array in a map of item : list of indexes, and the in same loop start checking for middle in the map, for for each index of the middle check for first such that first < middle. This is a solution but has a complexity of n^2 in the worst case scenario, so a four of test cases failed. Then I saw I could add add an optimization for r=1, when we add all the combinations for item nC3. After adding this optimization, still two testcases failed.
This final solution works in O(n), and whjat we do is, instad of making triplets with last element as the focus, we make triplets with middle as the focus. We first calculate the frequncies of all disctinct numbers. Then we iterate but taking the current item as the middle. Then we try to form a triplet from the frequency_map of items we have not yet seen for the last item of the triplet, and from the frequency map of items we have already seen for the first item of the triplet. Add new found triplets (frequency of first * 1 * frequency of last) , and mark current item as seen by adding it to the seen frequency map. By using two maps for find last and first, we get better time complexity as we don't have to do the i < j < k check in the same map.