Top K Frequent Elements
The briefingthe full drill, in my own words
The drill: Pull out the k values that appear most often in an array. Every solution counts first; the pace difference is entirely in how you select the winners from the tally — and there is a way to skip the comparison sort altogether.
An array of integers and a count k arrive together, and the task is to report the k values that occur most often across the whole array.
Ties in frequency don't need any particular tiebreak — as long as exactly k values come back and each one genuinely belongs among the most frequent, the order of the result is free.
On this course, k is always small enough, and the array varied enough, that exactly k distinct values can be identified as the answer without ambiguity over who belongs.
- arrays hold up to several thousand elements
- k is always between 1 and the number of distinct values present
- ties in frequency don't require a specific tiebreak
- the k returned values may come back in any order
The hintstake only what you need
HINT 1 THE NUDGE
Tally first — that part is forced. The open question is selecting the k largest counts without ordering everything.
HINT 2 THE STRUCTURE
A frequency is an integer between 1 and n. Values drawn from a small known range can be sorted by address instead of by comparison — that is a bucket sort.
HINT 3 ONE STEP FROM THE ANSWER
Build bucket[f] = the values occurring exactly f times, then read the buckets from f = n downward, collecting until you hold k values.
Coach's boardthe pattern, step by step
nums = [4, 4, 4, 6, 6, 2], k = 2. Tally frequencies first, then bucket by count instead of sorting.
The splitstwo paces, two languages
class Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freq = collections.Counter(nums)
buckets = [[] for _ in range(len(nums) + 1)] # buckets[f]: values seen f times
for v, f in freq.items():
buckets[f].append(v)
ans = []
for f in range(len(nums), 0, -1): # sweep from the top bucket down
for v in buckets[f]:
ans.append(v)
if len(ans) == k:
return ans
return ansclass Solution:
def topKFrequent(self, nums: List[int], k: int) -> List[int]:
freq = collections.Counter(nums)
ranked = sorted(freq, key=lambda v: freq[v], reverse=True)
return ranked[:k]class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : nums) freq.merge(v, 1, Integer::sum);
List<List<Integer>> buckets = new ArrayList<>(); // buckets.get(f): values seen f times
for (int f = 0; f <= nums.length; f++) buckets.add(new ArrayList<>());
for (Map.Entry<Integer, Integer> e : freq.entrySet()) {
buckets.get(e.getValue()).add(e.getKey());
}
int[] ans = new int[k];
int filled = 0;
for (int f = nums.length; f >= 1 && filled < k; f--) { // top bucket down
for (int v : buckets.get(f)) {
ans[filled++] = v;
if (filled == k) break;
}
}
return ans;
}
}class Solution {
public int[] topKFrequent(int[] nums, int k) {
Map<Integer, Integer> freq = new HashMap<>();
for (int v : nums) freq.merge(v, 1, Integer::sum);
List<Integer> ranked = new ArrayList<>(freq.keySet());
ranked.sort((a, b) -> Integer.compare(freq.get(b), freq.get(a)));
int[] ans = new int[k];
for (int i = 0; i < k; i++) ans[i] = ranked.get(i);
return ans;
}
}✓ CHIP-TIMEDALL 4 SOLUTIONS RAN GREEN AGAINST SELF-AUTHORED CASES IN CI · JDK 21 · CPYTHON 3.12 · NOTHING PUBLISHES RED