Given an integer array and a number k, return the k most frequent elements. The answer can be in any order.
DSA Animator › DSA Revision › Heap / Priority Queue › Top K Frequent Elements
Remember: count first, then keep the top k with a min heap. Bucket sort by frequency is the O of n alternative. The video solves Top K Frequent Elements (LeetCode 347, Medium) with the Count + Min Heap pattern from the Heap / Priority Queue topic, and you can replay every step in the interactive Top K Frequent Elements animation.
Given an integer array and a number k, return the k most frequent elements. The answer can be in any order.
For 1, 1, 1, 2, 2, 3 with k equal to 2, the answer is 1 and 2. 1 appears three times, 2 appears twice, and 3 appears once.
You could count the frequencies, then sort all distinct values by frequency. That is O of n log n. With a heap of size k, we only keep the best k candidates.
First, count every value with a hash map. Then go through the map, and push each value into a min heap ordered by frequency. If the heap grows beyond k, poll the root, which is the least frequent value in it. At the end, the heap holds exactly the k most frequent values.
The counts are 1 appears 3 times, 2 appears 2 times, and 3 appears once. Push 1 with frequency 3. Push 2 with frequency 2, and it becomes the root, because 2 is smaller than 3. Push 3 with frequency 1, which makes three entries. Poll the root, which is 3, the least frequent. The heap holds 2 and 1, so the answer is 1 and 2.
In code, build the count map with merge or get or default. Create a min heap that compares counts. For every key, offer it, and poll when the size is greater than k. Finally, pour the heap into the result array. Counting is O of n, and the heap work is O of n log k.
Remember: count first, then keep the top k with a min heap. Bucket sort by frequency is the O of n alternative.