Find the most frequent triplet in an array

Question

We have an array of N numbers. All the numbers are between 1-k.

The problem is how to find the best way of finding the most frequent triplet.

My approach to the problem is:

Say if the input is like { 1, 2, 3, 4, 1, 2, 3, 4}

First search for the count of triplet ( 1, 2, 3) start from the second element in the array till the end of the array. Now we will have the count as 1. Now start with { 2, 3, 4) and search the array.

for each triplet we scan the array and find the count. Like this we run the array for n-1 times.

This way my algorithm runs in the order of n*n time complexity. Is there any better way for

this problem.?

Answer 1

You can do it in O(n * log n) worst-case space and time complexity: Just insert all triples into a balanced binary search tree and find the maximum afterwards.

Alternatively, you can use a hash table to get O(n) expected time (which is typically faster than the search tree approach in reality, if you choose a good hash function).

Answer 2

Are there any memory boundaries i.e. does it run on a device with memory limitations?

If not, maybe this could be good solution: iterate over array and for each tripple build and representation object (or struct if implemented in c#) which goes into map as a key and the tripple counter as a value.

If you implement hash and equals functions appropriately, you will be able to find the "most popular" tripple where numbers order matters or not e.g. 1,2,3 != 2,1,3 or 1,2,3 == 2,1,3

After iterating entire array you would have to find the largest value and its key would be your "most popular" tripple. With that approach you could find X most popular tripples too. Also you would scan array only once and aggregate all the trippels (no extra scanning for each tripple).