Top K Frequent Elements

Learning goal: Translate the problem into a frequency-ranking task rather than an array-ordering task.

Core idea The input may contain many repeated values, but the answer concerns distinct values and their counts. First build a frequency map such as value -> count; then select the k values with the largest counts. The order of the returned values does not matter, so we do not need to sort the final answer.

Algorithm plan

• Scan nums once and increment freq[x] for every value x.
• Choose the k entries with the greatest frequency.
• Use either a size-k min-heap or frequency buckets.

Micro-example For [4,1,-1,2,-1,2,3], the map is {4:1, 1:1, -1:2, 2:2, 3:1}. With k = 2, the answer is [-1, 2].

Pitfalls

• Return distinct values, not repeated copies from the original array.
• Do not assume the result must be sorted numerically.
• A tie in frequency is acceptable when the problem permits multiple valid answers; here the selected set is determined by the input guarantee.

Recap

• Frequency is the ranking key.
• Hashing performs the counting pass.
• Selection, not full ordering, is the optimization opportunity.

Learning goal: Understand why top-k selection can be cheaper than sorting every frequency.

Core idea After counting, suppose there are m distinct values. A full sort orders all m frequency entries, even though only the largest k are needed. A size-k min-heap keeps the current winners: the smallest winner sits at the root, so a new candidate can replace it when its frequency is larger. Alternatively, bucket sort places each value into a bucket indexed by its frequency.

Algorithm plan

• Build freq in O(n) time.
• For a heap solution, push each (frequency, value) pair and remove the smallest whenever the heap exceeds k.
• For the target linear solution, create buckets from frequency 0 through n.
• Scan buckets from frequency n downward until k values are collected.

Micro-example Counts [2,2,1,1,1] need only the two entries with count 2; sorting all five entries is unnecessary.

Pitfalls

• A min-heap is not the same as a max-heap: its root is the weakest current winner.
• Bucket indices are frequencies, not array values.
• The maximum possible frequency is nums.length, so buckets need indices 0..n.

Recap

• Full sorting costs more than necessary.
• Heap selection costs O(n log k).
• Bucket selection reaches O(n).

Learning goal: Build the linear-time bucket solution from its frequency bounds.

Core idea No value can appear more than n times, where n = nums.length. Therefore, an array of n + 1 buckets is enough: bucket f stores every value appearing exactly f times. Once the frequency map is complete, scan from bucket n down to bucket 1; descending order guarantees that values are encountered from most frequent to least frequent.

Algorithm plan

1. Initialize an empty hash map freq.
2. For each x in nums, increment freq[x].
3. Create buckets, where buckets[f] is a list of values with frequency f.
4. Insert each (value, count) pair into buckets[count].
5. Traverse frequencies from n down to 1.
6. Append values until result.length == k, then return.

freq = Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)]
for value, count in freq.items():
    buckets[count].append(value)
for count in range(len(nums), 0, -1):
    for value in buckets[count]:
        result.append(value)
        if len(result) == k:
            return result

Micro-example For the running input, bucket 2 contains [-1, 2]; buckets 1 contains [4, 1, 3]. Scanning downward immediately produces both answers.

Pitfalls

• Stop exactly after collecting k values.
• Iterate over freq.items(), not every position in nums.
• Allocate n + 1 buckets so frequency n is valid.

Recap

• Frequency itself provides a natural ordering index.
• Counting, bucketing, and scanning are all linear.
• Total complexity is O(n) time and O(n) space.

Learning goal: Trace the heap alternative and see how it avoids sorting all candidates.

Core idea The bucket method gives the target O(n) bound, but a size-k min-heap is often convenient and is asymptotically better than full sorting when k is small. Each heap entry represents one distinct value, ordered by its frequency. When the heap grows beyond k, remove its minimum; that value cannot belong to the final top k among the candidates seen so far.

Algorithm plan

• Count the running example: -1 and 2 have frequency 2; 4, 1, and 3 have frequency 1.
• Push each frequency into a heap of capacity k = 2.
• When a third candidate arrives, remove the minimum frequency.
• At the end, the heap contains the selected values.

for each (value, count) in freq:
    push (count, value)
    if heap.size > k:
        pop minimum
return values in heap

Micro-example After pushing -1:2 and 2:2, the heap holds both winners. Pushing 4:1 temporarily creates three candidates; removing 4:1 restores the size limit.

Pitfalls

• The heap must store the value along with its count; counts alone cannot identify the answer.
• Remove only when the heap size exceeds k.
• Heap output order is not guaranteed to be sorted.

Recap

• The root is the weakest retained candidate.
• The heap stores only k winners.
• Heap time is O(n log k); buckets are needed for the target O(n) bound.

Learning goal: Recognize implementation mistakes that change either correctness or asymptotic performance.

Core idea The difficult part is usually not counting; it is selecting without doing unnecessary work. Sorting all frequency entries is correct, but it spends O(n log n) time to arrange values that will never be returned. The intended optimization is to use frequency buckets for O(n) time, or a size-k heap for O(n log k) time.

Edge-case checklist

• If one value fills the entire array, its frequency is n, so the highest bucket index must be valid.
• If k equals the number of distinct values, every distinct value must be returned; bucket scanning naturally handles this.
• Multiple values may share a frequency. Store all of them in the same bucket.
• The result can be emitted in any order unless a particular implementation chooses an order.

Micro-example For [5,5,5,2,2,8] and k = 1, counts are 5:3, 2:2, 8:1. Scanning bucket 3 returns 5 immediately.

Pitfalls

• Explicit mistake: Sorting all counts costs O(n log n) when only the top k are needed.
• Forgetting to keep values associated with their frequencies.
• Returning duplicate values instead of one entry per distinct key.
• Continuing the scan after k results have been collected.

Recap

• Buckets handle ties by storing lists.
• Heap capacity must remain k.
• Choose buckets for the required linear target.

Learning goal: Justify the target complexity and choose the right implementation for the constraints.

Core idea The bucket solution performs a constant amount of work per input item, per distinct value, and per bucket position scanned. Since the number of buckets is n + 1, all phases remain linear in n. The frequency map and buckets together use O(n) auxiliary space in the worst case.

Complexity summary

The heap alternative is valuable when k is much smaller than the number of distinct values: it uses O(n log k) time and O(n) space including the map. The bucket approach is the canonical target here because it remains linear even when k approaches n.

Micro-example For n = 7, bucket indices 0..7 are sufficient. We inspect them from 7 down until two values have been collected.

Pitfalls

• Do not claim the heap solution is O(n) unless k is treated as a fixed constant.
• Include the map and buckets when reporting space.
• Big-O ignores the arbitrary order of the returned result.

Recap

• Target: O(n) time and O(n) space with buckets.
• Heap: O(n log k) time, often practical for small k.
• Count first, then select only what the answer requires.