Top K Frequent Elements

MediumArray Hash Table Heap Sorting

An on-call engineer wants a quick summary of last night's failures. Each failure was logged as an integer error code in nums; codes from the operating system are negative and codes from the application are positive. Given a number k, return the k codes that were logged most often, in any order.

The tests are built so that the answer is unique: the k-th most frequent code always occurs strictly more often than any code that is left out.

Example 1

Input: nums = [500,-2,500,404,-2,500], k = 2
Output: [500,-2]

Explanation: 500 was logged three times and -2 twice; 404 only once.

Example 2

Input: nums = [-1,-1,8,8,8,5,5,5,5], k = 3
Output: [5,8,-1]

Explanation: There are exactly three distinct codes, so all of them are returned.

Example 3

Input: nums = [4,4,6,9,6,4,9,9,4], k = 1
Output: [4]

Explanation: The counts are 4 → 4, 9 → 3 and 6 → 2.

Constraints

nums holds between 1 and 10^5 error codes.
Each code is an integer from -10^4 to 10^4.
k is at least 1 and at most the number of distinct codes in nums.
The k most frequent codes are uniquely determined.

Follow-up: A busy night can produce millions of log entries. Can you skip sorting altogether and answer in time linear in the length of the log?

💡 Hint 1

First count how many times each value occurs with a hash map.

💡 Hint 2

Sorting the distinct values by count costs O(m log m). A min-heap of size k brings that to O(m log k).

💡 Hint 3

A frequency is always between 1 and n. Put each value into a bucket indexed by its count, then read buckets from the highest count down until you have k values.

Try it yourself first ✎

Solutions stick better after a real attempt. Peek when you're ready.

Approach

Count occurrences with a hash map. Then use bucket sort by frequency: create n + 1 buckets where buckets[c] holds every value that occurs exactly c times. Walk the buckets from n down to 1, collecting values until you have k of them. Because frequencies are bounded by n, this avoids sorting entirely.

Time O(n)Space O(n)

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 }, () => []);
  for (const [value, c] of count) buckets[c].push(value);
  const result = [];
  for (let c = nums.length; c > 0 && result.length < k; c--) {
    for (const value of buckets[c]) {
      if (result.length < k) result.push(value);
    }
  }
  return result;
}

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<>();
        for (int i = 0; i <= nums.length; i++) buckets.add(new ArrayList<>());
        for (Map.Entry<Integer, Integer> e : count.entrySet()) buckets.get(e.getValue()).add(e.getKey());
        int[] result = new int[k];
        int filled = 0;
        for (int c = nums.length; c > 0 && filled < k; c--) {
            for (int value : buckets.get(c)) {
                if (filled < k) result[filled++] = value;
            }
        }
        return result;
    }
}

/**
 * @param {number[]} nums
 * @param {number} k
 * @return {number[]}
 */
function topKFrequent(nums, k) {

}

Ctrl/⌘ + ' run · Ctrl/⌘ + Enter submit