Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
1 <= nums.length <= 10^5k is in the range [1, the number of unique elements in the array].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.
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.
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).
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)