Top K Frequent Elements
Problem Description
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Example 1:
Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]
Example 2:
Input: nums = [1], k = 1
Output: [1]
Example 3:
Input: nums = [1,2,1,2,1,2,3,1,3,2], k = 2
Output: [1,2]
Constraints:
- 1 <= nums.length <= 105
- -104 <= nums[i] <= 104
kis in the range[1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
Solve it on LeetCode
Approaches
1. Sorting
Intuition:
The most straightforward way to find the top k frequent elements is to count the frequency of each element using a hashmap, then sort the elements based on their frequency in descending order, and finally pick the first k elements from this sorted list.
Steps:
- Create a hashmap to count the frequency of each element.
- Transform hashmap entries into a list of pairs and sort it based on frequency.
- Extract the first
kelements from the sorted list.
Code:
- Time Complexity: O(N log N) due to sorting operation, where N is the number of elements in
nums. - Space Complexity: O(N) for storing the frequency map.
2. Priority Queue
Intuition:
Instead of sorting all elements, we can use a Min-Heap (Priority Queue) to keep track of the top k elements. As we iterate through the hashmap, we maintain the size of the heap to be at most k by removing the smallest element whenever the size exceeds k.
Steps:
- Use a hashmap to count the frequency of each element.
- Use a priority queue to keep track of the top
kelements. - Iterate through the map and push each entry into the Min-Heap, evicting the smallest when the heap exceeds size
k.
Code:
- Time Complexity: O(N log k) due to the heap operations, where N is the number of elements in
nums. - Space Complexity: O(N) for the frequency map and O(k) for the heap.
3. Bucket Sort
Intuition:
We can utilize a bucket sort technique since the maximum frequency of any element can't exceed the number of elements. We'll create an array of lists where each index corresponds to a frequency, then we'll fill each list with the numbers that have the respective frequency.
Steps:
- Build the frequency map.
- Create buckets where index corresponds to frequency, and append elements to respective buckets.
- Iterate from the end of the bucket array to pick the top
kfrequent elements.
Code:
- Time Complexity: O(N), where N is the number of elements in
nums. This is because we are only doing constant-time operations per element. - Space Complexity: O(N) for storing the frequency map and bucket list.