Top K Frequent Elements Problem

Question

Given a non-empty array of integers, return the k most frequent elements.

Example 1:

Input: nums = [1,1,1,2,2,3], k = 2
Output: [1,2]

Example 2:

Input: nums = [1], k = 1
Output: [1]

Note:

• You may assume k is always valid, 1 ≤ k ≤ number of unique elements.
• Your algorithm's time complexity must be better than O(n log n), where n is the array's size.
• It's guaranteed that the answer is unique, in other words the set of the top k frequent elements is unique.
• You can return the answer in any order.

Answer 1

Bucket sort. 

The idea, is that frequency of any element can not be more than n. So, the plan is the following:

1. Create list of empty lists for bucktes: for frequencies 1, 2, ..., n.
2. Use Counter to count frequencies of elements in nums
3. Iterate over our Counter and add elements to corresponding buckets.
4. buckets is list of lists now, create one big list out of it.
5. Finally, take the k last elements from this list, these elements will be top K frequent elements.

Complexity: 

time complexity is O(n), because we first iterate over nums once and create buckets, then we flatten list of lists with total number of elements O(n) and finally we return last k elements. 

Space complexity is also O(n).

class Solution:     def topKFrequent(self, nums, k):         bucket = [[] for _ in range(len(nums) + 1)]         Count = Counter(nums).items()           for num, freq in Count: bucket[freq].append(num)          flat_list = list(chain(*bucket))         return flat_list[::-1][:k]

eg : ans = Solution()

nums = [1,1,1,2,2,3], k = 2

ans.topKFrequent(nums, k)

Output -

[1,2]