https://leetcode.com/problems/top-k-frequent-elements

There are solution, using quickselect with O(n) complexity in average, but I think they are overcomplicated: actually, there is O(n) solution, using 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]

If you like the solution, you can upvote it on leetcode discussion section: Problem 0347