#347 Top K Frequent Elements
frequently reported atMetaAppleOracleAmazonByteDance / TikTokWalmart
the problem
In plain words
Return the k most frequent elements, in any order. The answer is unique.
in nums = [1,1,1,2,2,3], k = 2
out [1,2]
in nums = [1], k = 1
out [1]
- 1 ≤ nums.length ≤ 10⁵
- -10⁴ ≤ nums[i] ≤ 10⁴
- k is in [1, number of distinct values]
- Follow-up: better than O(n log n)
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTop-k with a size-k heapCounting / bucket sortFrequency counting
Count first (HashMap). Then it's "top k by count": a size-k min-heap on counts, or — since counts are at most n — buckets indexed by count.
solutions
From brute force to optimal
Sort the distinct values by frequency, take the first k.
- count with
merge(x, 1, Integer::sum). - Sort keys by count descending.
- Take k.
m distinct values sorted — up to O(n log n).
Map and key list.
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int x : nums) count.merge(x, 1, Integer::sum); List<Integer> keys = new ArrayList<>(count.keySet()); keys.sort((a, b) -> Integer.compare(count.get(b), count.get(a))); // most frequent first int[] out = new int[k]; for (int i = 0; i < k; i++) out[i] = keys.get(i); return out; }}Heap ordered by count keeps the k most frequent.
- Count.
- Offer each distinct value; poll when size > k.
- Drain the heap.
m heap operations on a heap of ≤ k + 1.
Map plus heap.
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> count = new HashMap<>(); for (int x : nums) count.merge(x, 1, Integer::sum); // min-heap by count: the root is the weakest of the current top k PriorityQueue<Integer> heap = new PriorityQueue<>(Comparator.comparingInt(count::get)); for (int x : count.keySet()) { heap.offer(x); if (heap.size() > k) heap.poll(); } int[] out = new int[k]; for (int i = k - 1; i >= 0; i--) out[i] = heap.poll(); return out; }}bucket[c] lists values that appear exactly c times; walk buckets from n down.
- Count.
- Put each value in bucket[count].
- Collect from the highest bucket until k values.
Counting, filling and scanning n + 1 buckets are all linear.
The bucket lists.
class Solution { public int[] topKFrequent(int[] nums, int k) { Map<Integer, Integer> freq = new HashMap<>(); for (int x : nums) freq.merge(x, 1, Integer::sum); // bucket[c] = numbers that appear exactly c times; c can be at most n List<List<Integer>> bucket = new ArrayList<>(); for (int c = 0; c <= nums.length; c++) bucket.add(new ArrayList<>()); for (Map.Entry<Integer, Integer> e : freq.entrySet()) { bucket.get(e.getValue()).add(e.getKey()); } int[] result = new int[k]; int filled = 0; for (int c = nums.length; c >= 1 && filled < k; c--) { // highest count first for (int x : bucket.get(c)) { if (filled == k) break; result[filled++] = x; } } return result; }}Dry run
in the room
How to say it in the interview
talk track
- Counting is step one in every approach — say so, then discuss how to pick the top k.
- Offer the heap (O(n log k), great when k is small or data streams in), then bucket sort for O(n).
- Explain the min-heap direction: we keep the k largest, so the smallest of them must be on top to be evicted.
traps
- Offering all m values to a max-heap — it works, but it's O(m log m) and not what the follow-up wants.
- Subtraction comparators like
(a, b) -> count.get(a) - count.get(b)are fine for counts ≤ 10⁵ but overflow on arbitrary ints. PreferInteger.compare.
what they ask next
Follow-ups
Top K Frequent Words (LC 692)?
Same counting, but ties break alphabetically: the heap comparator becomes count ascending, then word descending (so the 'worst' word is on top). It has its own page in this chapter.
Data arrives as a stream?
Bucket sort needs all the counts. Keep a counting map and a size-k min-heap updated per element, or a Count-Min sketch for approximate heavy hitters.
before you submit
Edge cases to test
- k = number of distinct values: return all of them.
- Negative values: use a HashMap (or shift array indices by 10⁴).
- Ties inside the top k are fine; the k-th and (k+1)-th counts always differ, so the answer is unique.
practise next
Similar problems
- #692Top K Frequent WordsMediumin Heaps
- #215Kth Largest Element in an ArrayMediumin Heaps
- #1636Sort Array by Increasing FrequencyEasyin Sorting