Top K Frequent Elements

Intuition

The order of the array does not matter; only how often each value appears. So first tally every value in a hash map with a single pass. Now the task reduces to selecting the k entries with the largest counts. A size-k min-heap keyed by frequency keeps only the strongest candidates, evicting the weakest whenever it overflows, which gives O(n log k). When counts are bounded by n, bucket sort is even better: place each value in a bucket indexed by its frequency and scan buckets from high to low to reach O(n).

Algorithm walkthrough

1. 1Traverse the array once, incrementing each value's count in a hash map.
2. 2Create buckets where bucket[f] holds every value whose frequency equals f (frequencies range from 1 to n).
3. 3Alternatively, push (frequency, value) into a min-heap and pop whenever its size exceeds k.
4. 4To read the answer with buckets, walk frequencies from n down to 1, collecting values until k are gathered.
5. 5Return the collected values.

Implementation

import heapq
from collections import Counter


class Solution:
    def topKFrequent(self, nums: list[int], k: int) -> list[int]:
        counts = Counter(nums)
        heap: list[tuple[int, int]] = []
        for value, freq in counts.items():
            heapq.heappush(heap, (freq, value))
            if len(heap) > k:
                heapq.heappop(heap)
        return [value for _, value in heap]