Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. You may return the answer in any order.
Sample Input: nums = [1,1,1,2,2,3], k = 2
Expected Output: [1, 2]
1 appears 3 times, 2 appears 2 times. The top 2 are 1 and 2.
Constraints
1 <= nums.length <= 105-104 <= nums[i] <= 104kis in the range [1, the number of unique elements in the array].- It is guaranteed that the answer is unique.
How We Solve This
- Count how often each element appears using a HashMap.
- Keep the top k elements in a min-heap:
- If the heap has less than k elements, add the current element.
- If the heap is full and the current element’s frequency is higher than the smallest in the heap, replace the smallest.
- The heap now contains the k most frequent elements.
Edge Cases to Consider
Empty Array
Input:
[]k:
2Output:
[]Should return an empty list if the input array is empty.
All Elements Unique
Input:
[1, 2, 3, 4]k:
2Output:
[1, 2]When all frequencies are 1, the first k elements encountered are returned.
Tie in Frequencies
Input:
[1, 1, 2, 2, 3]k:
1Output:
[1]If frequencies are tied, the element with the smaller value is chosen based on iteration order.
Negative Numbers
Input:
[-1, -1, -2]k:
1Output:
[-1]The algorithm should handle negative numbers correctly.