Top K Frequent Elements
Find the k most frequent distinct values. Order the result by descending frequency; break ties by increasing value.
Work through the cases
3 examplesInput notation
Space-separated integers on line 1. Line 2 contains k, from 1 to the number of distinct values.Expected result
The selected values separated by spaces.Case 1
Input
4 4 4 2 2 9 2
Expected output
4 2
Case 2
Input
3 1 3 1
Expected output
3
Case 3
Input
-1 -1 0 2
Expected output
-1 0
These notes use simplified input/output notation. The linked platform defines the method signature and judge format.
FROM IDEA TO IMPLEMENTATION
Understand the approach.
Compare the documented approaches below. Brute force, better, and optimal versions appear where available; a direct exercise may need only one approach.
The k most frequent values. Full sort is O(nlog n). Only the top k frequencies matter. Count, then select the k largest frequencies. Counter.most_common(k) is a heap selection in O(nlog k).
We can use a hash table cnt to count the occurrence of each element, and then use a min heap (priority queue) to store the top k frequent elements.
First, we traverse the array once to count the occurrence of each element. Then, we iterate through the hash table, storing each element and its count into the min heap. If the size of the min heap exceeds k, we pop the top element of the heap to ensure the heap size is always k.
Finally, we pop the elements from the min heap one by one and place them into the result array.
The time complexity is O(n log k), and the space complexity is O(k). Here, n is the length of the array.
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> cnt = new HashMap<>();
for (int x : nums) {
cnt.merge(x, 1, Integer::sum);
}
PriorityQueue<Map.Entry<Integer, Integer>> pq
= new PriorityQueue<>(Comparator.comparingInt(Map.Entry::getValue));
for (var e : cnt.entrySet()) {
pq.offer(e);
if (pq.size() > k) {
pq.poll();
}
}
return pq.stream().mapToInt(Map.Entry::getKey).toArray();
}
}Reference code. Platform solutions may use supplied node types, imports, or collection libraries; foundational examples are complete programs.
Solutions adapted from Doocs / LeetCode contributors, licensed under CC BY-SA 4.0. Formatting changed; TypeScript versions converted to JavaScript. Supplemental implementations and approach notes added. Adapted solution material is available under the same license.