Top K Frequent Elements Java | Fresher Interview
Fast recall
Quick revision
Core answer
Whether you count first, then pick top-K with a size-K min-heap (O(n log K)) or bucket sort (O(n))
Sorting all elements by frequency (O(n log n)) when a size-K heap or bucket sort is better, or a max-heap of all n
Explain why a size-K MIN-heap beats a full max-heap, and offer bucket sort as the O(n) optimum
Interview-ready guide
Interview answer
The first step for top K frequent elements is always frequency counting: I make one pass and build a map from each element to how many times it appears.
The interesting part is how I select the top K from those counts, and there are three approaches. The simplest is to sort all the entries by frequency and take the first K, but that's O of n log n, which is wasteful when K is small. A better approach is a min-heap of size K.
I push elements keyed by their count, and whenever the heap grows beyond K, I pop the smallest. The reason I use a min-heap and not a max-heap is subtle but important: with a size-K min-heap, the smallest of the current top K is always at the top, so it's cheap to evict it when a more frequent element comes along.
At the end the heap holds exactly the K most frequent elements, and the total time is O of n log K, which beats full sorting when K is much smaller than n. The optimal approach is bucket sort.
Since any element's frequency is between one and n, I can make an array of lists where the index is the frequency, drop each element into the bucket matching its count, and then collect elements from the highest-frequency buckets downward until I have K. That's linear, O of n time.
So in an interview I'd present the size-K min-heap as my main answer and mention bucket sort as the linear-time optimization.
For example, [1, 1, 1, 2, 2, 3] gives counts {1=3, 2=2, 3=1}. With k = 2, the two highest counts belong to 1 and 2, so the result is [1, 2].
Top K Frequent Elements Java | Fresher Interview
Direct Answer
Count frequencies in a map, then select the top K. Two good options: a min-heap of size K over (element, count) gives O(n log K) time; or bucket sort by frequency (index = count) gives O(n) time. Avoid sorting all counts (O(n log n)) when K is small. The heap keeps only the K best seen so far.
Deep Dive & Architecture
The problem has two stages: count each value, then keep the k values with the largest counts. A HashMap handles counting, and a min-heap ordered by frequency keeps only the best k candidates seen so far.
Worked example: [1, 1, 1, 2, 2, 3], k = 2
The map is {1=3, 2=2, 3=1}. Add entries to the heap. Whenever its size exceeds 2, remove the smallest frequency. After all three entries, frequency 1 is removed, leaving values 1 and 2. Their output order can be arbitrary unless the problem specifies a tie or ranking rule.
The heap's root is the weakest selected candidate, so a better candidate can replace it immediately. Building the counts costs O(n). If there are m distinct values, heap work costs O(m log k), and storage is O(m + k).
Sorting all m frequency entries is simpler but costs O(m log m). Bucket sorting by frequency can reach O(n) time because no count exceeds n, but it uses an array of buckets. Clarify what should happen when counts tie and validate that 0 <= k <= m; those details affect deterministic output and error handling.
Common Mistakes & Pitfalls
- Sorting everything: O(n log n) when a size-K heap is O(n log K).
- Max-heap of all n: O(n + k log n); a size-K min-heap is better for small K.
- Comparator direction: for a min-heap by count use
freq.get(a) - freq.get(b). - Forgetting bucket sort: it's the O(n) optimum since counts are bounded by n.
Check your understanding
Answer these without looking back at the article.
- What is the frequency counting pattern and when do you apply it?
- How do you group strings that are anagrams together?
- How do you find the first non-repeating character in a string?
Looking for a structured roadmap?
Every module on this page is also part of the full Java backend interview track.