Top K Frequent Elements
Given an integer array nums and an integer k, return the k most frequent elements. The order of elements in the returned array doesn't matter.
Example 1:
Input: nums = [1,2,2,3,3,3], k = 2 Output: [3,2]
Example 2:
Input: nums = [1], k = 1 Output: [1]
Example 3:
Input: nums = [1,1,1,2,2,3], k = 2 Output: [1,2]
Recommended time and space complexity
The optimal solution has O(n) time complexity and O(n) space complexity, where n is the size of the input array.
Hint 1
The first step is to count the frequency of each element. What data structure is best to use for this?
Hint 2
After counting frequencies, how can you efficiently find the k most frequent elements? Think about data structures that work well with finding top-k elements.
Hint 3
Instead of using sorting or heaps, think about the Bucket Sort method. Since element frequency cannot exceed the array size, we can use an array of "buckets" where the index represents frequency.