🧩 Problem Description
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
1
2
| Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
|
Example 2
1
2
| Input: nums = [1], k = 1
Output: [1]
|
💡 Intuition
Two common solutions:
Heap (PriorityQueue):
- Count frequencies using HashMap.
- Maintain a min-heap of size k.
- Time: O(n log k).
Bucket Sort:
- Frequencies range from 1 to n.
- Place numbers into buckets indexed by frequency.
- Traverse from high frequency to low until k elements are collected.
- Time: O(n).
🔢 Java Code (Heap)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
| import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[1] - b[1]);
for (Map.Entry<Integer, Integer> entry : freqMap.entrySet()) {
heap.offer(new int[]{entry.getKey(), entry.getValue()});
if (heap.size() > k) {
heap.poll();
}
}
int[] result = new int[k];
for (int i = k - 1; i >= 0; i--) {
result[i] = heap.poll()[0];
}
return result;
}
}
|
🔢 Java Code (Bucket Sort)
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
| import java.util.*;
class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freqMap = new HashMap<>();
for (int num : nums) {
freqMap.put(num, freqMap.getOrDefault(num, 0) + 1);
}
List<Integer>[] buckets = new List[nums.length + 1];
for (int key : freqMap.keySet()) {
int freq = freqMap.get(key);
if (buckets[freq] == null) {
buckets[freq] = new ArrayList<>();
}
buckets[freq].add(key);
}
List<Integer> result = new ArrayList<>();
for (int i = buckets.length - 1; i >= 0 && result.size() < k; i--) {
if (buckets[i] != null) {
result.addAll(buckets[i]);
}
}
return result.stream().mapToInt(x -> x).toArray();
}
}
|
⏱ Complexity Analysis
Heap Solution
- Time: O(n log k)
- Space: O(n)
Bucket Sort Solution
✍️ Summary
- Use heap for balanced performance.
- Use bucket sort for O(n) solution.
Related problems
lc-215 — Kth Largest Element in an Array lc-451 — Sort Characters By Frequency lc-973 — K Closest Points to Origin