347. Top K Frequent Elements

Problem Link

Heap

This is a general problem designed to be solved efficiently using heap data structure. For now, we'll solve it using hashmaps.

The general idea to solve this is by generating a hashmap where the value is list of numbers and key is the frequency of those number in nums. Now, you can use this hashmap to generate list of nums sorted in order of their frequency in nums. But for this problem, we only want first \(k\) elements from this list.

Pseudocode

• Generate hashmap where key is \(num\) and value is frequency of that \(num\) in nums.
• Using above hashmap, generate another hashmap where key is a number and value is the list of numbers having \(key\) frequency in nums.
• Generate result having numbers sorted in order of highest frequency. Since the highest frequency could be len(nums) while smallest -> \(0\).
  • Iterate from the highest frequency to the smallest while adding numbers of frequencies found in our hashmap.

Runtime Complexity

Time: \(O(n)\), from iterating nums.

Space: \(O(n)\) <- from hashmaps.

PythonGo

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        freq = Counter(nums)
        buckets = defaultdict(list)
        for num, count in freq.items():
            buckets[count].append(num)

        result = []
        for count in range(len(nums), 0, -1):
            if count in buckets:
                result.extend(buckets[count])

        return result[:k]

func topKFrequent(nums []int, k int) []int {
    freq := make(map[int]int)
    for _, num := range nums {
        freq[num]++
    }
    buckets := make(map[int][]int)
    for num, count := range freq {
        buckets[count] = append(buckets[count], num)
    }

    var result []int
    for i := len(nums); i >= 0; i-- {
        vals, ok := buckets[i]
        if ok {
            result = append(result, vals...)
        }
    }
    return result[:k]
}

---