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

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Example 2:

Input: nums = [1], k = 1

Output: [1]

Example 3:

Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2

Output: [1,2]

The solution i could think of while solving this problem was using hashmaps, sorting.

To find the k most frequent elements, we first need to know how often each number appears.
Once we count the frequencies, we can sort the unique numbers based on how many times they occur.
After sorting, the numbers with the highest frequencies will naturally appear at the end of the list.
By taking the last k entries, we get the k most frequent elements.

This approach is easy to reason about:
count the frequencies → sort by frequency → take the top k.

But as i looked at more optimized and better solutions, we have two more approaches.
Min heap and Bucket sort, the min heap solution is something which was easily understood as it was just the sorting method enhanced by min heap structure, but the bucket list logic is a copletely different approach. So even though the best result of O(n) is achieved by bucket list, i stick with min heap for personal satisfaction as this approach was more or less what i thought of myself.

After counting how often each number appears, we want to efficiently keep track of only the k most frequent elements.
A min-heap is perfect for this because it always keeps the smallest element at the top.
By pushing (frequency, value) pairs into the heap and removing the smallest whenever the heap grows beyond size k, we ensure that the heap always contains the top k most frequent elements.
In the end, the heap holds exactly the k values with the highest frequencies.

Implementation

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        for num in nums:
            count[num] = 1 + count.get(num, 0)

        heap = []
        for num in count.keys():
            heapq.heappush(heap, (count[num], num))
            if len(heap) > k:
                heapq.heappop(heap)

        res = []
        for i in range(k):
            res.append(heapq.heappop(heap)[1])
        return res