Top K Frequent Elements — Practice

Problem

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

Examples

Example 1

Input: nums = [1,1,1,2,2,3], k = 2

Output: [1,2]

Constraints

•1 <= nums.length <= 10^5
•k is in the range [1, the number of unique elements in the array].

Hints

Hint 1

Counting frequencies first with a hash map is the same starting step regardless of approach — the real design decision is what to do with those frequencies next.

Hint 2

A min-heap of size k (not a max-heap of everything) is the space-efficient way to track 'the k largest seen so far' — anything smaller than the heap's current minimum can never make the cut.

Hint 3

Since frequency is bounded by the array's own length, BUCKET SORT (one bucket per possible frequency value) avoids comparison-based sorting or heap operations entirely, reaching O(n).

Solutions

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 by frequency — keeps only the k most frequent
    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
    }
    return minHeap.stream().mapToInt(i -> i).toArray();
}

Time: O(n log k) · Space: O(n)