Problem Statement
Given an unsorted array of numbers, find the top K frequently occurring numbers in it.
Example 1:
Input: [1, 3, 5, 12, 11, 12, 11], K = 2
Output: [12, 11]
Explanation: Both '11' and '12' appeared twice.
Example 2:
Input: [5, 12, 11, 3, 11], K = 2
Output: [11, 5] or [11, 12] or [11, 3]
Explanation: Only '11' appeared twice; all other numbers appeared once.
Constraints:
- 1 <= nums.length <= 10<sup>5</sup>
- -10<sup>5</sup> <= nums[i] <= 10<sup>5</sup>
- k is in the range [1, the number of unique elements in the array].
- If there are multiple valid answers, you can return any of them.
Why this is a Top 'K' Elements problem
| What the question says | The signal it matches |
|---|---|
| "find the top 'K' frequently occurring numbers in it" | the wording is K most frequent |
| "Both '11' and '12' appeared twice" | the ordering is by a count |
This is the most or least frequent variant: a count from a hash map built first.
The closest alternative. Count with a map, then sort the entries by count and take the first K. It is the version most people write, and it is correct.
This problem is two patterns joined, and noticing the join is the skill. Hash Maps answers how often, and this pattern answers which K are the most. The map has to be complete before any answer is possible, so the pass over the array cannot be avoided. Only the second stage is a choice: a heap of size K over the distinct values, rather than a full ordering of them.
Solution
This problem follows Top 'K' Numbers. The only difference is that in this problem, we need to find the most frequently occurring number compared to finding the largest numbers.
We can follow the same approach as discussed in the Top K Elements problem. However, in this problem, we first need to know the frequency of each number, for which we can use a HashMap. Once we have the frequency map, we can use a Min Heap to find the K most frequently occurring number. In the Min Heap, instead of comparing numbers we will compare their frequencies in order to get frequently occurring numbers
Code
Here is what our algorithm will look like:
Time Complexity
The time complexity of the above algorithm is O(N+N∗logK).
Space Complexity
The space complexity will be O(N). Even though we are storing only K numbers in the heap. For the frequency map, however, we need to store all the N numbers.