Top K Frequent Elements - Python Leetcode Solution

 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.

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        heap = [(-freq, word) for word, freq in count.items()]
        heapq.heapify(heap)
        return [heapq.heappop(heap)[1] for _ in range(k)]
        

TC: O(nlogn) SC: O(n)

class Solution:
    def topKFrequent(self, nums: List[int], k: int) -> List[int]:
        count = collections.Counter(nums)
        buckets = [[] for _ in range(max(count.values())+1)]
        for i,freq in count.items(): buckets[freq].append(i) 
        flat_list = [item for bucket in buckets for item in bucket]
        return flat_list[::-1][:k]

TC: O(n) SC: O(1)