Top k frequent elements

Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.

When dealing with top k, we would like to think about a priority queue.

But first we need to figure out how to keep track of all the integers...

Since we have to iterate through the entire array, we can use something to keep track of the integer frequencies. Therefore we will use a frequency map. Basically a frequency map is a hashmap. Each key represents an integer from the array, while each value represents the frequency of that integer in the array.

Map<Integer, Integer> freq = new HashMap<>();

for(int num: nums){
   freq.put(num, freq.getOrDefault(num, 0) + 1);
}

Now, we must determine which integers are the top 5. We can easily achieve this by using a priority queue. A priority queue is a data structure in which each element additionally has a priority associated with it. In a priority queue, an element with high priority is served before an element with low priority.

Queue<Integer> minHeap = new PriorityQueue<>((n1,n2) -> freq.get(n1) - freq.get(n2));
for(int num : freq.keySet()){
  heap.add(num);
  if(heap.size() > k) heap.poll();
}

The priority queue constructor accepts a lambda function to override a comparator operation. In this case, we do so so that the frequency of the integers are compared before adding to the heap.

Comparator<Integer> result = new Comparator<Integer>() {
        @Override
        public int compare(Integer n1, Integer n2){
            return n1.compareTo(n2);
        }
    };

PriorityQueue<Integer> heap = new PriorityQueue<Integer>(result);

There are several ways to define how you want the priority queue to act. In this case we want a min heap.

• Result is negative -> n1 is smaller
• Result is 0 -> n1 and n2 are same
• Result is positive -> n1 is greater

Finally we now just poll the min heap to an array

        int[] top = new int[k];
        for(int i = k - 1; i>=0;--i){
            top[i]=heap.poll();
        }
        return top;