6. Top K Frequent Elements · DSA Practice

Return the k most frequent values in nums, in any order. The answer is guaranteed to be unique.

Example 1

Input: nums = [4,4,4,6,6,9], k = 2

Output: [4,6]

Example 2

Input: nums = [7], k = 1

Output: [7]

Constraints

1 ≤ k ≤ number of distinct values

Hint 1

Count frequencies first.

Hint 2

A frequency can be at most n, so you can bucket values by frequency instead of sorting.

Hash TableBucket SortHeap

Approach 1: Sort by count

Count with a hash map, sort the distinct values by count, take k.

⏱ Time O(n log n)💾 Space O(n)

Approach 2: Min-heap of size k

Push (count, value) into a heap and pop when it grows beyond k.

⏱ Time O(n log k)💾 Space O(n)

Approach 3: Bucket sort ✅

Put each value in bucket[count] and read buckets from high to low.

⏱ Time O(n)💾 Space O(n)

Reference solution for Bucket sort (time O(n), space O(n)). Each solution passes every test in all four languages.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = Counter(nums)
        buckets = [[] for _ in range(len(nums) + 1)]   # buckets[f] = values seen f times
        for x, f in count.items():
            buckets[f].append(x)
        res = []
        for f in range(len(buckets) - 1, 0, -1):       # highest frequency first
            for x in buckets[f]:
                res.append(x)
                if len(res) == k:
                    return res
        return res

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> count = new HashMap<>();
        for (int x : nums) count.merge(x, 1, Integer::sum);
        List<List<Integer>> buckets = new ArrayList<>();          // buckets.get(f) = values seen f times
        for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
        for (var e : count.entrySet()) buckets.get(e.getValue()).add(e.getKey());
        int[] res = new int[k];
        int i = 0;
        for (int f = nums.length; f > 0 && i < k; f--)
            for (int x : buckets.get(f))
                if (i < k) res[i++] = x;
        return res;
    }
}

class Solution {
public:
    vector<int> topKFrequent(vector<int>& nums, int k) {
        unordered_map<int, int> count;
        for (int x : nums) count[x]++;
        vector<vector<int>> buckets(nums.size() + 1);   // buckets[f] = values seen f times
        for (auto& kv : count) buckets[kv.second].push_back(kv.first);
        vector<int> res;
        for (int f = nums.size(); f > 0 && (int)res.size() < k; f--)
            for (int x : buckets[f])
                if ((int)res.size() < k) res.push_back(x);
        return res;
    }
};

function topKFrequent(nums, k) {
  const count = new Map();
  for (const x of nums) count.set(x, (count.get(x) || 0) + 1);
  const buckets = Array.from({ length: nums.length + 1 }, () => []); // buckets[f] = values seen f times
  for (const [x, f] of count) buckets[f].push(x);
  const res = [];
  for (let f = nums.length; f > 0 && res.length < k; f--)
    for (const x of buckets[f]) if (res.length < k) res.push(x);
  return res;
}

Try solving it yourself first. Interviewers care more about how you explain the approach than about the finished code.

This problem is explained in the lesson Arrays, Hashing & Prefix Sums.