Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. The algorithm's time complexity must be better than O(N log N), where N is the array's size.
Requirements
- ✓Return the k most frequent elements in any order.
- ✓Time complexity must be strictly better than O(N log N).
- ✓Handle negative numbers and arrays with all identical elements.
- ✓k is always valid (1 <= k <= number of unique elements).
Constraints & Scale
- —1 <= nums.length <= 10^5
- —-10^4 <= nums[i] <= 10^4
- —k is in the range [1, the number of unique elements in the array].
- —It is guaranteed that the answer is unique.
Understand
Guided mode
Why does full sorting take O(N log N)? What approaches avoid full sorting? Compare min-heap vs bucket sort.
Context & Constraints — Human Reviewed
First pass: frequency map takes O(N) time and O(U) space where U is unique elements. Full sort on frequencies is O(U log U). Min-heap of size k is O(N log k). Bucket sort where index represents frequency is O(N) linear time.
Trade-offs
- ⚖Min-heap: O(N log k) time, O(N) space. Works on streaming data where total size N is unknown ahead of time.
- ⚖Bucket sort: O(N) time, O(N) space. Requires finite bounded frequency space (max frequency is N).
Concepts used in this stage