Leetcode: Top K Frequent Elements (Kotlin)

Top K Frequent Elements is a medium-tagged question on Leetcode. Top K Frequent Elements - LeetCode

It is also one of the recommended questions from the Blind 75 Leetcode List. Blind 75 LeetCode Questions - LeetCode Discuss

The problem statement states:

Examples:

Constraints:

Approaches:

The problem mentions when we need to know how frequently a number exists in the array. We can use a HashMap to accomplish this.

Example 1 map would look like the following:

The most challenging part of this problem is coming up with a way to find the k top frequent numbers. We can use a min-heap priority queue to store the data in ascending order of the count. These are the steps you can take to achieve this:

Create a map that keeps track of the count of each number.
Create a PriorityQueue of type Int. We can make this a min-heap by using a custom comparator and using the count as the value to compare to. We can use the actual number as the value in the PriorityQueue.
Iterate over the keys in the map and add the numbers in the priority queue. If the priority queue is bigger than the size of k, we can remove an element, which has a lesser count.
Create an array the size of k.
Add the first k values to the array. Problem mentions order does not matter
Return the array

We could use a max heap using the Kotlin comparator helper function compareByDescending. We would just add all the values to the priority queue without removing any since the ones with the highest count would be at the front of the priority queue. Of course, we would be using more memory with the max heap approach kotlin.comparisons - Kotlin Programming Language

Using Example 1 we can visualize the max vs min heap Priority Queues compared by the count:

Solution:

{% gist https://gist.github.com/cmcoffeedev/6365927a226b19bb5b6eb686e430b015.js %}