Sweaty Imposter

Top K Frequent Elements

MediumTop K ElementsBlind 75MidOpen on LeetCodeUpdated

You're given an integer array nums and an integer k. Return the k distinct values that occur most often in nums, in any order. The answer is guaranteed to be unique, so there is never a tie for the last spot. Aim for better than O(n log n) time, which rules out simply sorting every value by its count.

Examples

nums = [1,1,1,2,2,3], k = 2 returns [1,2]

1 appears three times, 2 twice and 3 once. The two most frequent values are 1 and 2.

nums = [1], k = 1 returns [1]

There is only one distinct value, so it is the whole answer.

Constraints

  • 1 <= nums.length <= 10^5
  • 1 <= k <= number of unique values

Hints

Hint 1

You don't need to fully sort by frequency, what's the smallest structure that always holds the right elements?

Hint 2
A pointer toward the approach
Hint 3
The full approach, step by step

Drill This: Your Approach First

Approach

Count how often each value occurs, then group values by count: bucket f holds every value that appears exactly f times. No count can exceed n, so n + 1 buckets cover every case. Walk the buckets from the highest count down, collecting values until you have k. Grouping by count replaces a full sort, so the whole thing is O(n) time and O(n) space.

Time

O(n)

Space

O(n)

Pitfall

Stopping only at bucket boundaries: one bucket can hold more values than you still need, so check for k after each value you collect, not after each bucket. Also return the values themselves, not their counts.

Solutions

class Solution {
    public int[] topKFrequent(int[] nums, int k) {
        Map<Integer, Integer> freq = new HashMap<>();
        for (int num : nums) freq.merge(num, 1, Integer::sum);
        List<Integer>[] buckets = new List[nums.length + 1];
        for (var e : freq.entrySet()) {
            int f = e.getValue();
            if (buckets[f] == null) buckets[f] = new ArrayList<>();
            buckets[f].add(e.getKey());
        }
        int[] result = new int[k];
        int idx = 0;
        for (int f = buckets.length - 1; f >= 0 && idx < k; f--) {
            if (buckets[f] == null) continue;
            for (int v : buckets[f]) {
                result[idx++] = v;
                if (idx == k) break;
            }
        }
        return result;
    }
}
Drill This