Find the N-th most frequent number in the array

Question

Find the nth most frequent number in array.
(There is no limit on the range of the numbers)

I think we can

(i) store the occurence of every element using maps in C++

(ii) build a Max-heap in linear time of the occurences(or frequence) of element and then extract upto the N-th element, Each extraction takes log(n) time to heapify.

(iii) we will get the frequency of the N-th most frequent number

(iv) then we can linear search through the hash to find the element having this frequency.

Time - O(NlogN) Space - O(N)

Is there any better method ?

Answer 1

It can be done in linear time and space. Let T be the total number of elements in the input array from which we have to find the Nth most frequent number:

1. Count and store the frequency of every number in T in a map. Let M be the total number of distinct elements in the array. So, the size of the map is M. -- O(T)
2. Find Nth largest frequency in map using Selection algorithm. -- O(M)

Total time = O(T) + O(M) = O(T)

Answer 2

Your method is basically right. You would avoid final hash search if you mark each vertex of the constructed heap with the number it represents. Moreover, it is possible to constantly keep watch on the fifth element of the heap as you are building it, because at some point you can get to a situation where the outcome cannot change anymore and the rest of the computation can be dropped. But this would probably not make the algorithm faster in the general case, and maybe not even in special cases. So you answered your own question correctly.

Answer 3

It depends on whether you want most effective, or the most easy-to-write method.

1) if you know that all numbers will be from 0 to 1000, you just make an array of 1000 zeros (occurences), loop through your array and increment the right occurence position. Then you sort these occurences and select the Nth value.

2) You have a "bag" of unique items, you loop through your numbers, check if that number is in a bag, if not, you add it, if it is here, you just increment the number of occurences. Then you pick an Nth smallest number from it.

Bag can be linear array, BST or Dictionary (hash table).

The question is "N-th most frequent", so I think you cannot avoid sorting (or clever data structure), so best complexity can not be better than O(n*log(n)).

Answer 4

Just written a method in Java8: This is not an efficient solution.

• Create a frequency map for each element
• Sort the map content based on values in reverse order.

• Skip the (N-1)th element then find the first element

  private static Integer findMostNthFrequentElement(int[] inputs, int frequency) {
      return Arrays.stream(inputs).boxed()
          .collect(Collectors.groupingBy(Function.identity(), Collectors.counting()))
          .entrySet().stream().sorted(Map.Entry.comparingByValue(Comparator.reverseOrder()))
          .skip(frequency - 1).findFirst().get().getKey();
  }