CS1: Given an array of integers return top-n most frequent integers in the array.

Language: Java

Data structures:
Map<K, V>
Map.Entry<K, V>
MinMaxPriorityQueue<E> // Used as a min-heap.

Algo idea O(n):
Input: Integer[] inputValue;

1. From the given array of values create a map of (value, freq)

    Map<Integer, Integer> map = new HashMap<Integer, Integer>();
    for (int i = 0; i < inputValue.length; i++) {
      Integer value = array[i];
      Integer freq = map.get(value); // get() returns null if a key does not exist.
      map.put(value, freq == null ? 1 : freq + 1);
    }

2. Populate the priorityQueue (ordered based on entry.getValue() i.e., freq) with at most n elements

    MaxMinPriorityQueue<Map.Entry<Integer, Interger>> priorityQueue =
        MaxMinPriorityQueue.create(); // You may need to wrap Map.Entry into a Comparable.
   
    for (Map.Entry<Integer, Interger> entry : map.entrySet()) {
      if (priorityQueue.size() < n) {
        priorityQueue.add(entry);
      } else {
        Map.Entry<Integer, Interger> minEntry = priorityQueue.peekFirst();
        if (entry.getValue() > minEntry.getValue() ) {  // compare frequencies.
          // Replace min element with current element.
          priorityQueue.removeFirst();
          priorityQueue.add(entry);
      }
    }

3. Output the result:

    for (Map.Entry<Integer, Interger> entry : priorityQueue.iterator()) { output(entry.getKey()); }