Given an integer array nums and an integer k,
return the k most frequent elements. The answer may be returned in any order.
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Input: nums = [1], k = 1
Output: [1]
Constraints:
- 1 <= nums.length <= 105
- k is in the range [1, the number of unique elements in nums]
- The answer is guaranteed to be unique.
Contents
- Approach 1 — HashMap + Min-Heap O(n log k)
- Approach 2 — Bucket Sort O(n)
- Complexity Analysis
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.
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;
}
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.
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;
}
| Approach | Time | Space |
|---|
| HashMap + Min-Heap | O(n log k) | O(n + k) |
| Bucket Sort | O(n) | O(n) |