Top K Frequent Elements

How it works

Each number in the array appears a certain number of times, and the maximum possible frequency is the length of the array. We can use this idea by creating a list where the index represents a frequency, and at each index we store all numbers that appear exactly that many times.

For example:

• All numbers that appear 1 time go into group freq[1].
• All numbers that appear 2 times go into group freq[2].
• And so on.

After we build these groups, we look from the highest possible frequency down to the lowest and collect numbers from these groups until we have k of them. This way, we directly jump to the most frequent numbers without sorting all the elements by frequency.

Steps

1. Build a frequency map that counts how many times each number appears.
2. Create a list of groups freq, where freq[i] will store all numbers that appear exactly i times.
3. For each number and its frequency in the map, add the number to freq[frequency].
4. Initialize an empty result list.
5. Loop from the largest possible frequency down to 1:
   • For each number in freq[i], add it to the result list.
   • Once the result contains k numbers, return it.

Complexity

• Time complexity: O(n)
• Space complexity: O(n)

Things to watch for

Using a Max-Heap Instead of Min-Heap

When keeping track of the top k elements, a min-heap of size k is needed so you can efficiently remove the smallest frequency when the heap exceeds size k. Using a max-heap requires storing all elements and then extracting k times, which is less efficient. The min-heap approach maintains only the k largest frequencies at any time.

Forgetting to Handle Ties in Frequency

When multiple numbers have the same frequency, the order in which they appear in the result may vary. Most problem statements accept any valid ordering, but some solutions incorrectly assume a specific order or break when frequencies are equal. Ensure your comparison function handles equal frequencies gracefully.

Off-By-One in Bucket Sort Index

In bucket sort, frequencies range from 1 to n (the array length), so you need n + 1 buckets indexed 0 to n. A common mistake is creating only n buckets, causing an index out of bounds error when an element appears n times. Always allocate len(nums) + 1 buckets to accommodate all possible frequencies.

from typing import List

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = {}
        freq = [[] for i in range(len(nums) + 1)]

        for num in nums:
            count[num] = 1 + count.get(num, 0)
        for num, cnt in count.items():
            freq[cnt].append(num)

        res = []
        for i in range(len(freq) - 1, 0, -1):
            for num in freq[i]:
                res.append(num)
                if len(res) == k:
                    return res

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        vector<vector<int>> freq(nums.size() + 1);

        for (int n : nums) {
            count[n] = 1 + count[n];
        }
        for (const auto& entry : count) {
            freq[entry.second].push_back(entry.first);
        }

        vector<int> res;
        for (int i = freq.size() - 1; i > 0; --i) {
            for (int n : freq[i]) {
                res.push_back(n);
                if (res.size() == k) {
                    return res;
                }
            }
        }
        return res;
    }
};