Top K Frequent Elements

Question

Given a non-empty array of integers, return the k most frequent elements

Examples

Array: [1, 1, 1, 2, 2, 3]; K = 2;

Clues

K th element => find a way to sort elements => priority queue / heap

count frequencies => hash map

Assumptions

K is always valid, 1 ≤ K ≤ number of unique elements

Brute Force Solution

Use hashmap to record how many times each element appears => O(n)

Go through hashmap to find the element with highest frequencies.

=> O(m * K), where m is the size of hashmap and K is the k th number of element

Total: O(m * K)

BUD Optimization (bottleneck, unnecessary, duplicate work)

Obviously, in the brute force solution, the bottleneck is the process of retrieving Kth element from the hashmap. If entries in the hashmap can be sorted by their frequencies, it will reduce the duplicate work of going through the hashmap m times.

This leads to the method of using Priority Queue or heap:

class freqCount {…}

class freqComparator implements Comparator<freqCount>{…}

PriorityQueue<freqCount> queue = new PriorityQueue<freqCount>(size, new frequencyComparator());

Walkthrough

1. Create freqCount class and freqComparator class for convenience
2. Iterate through the array and map the frequency to the hashMap
3. Iterate through the hashMap and add them to the PriorityQueue
4. Poll top K items from the PriorityQueue
5. Total big O is nlog(n), where n is length of the hashMap. PriorityQueue insertion is O(log(n))