Top K Frequent Elements

Approach Summary

Count frequencies with a map. Use a min-heap of size k or bucket sort by frequency for O(n) solution.

Full Solution & Approach

Count frequencies with a hash map first — that is unavoidable. Then get the top k without a full sort. Bucket sort is the elegant O(n) answer: the maximum frequency is n, so create buckets as an array of lists where bucket[i] holds every number that appears exactly i times. Fill the buckets from the frequency map, then walk from the highest bucket index downward, collecting numbers until you have k. This is O(n) because counting is one pass and the downward walk collects at most k extra elements. The alternative is a size-k min-heap keyed by frequency, which gives O(n log k) — better when k is small or the data streams in. Bucket sort wins on time; the heap wins on memory when k is tiny. Either is preferable to sorting all distinct values.

Counting is O(n); filling and walking the n + 1 buckets is O(n) — O(n) total time. The map plus buckets store up to n values — O(n) space.

Solution Code

Solution

from collections import Counter

def top_k_frequent(nums: list[int], k: int) -> list[int]:
    return [n for n, _ in Counter(nums).most_common(k)]

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

public int[] topKFrequent(int[] nums, int k) {
    Map<Integer, Integer> freq = new HashMap<>();
    for (int n : nums) freq.merge(n, 1, Integer::sum);
    // Min-heap of size k ordered by frequency
    PriorityQueue<Integer> heap = new PriorityQueue<>(
        (a, b) -> freq.get(a) - freq.get(b));
    for (int key : freq.keySet()) {
        heap.offer(key);
        if (heap.size() > k) heap.poll();
    }
    int[] res = new int[k];
    for (int i = 0; i < k; i++) res[i] = heap.poll();
    return res;
}

vector<int> topKFrequent(const vector<int>& nums, int k) {
    unordered_map<int,int> freq;
    for (int n : nums) freq[n]++;
    // Min-heap of size k ordered by frequency
    priority_queue<pair<int,int>, vector<pair<int,int>>, greater<>> heap;
    for (auto& [num, count] : freq) {
        heap.push({count, num});
        if ((int)heap.size() > k) heap.pop();
    }
    vector<int> res;
    while (!heap.empty()) { res.push_back(heap.top().second); heap.pop(); }
    return res;
}

Edge Cases to Watch

All elements distinct — every bucket holds one entry; the top k is any k of them
k equals the number of distinct elements — return all of them
One distinct value repeated — bucket[count] holds that single value
The problem guarantees 1 ≤ k ≤ number of distinct elements

How to Recognize This Pattern

Find k most frequent elements

Complexity Analysis

Time Complexity

O(n log k)

Space Complexity

O(n)