Leetcode: Top K Frequent Elements (Kotlin)
Kotlin

Leetcode: Top K Frequent Elements (Kotlin)

December 5, 2024

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:

  1. Create a map that keeps track of the count of each number.

  2. 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.

  3. 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.

  4. Create an array the size of k.

  5. Add the first k values to the array. Problem mentions order does not matter

  6. 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:

class Solution {
    fun topKFrequent(nums: IntArray, k: Int): IntArray {
        
        val map = mutableMapOf<Int,Int>()
        
        // set the frequency of each number in the map
        nums.forEach{ num ->
            map[num] = map.getOrDefault(num, 0) + 1
        }
        
        // create a custom comparator to compare by the count of each number
        // we will keep it as a min heap
        val pq = PriorityQueue<Int>( compareBy{ map[it] } )
        
        // Add the keys( each number ) to the heap based on the count in the map. 
        // If the priority queue's size is bigger than k, we want to remove an element,
        // because there are elements with a higher frequency
        for(key in map.keys){
            pq.offer(key)
            if(pq.size > k) pq.poll()
        }
        
        // create an array that is the size of k
        val topK = IntArray(k)
        
        // add the first k elements in the priority queue to the array
        // (problem statement mentions order does not matter)
        for(i in 0 until k) topK[i] = pq.poll()
        
        return topK
        
    }
}