Top K Frequent Elements
Solve this ProblemTest Case 1:
Test Case 2:
Test Case 3:
Constraints
- ◆
1 ≤ nums.length ≤ 100 - ◆
-100 ≤ nums[i] ≤ 100 - ◆
1 ≤ k ≤ number of distinct values in nums - ◆
The result is ordered by frequency, highest first; values with equal frequency are ordered by value, smallest first, so the answer is always unique
Try the Dry Run
Don't just read the solution — watch it execute, one step at a time.
Approach & Solutions
Brute Force — Count, Then Fully Sort
GoodCount how often each value appears using a hash map, then sort every distinct value by frequency (highest first, ties broken by value) and keep the first k. Simple and correct, but it fully sorts every distinct value even though only the top k are ever needed.
O(n log n)O(n)1class Solution {
2 public int[] topKFrequent(int[] nums, int k) {
3 Map<Integer, Integer> freq = new HashMap<>();
4 for (int num : nums) {
5 freq.merge(num, 1, Integer::sum);
6 }
7 List<Integer> values = new ArrayList<>(freq.keySet());
8 values.sort((a, b) -> freq.get(a).equals(freq.get(b)) ? a - b : freq.get(b) - freq.get(a));
9 int[] result = new int[k];
10 for (int i = 0; i < k; i++) {
11 result[i] = values.get(i);
12 }
13 return result;
14 }
15}Optimal — Bucket Sort by Frequency
OptimalCount frequencies the same way, but instead of sorting every distinct value, create one bucket per possible frequency (1 through n) and drop each value into the bucket matching its count. Then walk the buckets from the highest frequency down, collecting values until k of them have been gathered. Since a value can never appear more than n times, there are at most n buckets — no comparison-based sort is needed at all.
O(n)O(n)1class Solution {
2 public int[] topKFrequent(int[] nums, int k) {
3 Map<Integer, Integer> freq = new HashMap<>();
4 for (int num : nums) {
5 freq.merge(num, 1, Integer::sum);
6 }
7 int maxFreq = 0;
8 for (int f : freq.values()) maxFreq = Math.max(maxFreq, f);
9 List<List<Integer>> buckets = new ArrayList<>();
10 for (int i = 0; i <= maxFreq; i++) buckets.add(new ArrayList<>());
11 for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
12 buckets.get(e.getValue()).add(e.getKey());
13 }
14 List<Integer> result = new ArrayList<>();
15 for (int f = maxFreq; f >= 1 && result.size() < k; f--) {
16 for (int val : buckets.get(f)) {
17 if (result.size() < k) result.add(val);
18 }
19 }
20 result.sort((a, b) -> freq.get(a).equals(freq.get(b)) ? a - b : freq.get(b) - freq.get(a));
21 int[] output = new int[result.size()];
22 for (int i = 0; i < result.size(); i++) output[i] = result.get(i);
23 return output;
24 }
25}