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]
Constraints:
1 <= nums.length <= 105-104 <= nums[i] <= 104k is in the range [1, the number of unique elements in the array].
Follow up: Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
This approach uses a hash map to count the frequency of each element. We then use a min-heap to keep track of the top k elements.
We use a frequency map to track occurrences of each number. Then, we create a struct array for frequencies, sort it, and return the top k elements.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n log n) due to sorting.
Space Complexity: O(n) for storing frequencies.
This approach involves using bucket sort where we create buckets for frequency counts and then extract the top k frequent elements.
We manually record each element's frequency and sort the list based on counts into a frequency bucket. Then, we retrieve the top k elements.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n + k).
Space Complexity: O(n).
| Approach | Complexity |
|---|---|
| Using a Hash Map and Min-Heap | Time Complexity: O(n log n) due to sorting. |
| Using Bucket Sort | Time Complexity: O(n + k). |
Top K Frequent Elements - Bucket Sort - Leetcode 347 - Python • NeetCode • 665,789 views views
Watch 9 more video solutions →Practice Top K Frequent Elements with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor