Top K Frequent Elements

Share

Given an integer array nums and an integer k, return the k most frequent elements. The answer may be returned in any order.

Example 1
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2
Input: nums = [1], k = 1
Output: [1]
Constraints:

Contents

Approach 1: HashMap + Min-Heap

Count frequencies using a HashMap, then use a min-heap of size k keyed by frequency. The heap always retains the k most frequent elements.

Java
public int[] topKFrequent(int[] nums, int k) {
    // Step 1: count frequencies
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }

    // Step 2: min-heap ordered by frequency (lowest freq at top)
    PriorityQueue<Integer> minHeap = new PriorityQueue<>(
        Comparator.comparingInt(freq::get)
    );

    for (int num : freq.keySet()) {
        minHeap.offer(num);
        if (minHeap.size() > k) {
            minHeap.poll(); // remove least frequent
        }
    }

    // Step 3: collect results
    int[] result = new int[k];
    for (int i = 0; i < k; i++) {
        result[i] = minHeap.poll();
    }
    return result;
}

Approach 2: Bucket Sort O(n)

Since frequency can be at most n, create n+1 buckets where bucket[i] holds all numbers with frequency i. Read from the highest-frequency bucket down until we collect k elements.

Java
public int[] topKFrequent(int[] nums, int k) {
    // Step 1: count frequencies
    Map<Integer, Integer> freq = new HashMap<>();
    for (int num : nums) {
        freq.put(num, freq.getOrDefault(num, 0) + 1);
    }

    // Step 2: bucket by frequency (index = frequency)
    List<Integer>[] buckets = new List[nums.length + 1];
    for (Map.Entry<Integer, Integer> entry : freq.entrySet()) {
        int f = entry.getValue();
        if (buckets[f] == null) buckets[f] = new ArrayList<>();
        buckets[f].add(entry.getKey());
    }

    // Step 3: collect top-k from highest frequency downward
    int[] result = new int[k];
    int idx = 0;
    for (int f = buckets.length - 1; f >= 1 && idx < k; f--) {
        if (buckets[f] != null) {
            for (int num : buckets[f]) {
                result[idx++] = num;
                if (idx == k) break;
            }
        }
    }
    return result;
}

Complexity Analysis
ApproachTimeSpace
HashMap + Min-HeapO(n log k)O(n + k)
Bucket SortO(n)O(n)